# 1.4. Galois connections

## Contents

# 1.4. Galois connections#

See also Galois connection and Adjoint functors.

## 1.4.1. Definition and examples of Galois connections#

Notice \(f\) is on the left side of the left equation, and \(g\) is on the right side of the right equation. Hence the names.

*Example* 1.97.#

The first paragraph of this example should replace the dummy variable \(x\) with \(y\). Otherwise, itâs
not clear in the next paragraph that \(x\) is always a real number and \(y\) is always an integer. The
relation in this example needs to hold for *any* real number and integer; e.g. the pair (x=3.1, y=2)
is always true, and (x=7.3, y=1) is always false. The author could have put this more precisely:

Or as:

See Floor and ceiling functions. By the definition of the ceiling function we have \(x \leq_\RR n \iff \lceil x \rceil \leq_\ZZ n\). If we substitute \(x/3\) for \(x\), and \(y\) for \(n\), we get the result from the text.

*Exercise* 1.98.#

We need a function from \(\RR \to \ZZ\); an obvious function to try given the last example is \(\lfloor x/3 \rfloor\).

See Floor and ceiling functions. By the definition of the floor function we have \(n \leq_\RR x \iff n \leq_\ZZ \lfloor x \rfloor\). If we substitute \(x/3\) for \(x\), and \(y\) for \(n\), we get:

As expected the right adjoint is \(\lfloor x/3 \rfloor\).

Reveal answer

*Exercise* 1.99.#

All of these cases (for part `1.`

) are true, so \(f\) is left adjoint to \(g\):

As we work through the cases for `2.`

we hit a failure:

Reveal answer

*Remark* 1.100.#

The right adjoint is red:

*Exercise* 1.101.#

We are interested in finding the function \(f\):

To fix the corner cases, one could define \(f(z)\) to be the first real number greater than \(3(z-1)\).

Looking forward, one could use Theorem 1.115 to define a left adjoint, although it would also be in an unsatisfying set-builder notation. Because \(g(r) = \lceil r/3 \rceil\) preserves meets (trivial given itâs a total order), then by that theorem it should be a right adjoint.

The answer given in the Appendix seems wrong, with the logic failing at:

In the same way, \(L(1) \leq r\) for all \(r > 0\), so \(L(1) \leq 0\).

Reveal answer

## 1.4.2. Back to partitions#

The â?â in \(\sim_T^?\) is meant to indicate that the relationship is âdoubtfulâ to the author, something that is already stated in the text. Itâs arguable whether it helps the explanation or not.

*Exercise* 1.103.#

The author asks for 6 examples in the question, then only bothers to do 4 in the Appendix. Doing so many is probably not a great use of time; this answer includes 5 only because the same drawings can be reused in the next question.

Reveal answer

*Exercise* 1.105.#

Reveal answer

*Exercise* 1.106.#

The parenthetical remark in `3.`

could be taken to mean you need to go back and fix your answer to
`1.`

if you canât answer `3.`

, because you apparently misunderstood something. More likely it simply
means you need to choose a partition in `1.`

that allows for both a coarser partition in `2.`

and a
non-coarser partition in `3.`

.

Reveal answer

## 1.4.3. Basic theory of Galois connections#

*Exercise* 1.109.#

For `1.`

take any \(q \in Q\) and let \(p := g(q)\). With this definition we have \(p \leq g(q)\),
which by the definition of a Galois connection implies \(f(p) \leq q\). Substituting the definition of
\(p\) in the last equation we get the desired result.

For `2.`

suppose \(p \leq g(q)\). Since \(f\) is monotonic we have \(f(p) \leq f(g(q))\), and substituting
\(f(g(q)) \leq q\) we get the desired result \(f(p) \leq q\).

Reveal answer

*Exercise* 1.110.#

Reveal answer

### Proposition 1.111#

See Complete lattice Â§ Morphisms of complete lattices for comments on the categories **Sup** (for supremum) and **Inf** (for infimum).

*Exercise* 1.112.#

Let \(A \in P\) be any subset and let \(j := \vee A\) be its join. Then since \(f\) is monotone \(f(a) \leq f(j)\) for all \(a \in A\), so \(f(j)\) is an upper bound for the set \(f(A)\). We must now show it is the least upper bound.

So take any other upper bound \(b\) for \(f(A)\); that is suppose that for all \(a \in A\), we have \(f(a) \leq b\) and we want to show \(f(j) \leq b\). Then by definition of \(f\) being a left adjoint we also have \(a \leq g(b)\). However since \(j\) is the least upper bound, we have \(j \leq g(b)\). Again using the Galois connection, we have \(f(j) \leq b\), proving that \(f(j)\) really is the least upper bound for \(f(A)\).

