Suppose \(P \overset{g}{\underset{f}{\leftrightarrows}} Q\) are monotone maps. The following are equivalent:
f and g form a Galois connection where f is left adjoint to g
for every \(p \in P, q \in Q\) we have:
\(p \leq g(f(p))\)
\(f(g(q)) \leq q\)
Forward direction
Take any \(p \in P\) and let \(q = f(p) \in Q\)
By reflexivity, we have in \(Q\) that \(f(p) \leq q\)
By definition of Galois connection, we then have \(p \leq g(q)\), so (1) holds.
Take any \(q \in Q\) and let \(p = g(q) \in P\)
By reflexivity, we have in \(P\) that \(p \leq g(q)\)
By definition of Galois connection, we then have \(f(p) \leq q\), so (2) holds.
Reverse direction
Want to show \(f(p)\leq q \iff p \leq g(q)\)
Suppose \(f(p) \leq q\)
Since g is monotonic, \(g(f(p)) \leq g(q)\)
but, because (1), \(p \leq g(f(p))\), therefore \(p \leq g(q)\)
Suppose \(p \leq g(q)\)
Since f is monotonic, \(f(p) \leq f(g(q))\)
but, because (2), \(f(g(q)) \leq q\), therefore \(f(p) \leq q\)
Let \(P \overset{f}{\underset{g}{\rightleftarrows}} Q\) be monotone maps with \(f \dashv g\).
Right adjoints preserve meets
Left adjoints preserve joins
Given \(A \subseteq P\) and its image \(f(A) \subseteq Q\)
Then, if \(A\) has a join \(\vee A \in P\), then \(\vee f(a) \in Q\) exists
And \(f(\vee A) \cong \vee f(A)\)
Left adjoints preserve joins
let \(j = \vee A \subseteq P\)
Given f is monotone, \(\forall a \in A: f(a) \leq f(j)\), i.e. we have \(f(a)\) as an upper bound for \(f(A)\)
To show it is a least upper bound, take some arbitrary other upper bound b for \(f(A)\) and show that \(f(j) \leq b\)
Because \(j\) is the least upper bound of \(A\), we have \(j \leq g(b)\)
Using the Galois connection, we have \(f(j) \leq b\) showing that \(f(j)\) is the least upper bound of \(f(A) \subseteq Q\).
Right adjoints preserving meets is dual to this.
Adjoint functor theorem for preorders
Suppose \(Q\) is a preorder that has all meets and \(P\) is any preorder.
A monotone map \(Q \xrightarrow{g} P\) preserves meets iff it is a right adjoint.
Likewise, suppose \(P\) has all joins and \(Q\) is any preorder:
A monotone map \(P \xrightarrow{f} Q\) preserves joins iff it is a left adjoint.
Proved the reverse direction in Proposition 1.91.
Given a right adjoint, construct the left adjoint by:
\(f(p) := \bigwedge\{q \in Q\ |\ p \leq g(q)\}\)
First need to show this is monotone:
If \(p \leq p'\), the relationship between the joined sets of \(f(p)\) and \(f(p')\) is that the latter is a subset of the former.
By Proposition 1.91 we infer that \(f(p) \leq f(p')\).
Then need to show that it is satisfies the left adjoint property:
Show that \(p_0 \leq g(f(p_0))\)
\(p_0 \leq \bigwedge \{g(q)\ |\ p_0 \leq g(q)\} \cong g(\bigwedge\{q\ |\ p_0 \leq g(q)\}) = g(f(p_0))\)
The first inequality comes from the fact that the meet of the set (of which \(p_0\) is a lower bound) is a greatest lower bound.
The congruence comes from the fact that right adjoints preserve meets.
Show that \(f(g(q_0)) \leq q_0\)
\(f(g(q_0)) = \bigwedge\{q\ |\ g(q_0) \leq g(q)\} \leq \bigwedge \{q_0\} = q_0\)
The first inequality comes from Proposition 1.91 since \(\{q_0\}\) is a subset of the first set.
The second equality is a property of the meet of single element sets.
Proof of a left adjoint construction (assuming it preserves joins) is dual.
Let \(A \xrightarrow{f} B\) be a set function, say between apples and buckets into which we put each apple.
The ‘pullback along f’ \(\mathbb{P}(B) \xrightarrow{f^*} \mathbb{P}(A)\) maps each subset \(B' \subseteq B\) to its preimage \(f^{-1}(B') \subseteq A\)
It tells you for a set of buckets all the apples contained in total.
It is a monotonic map which has a left and right adjoint: \(f_! \dashv f^* \dashv f_*\)
The left adjoint \(\mathbb{P}(A)\xrightarrow{f_!}\mathbb{P}(B)\) is given by the direct image
\(f_!(A') := \{b \in B\ |\ \exists a \in A': f(a)=b\}\)
Tells you for a set of apples all the buckets that contain at least one of those apples.
The right adjoint \(\mathbb{P}(A) \xrightarrow{f_*} \mathbb{P}(B)\) is defined as follows:
\(f_*(A') := \{b \in B\ |\ \forall a: f(a)=b \implies a \in A'\}\)
Tells you all the buckets which are all-\(A\prime\) (note that empty buckets vacuously satisfy this condition).
Adjoints often turn out to have interesting semantic interpretations.
If we replace the \(\leq\) in Proposition 1.107 with \(=\), then we obtain the notion of a preorder isomorphism.
Since left adjoints preserve joins, we know a monotone map cannot have generative effects iff it is left adjoint to some other monotone.
Show that if \(P \xrightarrow{f}Q\) has a right adjoint g, then it is unique up to isomorphism. Is the same true for left adjoints?
Suppose \(h\) is also right adjoint to \(f\).
What it means for \(h \cong g\):
\(\forall q \in Q: h(q) \cong g(q)\)
\(g(q) \leq h(q)\)
Substitute \(g(q)\) for \(p\) in \(p \leq h(f(p))\) (from \(h\)’s adjointness) to get \(g(q) \leq h(f(g(q)))\)
Also apply \(h\) to both sides of \(f(g(q)) \leq q\) (from \(g\)’s adjointness) to get \(h(f(g(q)))\leq h(q)\)
The result follows from transitivity.
By symmetry (nothing was specified about \(h\) or \(g\)) the proof of \(h(q)\leq g(q)\) is the same.
Same reasoning for left adjoints.
Choose sets \(X,Y\) with between two and four elements each, and choose a function \(X \xrightarrow{f} Y\) NOCARD
Choose two different subsets \(B_1, B_2 \subseteq Y\) and find \(f^*(B_1)\) and \(f^*(B_2)\)
Choose two different subsets \(A_1, A_2 \subseteq X\) and find \(f_!(A_1)\) and \(f_!(A_2)\)
With the same \(A_1, A_2\) find \(f_*(A_1)\) and \(f_*(A_2)\)
\(\bar 3 \xrightarrow{f} \bar 4\) with \(\{1 \mapsto 2, 2 \mapsto 2, 3\mapsto 4\}\),\(A_1 = \{1,2\}, A_2=\{2,3\}, B_1=\{1\}, B_2=\{1,4\}\)
\(f^*(B_1)=\varnothing, f^*(B_2)=\{4\}\)
\(f_!(A_1)=\{2\},f_!(A_2)=\{2,4\}\)
\(f_*(A_1)=\{1,2,3\},f_*(A_2)=\{1,3,4\}\)