Reveal answer

*Exercise* 1.114.#

The second row in the solution for this question is incorrect.

Reveal answer

*Theorem* 1.115.#

*Example* 1.117.#

The names of the sets change from \(A\)/\(B\) to \(X\)/\(Y\) and then back again.

This section is confusing; the function \(f_{!}\) is a left adjoint not to \(f_*\) but \(f^*\). Similarly \(f_{*}\) is right adjoint to \(f^*\), not \(f_!\).

A similar example is given in category theory - A concrete intuition for Galois Connection - Math SE.

*Exercise* 1.118.#

Selecting the function and subsets:

Reveal answer

## 1.4.4. Closure operators#

See Closure operators on partially ordered sets.

Why do we use the term âinterior operatorâ for the other composite? Search for âclosureâ in Interior (topology). See also Interior algebra Â§ Modal logic and Interior algebra Â§ Definition.

*Exercise* 1.119.#

For `1.`

, this is simply a restatement of the first part of \(p \leq g(f(p))\) in Proposition 1.107.
but with different symbols.

For `2.`

, define \(q := f(p)\). Applying \(f(g(q)) \leq q\), we have \(f(g(f(p)) \leq f(p)\). Applying the
monotonicity property of \(g\) we then have \(g(f(g(f(p)))) \leq g(f(p))\), which is one half of what we
are trying to prove.

Define \(p_1 := g(f(p))\), and apply \(p_1 \leq g(f(p_1)\) to get \(g(f(p)) \leq g(f(g(f(p))))\), the second half of what we are trying to prove.

Reveal answer

*Example* 1.121.#

*Example* 1.122.#

For the term âinclusionâ used in this example, see Inclusion map.

It would be helpful to have an example to go with this example. See Upper set for the definition of an upper closure; letâs compute this closure on a simple preorder.

*Example* 1.123.#

See also Modal operator, although the article Modal logic provides a much more complete introduction to these two operators. See Geometric Shapes (Unicode block) for âwhite medium squareâ (âĄ) and âlozengeâ (â).

For more on propositional logic, see forall x: Calgary. An Introduction to Formal Logic.

### Which function is left and right?#

If you suspect or feel confident you have two functions that are adjoints, how do you determine which is left/right? In the examples in Section 1.4.1 above, the author establishes a convention that the left adjoint is a function from the top to bottom of a diagram and the right adjoint is a function from bottom to top. This means the label for the left adjoint (colored blue in most examples) is on an arrow going from top to bottom.

This doesnât help if you donât know which set to put on the top and bottom. Consider the following example, where weâre stripping the blue/red clue:

Recognize that the scales on your diagram donât matter. You should be able to stretch/scale or shift to the left/right the scales on top and bottom.

Form what will be either a closure or interior operator by composing the two functions; in this case weâll compose them as \(h_1=fâ¨g\) i.e. \(h_1=gâf\). On all pairs on top and bottom, check whether your composed function h is increasing (*extensive* per Closure operator) or decreasing. Similarly, form the opposite function \(h_2=fâg\) and apply the same tests.

If either function is not increasing or decreasing (both can be non-strictly), or what they do is not opposite, then you donât have an adjoint pair. Choose whichever function is not an identity, and pattern match it against the definitions of a closure/interior operator in this section to determine which is left/right.

In the example above, \(h_1\) is extensive and \(h_2\) is the identity function. Therefore \(f\) is the left adjoint, and \(g\) is the right adjoint (this drawing isnât actually too different than the one for Example 1.97 above).

## 1.4.5. Level shifting#

See Category of preordered sets.

*Exercise* 1.124.#

Reveal answer

*Exercise* 1.125.#

For `1.`

define the preorder \(\leq\):

Then we have \(U(\leq) = \{(1,3), (2,3), (1,1), (2,2), (3,3)\}\).

For `2.`

take the binary relations:

See Example 1.22 above; the authors are implying \(Cl\) is a closure and therefore a left adjoint. In
`3.`

weâll only show that \(Cl\) is monotone:

The preorder \(Cl(Q)\):

Clearly \(Cl(Q) \sqsubseteq \leq\) (see \(\leq\) defined in `1.`

above). For `4.`

we have:

The preorder \(Cl(Q')\):

Clearly \(Cl(Q) \not\sqsubseteq \leq\).

Reveal answer