It looks like you're new here. If you want to get involved, click one of these buttons!

- All Categories 2.3K
- Chat 500
- Study Groups 20
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 2
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 339
- MIT 2019: Lectures 79
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 69
- Azimuth Code Project 110
- Statistical methods 4
- Drafts 5
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 148
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 714

Options

Okay, now let's get to the cool part: Galois connections. Before he died in a duel, the young Évariste Galois proved that you couldn't solve the quintic equation with radicals: that is, there's nothing like the quadratic formula for equations like

$$ ax^5 + bx^4 + cx^3 + dx^2 + ex + f = 0. $$ He used a trick for converting one view of a problem into another, and then converting the other view back into the original one. By now, we've extracted the essence of this trick and dubbed it a "Galois connection". It's far more general than Galois dreamed.

Remember, a **preorder** is a set \(A\) with a relation \(\le_A\) that's reflexive and transitive. When we're in the mood for being careful, we write a preorder as a pair \( (A,\le_A)\). When we're feeling lazy we'll just call it something like \(A\), and just write \(\le\) for the relation.

**Definition.** Given preorders \((A,\le_A)\) and \((B,\le_B)\), a **monotone function** from \(A\) to \(B\) is a function \(f : A \to B\) such that

$$ x \le_A y \textrm{ implies } f(x) \le_B f(y) $$ for all elements \(x,y \in A\),

**Puzzle 10.** There are many examples of monotone maps between preorders. List a few interesting ones!

**Definition.** Given preorders \((A,\le_A)\) and \((B,\le_B)\), a **Galois connection** is a monotone function \(f : A \to B\) together with a monotone function \(g: B \to A\) such that

$$ f(a) \le_B b \textrm{ if and only if } a \le_A g(b) $$
for all \(a \in A, b \in B\). In this situation we call \(f\) the **left adjoint** and \(g\) the **right adjoint**.

So, the right adjoint of \(f\) is a way of going back from \(B\) to \(A\) that's related to \(f\) in some way.

**Puzzle 11.** Show that if the monotone function \(f: A \to B\) has an inverse \(g : B \to A \) that is also a monotone function, then \(g\) is *both a right adjoint and a left adjoint* of \(f\).

So, adjoints are some sort of generalization of inverses. But as you'll eventually see, they're much more exciting!

I will spend quite a few lectures describing really interesting examples, and you'll start seeing what Galois connections are good for. It shouldn't be obvious yet, unless you already happen to know or you're some sort of superhuman genius. I just want to get the definition on the table right away.

Here's one easy example to get you started. Let \(\mathbb{N}\) be the set of natural numbers with its usual notion of \(\le\). There's a function \(f : \mathbb{N} \to \mathbb{N}\) with \(f(x) = 2x \). This function doesn't have an inverse. But:

**Puzzle 12.** Find a right adjoint for \(f\): that is, a function \(g : \mathbb{N} \to \mathbb{N}\) with

$$ f(m) \le n \textrm{ if and only if } m \le g(n) $$ for all \(m,n \in \mathbb{N}\). How many right adjoints can you find?

**Puzzle 13.** Find a left adjoint for \(f\): that is, a function \(g : \mathbb{N} \to \mathbb{N}\) with

$$ g(m) \le n \textrm{ if and only if } m \le f(n) $$ for all \(m,n \in \mathbb{N}\). How many left adjoints can you find?

## Comments

Puzzle 10:If \(A, \leq_A\) is the ancestor graph (assuming everyone is a trivial self-ancestor) and \(\mathbb{N}, \geq\) is the usual preorder given by the conventional interpretation of \(\geq\) on the natural numbers, then theagefunction taking each person to their age in years is a monotone map: if \(x\) is an ancestor of \(y\), then \(\textrm{age}(x) \geq \textrm{age}(y)\). (Note that the converse does not hold.)There is also no requirement that \(A, \leq_A\) and \(B, \leq_B\) be distinct, so we could consider monotone maps from \(A, \leq_A\) to itself. For example, let \(A, \leq_A\) be the ancestry preorder in a colony of bacteria, and consider the

motherfunction which maps each cell \(x\) to its mother. (You might wonder why not its "parent", but it's an established convention in biology.) If \(x\) is an ancestor of \(y\), then \(x\)'s mother is an ancestor of \(y\)'s mother.Puzzle 11:I have a question about this one. Suppose \(A = \{a, b, c, d\}\) and \(\leq_A\) is given by: \(\leq_A = \{(a, c), (b, d), (a, a), (b, b), (c, c), (d, d)\}\). Let \( (B, \leq_B)\) be given by \(B=\{1, 2, 3, 4\}\) with \(\leq_B\) having the usual interpretation. Finally define \(f = \{(a, 1), (b, 2), (c, 3), (d, 4)\}\). Now \(f\) is a monotone map with an inverse \(g\), but \(g\) isn't a monotone map. In particular, \(2 \leq_B 3\) but we don't have \(b \leq_A c\). Maybe I'm confused?Puzzle 12:Let \(g = \lceil\frac{n}{2}\rceil\).Puzzle 13:Let \(g = \lfloor{\frac{n}{2}}\rfloor\). The proofs in both cases are pretty direct.Crudely speaking, if you draw \(f\) and \(g\) out on two natural number lines, then \(f\) and \(g\) being adjoints seems to amount to the condition that there are no "wires crossed" in the diagram. So if for every \(n \in \mathbb{N}\) there are two \(m\)'s that \(g\) could send it to, is the number of adjoints \(2^\mathbb{N}\)?

Apologies in advance for typos and thinkos.

`<b>Puzzle 10:</b> If \\(A, \leq_A\\) is the ancestor graph (assuming everyone is a trivial self-ancestor) and \\(\mathbb{N}, \geq\\) is the usual preorder given by the conventional interpretation of \\(\geq\\) on the natural numbers, then the <i>age</i> function taking each person to their age in years is a monotone map: if \\(x\\) is an ancestor of \\(y\\), then \\(\textrm{age}(x) \geq \textrm{age}(y)\\). (Note that the converse does not hold.) There is also no requirement that \\(A, \leq_A\\) and \\(B, \leq_B\\) be distinct, so we could consider monotone maps from \\(A, \leq_A\\) to itself. For example, let \\(A, \leq_A\\) be the ancestry preorder in a colony of bacteria, and consider the <i>mother</i> function which maps each cell \\(x\\) to its mother. (You might wonder why not its "parent", but it's an established convention in biology.) If \\(x\\) is an ancestor of \\(y\\), then \\(x\\)'s mother is an ancestor of \\(y\\)'s mother. <b>Puzzle 11:</b> I have a question about this one. Suppose \\(A = \\{a, b, c, d\\}\\) and \\(\leq_A\\) is given by: \\(\leq_A = \\{(a, c), (b, d), (a, a), (b, b), (c, c), (d, d)\\}\\). Let \\( (B, \leq_B)\\) be given by \\(B=\\{1, 2, 3, 4\\}\\) with \\(\leq_B\\) having the usual interpretation. Finally define \\(f = \\{(a, 1), (b, 2), (c, 3), (d, 4)\\}\\). Now \\(f\\) is a monotone map with an inverse \\(g\\), but \\(g\\) isn't a monotone map. In particular, \\(2 \leq_B 3\\) but we don't have \\(b \leq_A c\\). Maybe I'm confused? <b>Puzzle 12:</b> Let \\(g = \lceil\frac{n}{2}\rceil\\). <b>Puzzle 13:</b> Let \\(g = \lfloor{\frac{n}{2}}\rfloor\\). The proofs in both cases are pretty direct. Crudely speaking, if you draw \\(f\\) and \\(g\\) out on two natural number lines, then \\(f\\) and \\(g\\) being adjoints seems to amount to the condition that there are no "wires crossed" in the diagram. So if for every \\(n \in \mathbb{N}\\) there are two \\(m\\)'s that \\(g\\) could send it to, is the number of adjoints \\(2^\mathbb{N}\\)? Apologies in advance for typos and thinkos.`

Your definition here is given the careful way, but the text

Definition 1.70does it the lazy way, which confused me and sent me here where I gratefully found your careful definition, which you must have anticipated. I think the text should give the careful definition.`Your definition here is given the careful way, but the text **Definition 1.70** does it the lazy way, which confused me and sent me here where I gratefully found your careful definition, which you must have anticipated. I think the text should give the careful definition.`

I agree with Patrick #1 on

Puzzle 11(or have the same confusion!). A simpler example: Let \(A = \{a, b\}\) and \(\leq_A\) be only \(\leq_A = \{(a, a), (b,b)\}\). Let \( (B, \leq_B)\) be given by \(B=\{1, 2\}\) with the usual \(\leq_B\). Then \(f = \{(a, 1), (b, 2)\}\) is trivially monotone, but its inverse \(g\) clearly isn't.`I agree with Patrick #1 on **Puzzle 11** (or have the same confusion!). A simpler example: Let \\(A = \\{a, b\\}\\) and \\(\leq_A\\) be only \\(\leq_A = \\{(a, a), (b,b)\\}\\). Let \\( (B, \leq_B)\\) be given by \\(B=\\{1, 2\\}\\) with the usual \\(\leq_B\\). Then \\(f = \\{(a, 1), (b, 2)\\}\\) is trivially monotone, but its inverse \\(g\\) clearly isn't.`

Question:

The definition of a monotone map reminded me of homomorphism.

I remember seeing homomorphism in a data-base class, where it was defined as:

A homomorphism from a data-base instance \( K1 \) to another instance \( K2 \) is a mapping \(h\) from the domain of \(K1\) to the domain of \( K2 \) such that for every fact \( R(a_1, ..., a_n) \) in \( K1 \), we have that \( R(h(a_1), ..., h(a_n)) \) is a fact in \( K2 \).

We can read fact as just a relation.

If we restrict the relation \( R \) in the definition of homomorphism above to a binary transitive, reflexive and anti-symmetric relation, we have a monotone map.

How are homomorphism and monotonicity related?

When I look up the definition of homomorphism on Wikipedia, it looks different from the one above:

$$ f ( x \star y ) = f(x) \star f(y) $$ How do I conciliate these definitions?

`Question: The definition of a monotone map reminded me of homomorphism. I remember seeing homomorphism in a data-base class, where it was defined as: A homomorphism from a data-base instance \\( K1 \\) to another instance \\( K2 \\) is a mapping \\(h\\) from the domain of \\(K1\\) to the domain of \\( K2 \\) such that for every fact \\( R(a_1, ..., a_n) \\) in \\( K1 \\), we have that \\( R(h(a_1), ..., h(a_n)) \\) is a fact in \\( K2 \\). We can read fact as just a relation. If we restrict the relation \\( R \\) in the definition of homomorphism above to a binary transitive, reflexive and anti-symmetric relation, we have a monotone map. How are homomorphism and monotonicity related? When I look up the definition of homomorphism on Wikipedia, it looks different from the one above: $$ f ( x \star y ) = f(x) \star f(y) $$ How do I conciliate these definitions?`

Daniel, a homomorphism is a "structure preserving map". In the DB example, this means that mapping from one domain to another preserves facts; for posets, a monotone function (poset homomorphism, if you like) preserves ordering.

As a monotone function, we know that: x ≤ y implies f(x) ≤ f(y)

If we regard the posets/mfs as categories & functors, then we are mapping not just the values, but the ordering relations. Then we might say: f(x ≤ y) = f(x) ≤ f(y), which just replaces ⋆ with ≤ from the Wikipedia definition. "The mapped ordering between x and y is equal to the ordering between the mapped x and mapped y"

`Daniel, a homomorphism is a "structure preserving map". In the DB example, this means that mapping from one domain to another preserves facts; for posets, a monotone function (poset homomorphism, if you like) preserves ordering. As a monotone function, we know that: x ≤ y implies f(x) ≤ f(y) If we regard the posets/mfs as categories & functors, then we are mapping not just the values, but the ordering relations. Then we might say: f(x ≤ y) = f(x) ≤ f(y), which just replaces ⋆ with ≤ from the Wikipedia definition. "The mapped ordering between x and y is equal to the ordering between the mapped x and mapped y"`

Thanks Thomas, that's a much clearer counterexample.

`Thanks Thomas, that's a much clearer counterexample.`

Thanks, Patrick and Thomas - I was confused about Puzzle 11. The inverse of a monotone map, if it exists, is not necessarily monotone. Your example shows why: if \(f : A \to B\) is monotone and invertible we have

$$ a \le_A a' \textrm{ implies } f(a) \le_B f(a') $$ for all \(a,a' \in A\), but saying that its inverse is monotone is equivalent to

$$ f(a) \le_B f(a') \textrm{ implies } a \le_A a' $$ and there's really no way to get this extra property out of thin air.

Let me say why I made such a dumb mistake. As Daniel and Ken point out, a monotone map between preorders is a bit like a homomorphism between groups: it's a map that

preserves the relevant structure. A preorder has a relation \(\le\) and a monotone map \(f : A \to B\) preserves this:$$ a \le_A a' \textrm{ implies } f(a) \le_B f(a') $$ A group has a multiplication \(\star\) and a homomorphism \(f : A \to B\) between groups preserves this:

$$ a \star_A a' = a'' \textrm{ implies } f(a) \star_B f(a') = f(a'') $$ A group also has an identity and inverses, and a homomorphism also preserves those too.

But the similarity is limited! If a function \(f : A \to B\) is a homomorphism between groups and it has an inverse, its inverse is also a homomorphism. That's what fooled me. If a function If a function \(f : A \to B\) is a monotone map between preorders and it has an inverse, its inverse

may not bea monotone map.The difference is that groups are described by an "algebraic theory": that is, they're described by

operationsobeying identities. Preorders are not: they're described by arelationobeying certain rules.`Thanks, Patrick and Thomas - I was confused about Puzzle 11. The inverse of a monotone map, if it exists, is not necessarily monotone. Your example shows why: if \\(f : A \to B\\) is monotone and invertible we have $$ a \le_A a' \textrm{ implies } f(a) \le_B f(a') $$ for all \\(a,a' \in A\\), but saying that its inverse is monotone is equivalent to $$ f(a) \le_B f(a') \textrm{ implies } a \le_A a' $$ and there's really no way to get this extra property out of thin air. Let me say why I made such a dumb mistake. As Daniel and Ken point out, a monotone map between preorders is a bit like a homomorphism between groups: it's a map that _preserves the relevant structure_. A preorder has a relation \\(\le\\) and a monotone map \\(f : A \to B\\) preserves this: $$ a \le_A a' \textrm{ implies } f(a) \le_B f(a') $$ A group has a multiplication \\(\star\\) and a homomorphism \\(f : A \to B\\) between groups preserves this: $$ a \star_A a' = a'' \textrm{ implies } f(a) \star_B f(a') = f(a'') $$ A group also has an identity and inverses, and a homomorphism also preserves those too. But the similarity is limited! If a function \\(f : A \to B\\) is a homomorphism between groups and it has an inverse, its inverse is also a homomorphism. That's what fooled me. If a function If a function \\(f : A \to B\\) is a monotone map between preorders and it has an inverse, its inverse _may not be_ a monotone map. The difference is that groups are described by an "[algebraic theory](https://en.wikipedia.org/wiki/Algebraic_theory)": that is, they're described by _operations_ obeying identities. Preorders are not: they're described by a _relation_ obeying certain rules.`

Note, Daniel, that my definition of "homomorphism" makes its resemblance to a monotone map a bit clearer. Using my notation, Wikipedia told you that a homomorphism \(f : A \to B\) obeys

$$ f(a \ast_A a') = f(a) \ast_B f(a') $$ for all \(a,a' \in A\). This is equivalent to what I said:

$$ a \ast_A a' = a'' \textrm{ implies } f(a) \ast_B f(a') = f(a'') $$ for all \(a,a',a'' \in A\). The Wikipedia definition is more efficient and more commonly used, but my definition shows what's going on: we're taking a fact that holds in \(A\), apply \(f\) to each of the elements involved, and claim that the corresponding fact must hold in \(B\). That's the general idea of a "structure-preserving map", of which homomorphisms and monotone maps are special cases.

This becomes an incredibly important theme in category theory, and one could write a book about it. My mistake in Problem 11 shows one of the subtleties: operations work a bit differently than relations.

`Note, Daniel, that my definition of "homomorphism" makes its resemblance to a monotone map a bit clearer. Using my notation, Wikipedia told you that a homomorphism \\(f : A \to B\\) obeys $$ f(a \ast_A a') = f(a) \ast_B f(a') $$ for all \\(a,a' \in A\\). This is equivalent to what I said: $$ a \ast_A a' = a'' \textrm{ implies } f(a) \ast_B f(a') = f(a'') $$ for all \\(a,a',a'' \in A\\). The Wikipedia definition is more efficient and more commonly used, but my definition shows what's going on: we're taking a fact that holds in \\(A\\), apply \\(f\\) to each of the elements involved, and claim that the corresponding fact must hold in \\(B\\). That's the general idea of a "structure-preserving map", of which homomorphisms and monotone maps are special cases. This becomes an incredibly important theme in category theory, and one could write a book about it. My mistake in Problem 11 shows one of the subtleties: operations work a bit differently than relations.`

A constant function from one preorder into a another is a monotone function.

`A constant function from one preorder into a another is a monotone function.`

The identity function on a preorder is a monotone function.

`The identity function on a preorder is a monotone function.`

Thanks Patrick and Thomas, your question clarified puzzle 11 for me also.

Patrick, regarding puzzles 12 and 13, I think the answers you gave are indeed adjoints but flipped (right -> left, left -> right). For example, take m=2, n=3 for puzzle 12:

$$f(2)\leq 3 \textrm{ if and only if } 2\leq g(3)$$ $$ 4 \leq 3 \textrm{ if and only if } 2 \leq \lceil \frac{3}{2} \rceil = 2 $$ which is no good. Of course, I may have made a thinko myself...

`Thanks Patrick and Thomas, your question clarified puzzle 11 for me also. Patrick, regarding puzzles 12 and 13, I think the answers you gave are indeed adjoints but flipped (right -> left, left -> right). For example, take m=2, n=3 for puzzle 12: $$f(2)\leq 3 \textrm{ if and only if } 2\leq g(3)$$ $$ 4 \leq 3 \textrm{ if and only if } 2 \leq \lceil \frac{3}{2} \rceil = 2 $$ which is no good. Of course, I may have made a thinko myself...`

I hope folks straighten out the answers to Puzzles 12 and 13. It's very easy to get mixed up between left and right in category theory, or \(\le\) and \(\ge\) in preorders.

But in fact, the answers are less important than the method of figuring out those answers. There's a lot of wisdom about adjoints to be gained from these puzzles! I'll explain it soon, but in the meantime I'd really appreciate solutions where people explain their work.

This is generally true for all my puzzles: learning category theory is a process of changing how you think, so seeing how people solve problems is more useful than seeing the answers. In category-theoretic terms, there's more to an arrow than its source and target!

`I hope folks straighten out the answers to Puzzles 12 and 13. It's very easy to get mixed up between left and right in category theory, or \\(\le\\) and \\(\ge\\) in preorders. But in fact, the answers are less important than the method of figuring out those answers. There's a lot of wisdom about adjoints to be gained from these puzzles! I'll explain it soon, but in the meantime I'd really appreciate solutions where people explain their work. This is generally true for all my puzzles: learning category theory is a process of changing how you think, so seeing how people solve problems is more useful than seeing the answers. In category-theoretic terms, there's more to an arrow than its source and target!`

The powerset \(2 ^ S\), which consists of all subsets of \(S\), is a preorder (and a poset) under the inclusion relation.

For another set \(T\), the function from \(2 ^ S\) into \(2 ^ T\) that is defined by intersection with \(T\) is monotone.

`The powerset \\(2 ^ S\\), which consists of all subsets of \\(S\\), is a preorder (and a poset) under the inclusion relation. For another set \\(T\\), the function from \\(2 ^ S\\) into \\(2 ^ T\\) that is defined by intersection with \\(T\\) is monotone.`

Lingo: monotone functions are also called order-preserving functions. The dual notion is an order-reversing function, aka an anti-monotone function.

`Lingo: monotone functions are also called order-preserving functions. The dual notion is an order-reversing function, aka an anti-monotone function.`

Puzzle 10not decreasing sequences, and functions are monotonic. But this is sort of not in the spirit of the posets we're exploring.Puzzle 11 post fixIf \( f : A \rightarrow B \) and its inverse \(g: B \rightarrow A \) are both monotonic. Then \( f(a) \leq b \Rightarrow g(f(a)) \leq g(b) \Rightarrow a \leq g(b) \) and similarly for the opposite direction.The formalism makes this feel more sophisticated then it is. Consider the map \(f(x) = x + 1\), then clearly $$ a + 1 \leq b \Leftrightarrow a \leq b - 1 $$

Puzzle 12The way I thought about this, was by imagining the function \(f(m) = 2m\) as a stretched number line, with0, 2, 4, 6, ...

Being the "next thing larger than 2" makes our number 3 or 4.

EDIT: I need to justify my choice of bundles better, these led to an incorrect adjointI want to wrap up the numbers in these bundles {3, 4}, {5, 6} back to "next thing larger by 1" or before \(f\). In this case {3, 4} would get mapped to 2, {5, 6} to 3, etc. Rounding up, after dividing by 2 does this. So \(g = \lceil\frac{n}{2}\rceil\) as Patrick said.

To verify this more formally. Note division by 2, and ceiling are both monotonic. Hence their composition is monotonic. So we get

$$ 2m \leq n \Rightarrow m \leq n/2 \Rightarrow \lceil m \rceil \leq \lceil n/2\rceil \Rightarrow m \leq \lceil n/2 \rceil $$

EDIT: the following paragraph is wrongThe other direction isn't too bad. It's clear it should work, because the numbers in the above "bundles" stay in their bundles, doing the proof in the opposite direction.EDIT:Apparently I don't know how to use the word "clear". I can't prove the reverse direction, Cole's comment gives the counter example.This intuition makes it feel like this answer is almost unique though, which doesn't seem quite right to me.

`**Puzzle 10** not decreasing sequences, and functions are monotonic. But this is sort of not in the spirit of the posets we're exploring. **Puzzle 11 post fix** If \\( f : A \rightarrow B \\) and its inverse \\(g: B \rightarrow A \\) are both monotonic. Then \\( f(a) \leq b \Rightarrow g(f(a)) \leq g(b) \Rightarrow a \leq g(b) \\) and similarly for the opposite direction. The formalism makes this feel more sophisticated then it is. Consider the map \\(f(x) = x + 1\\), then clearly $$ a + 1 \leq b \Leftrightarrow a \leq b - 1 $$ **Puzzle 12** The way I thought about this, was by imagining the function \\(f(m) = 2m\\) as a stretched number line, with 0, 2, 4, 6, ... Being the "next thing larger than 2" makes our number 3 or 4. **EDIT: I need to justify my choice of bundles better, these led to an incorrect adjoint** I want to wrap up the numbers in these bundles {3, 4}, {5, 6} back to "next thing larger by 1" or before \\(f\\). In this case {3, 4} would get mapped to 2, {5, 6} to 3, etc. Rounding up, after dividing by 2 does this. So \\(g = \lceil\frac{n}{2}\rceil\\) as Patrick said. To verify this more formally. Note division by 2, and ceiling are both monotonic. Hence their composition is monotonic. So we get $$ 2m \leq n \Rightarrow m \leq n/2 \Rightarrow \lceil m \rceil \leq \lceil n/2\rceil \Rightarrow m \leq \lceil n/2 \rceil $$ **EDIT: the following paragraph is wrong** The other direction isn't too bad. It's clear it should work, because the numbers in the above "bundles" stay in their bundles, doing the proof in the opposite direction. **EDIT:** Apparently I don't know how to use the word "clear". I can't prove the reverse direction, Cole's comment gives the counter example. This intuition makes it feel like this answer is almost unique though, which doesn't seem quite right to me.`

Let \(X\) be a set, \(\mathcal{P}(X)\) its power set ordered by inclusion (\(A \leq B\) iff \(A \subseteq B\)), and \(\mathcal{P}(X)^{op}\) its power set ordered by containment (\(A \leq B\) iff \(B \subseteq A\)). Then the function \(\mathcal P(X) \rightarrow \mathcal P(X)^{op}\) which sends a subset to its complement is monotone. In fact, I think it's an isomorphism, which would make it an adjoint.

`Let \\(X\\) be a set, \\(\mathcal{P}(X)\\) its power set ordered by inclusion (\\(A \leq B\\) iff \\(A \subseteq B\\)), and \\(\mathcal{P}(X)^{op}\\) its power set ordered by containment (\\(A \leq B\\) iff \\(B \subseteq A\\)). Then the function \\(\mathcal P(X) \rightarrow \mathcal P(X)^{op}\\) which sends a subset to its complement is monotone. In fact, I think it's an isomorphism, which would make it an adjoint.`

Cole, my answers agree with yours. Assuming that an adjoint exists, proposition 1.88 gives a way to construct it, so I used that, simplified a bit and then verified that the functions I got were the required adjoints.

I think in the case of Puzzles 12 and 13 the adjoints are unique. Suppose \( f : A \rightarrow B \) is left adjoint to \( g \) and that we can uniquely determine an element \( x \) of \( A \) by the set of elements \( \{ a \in A | a \leq x \} \). Then the choice of \( f \) seems to uniquely determine the value of \( g(b) \) for every \( b \in B \), since $$ a \leq g(b) \Leftrightarrow f(a) \leq b $$ EDIT: To clarify, suppose \( d : A \rightarrow \mathcal P (A) \) defined by \( d(x) = \{ a \in A | a \leq x \} \) has a left inverse \( h \). Then \( g(b) = h(d(g(b))) = h( \{ a \in A | a \leq g(b) \} ) = h( \{ a \in A | f(a) \leq b \} ) \)

`Cole, my answers agree with yours. Assuming that an adjoint exists, proposition 1.88 gives a way to construct it, so I used that, simplified a bit and then verified that the functions I got were the required adjoints. I think in the case of Puzzles 12 and 13 the adjoints are unique. Suppose \\( f : A \rightarrow B \\) is left adjoint to \\( g \\) and that we can uniquely determine an element \\( x \\) of \\( A \\) by the set of elements \\( \\{ a \in A | a \leq x \\} \\). Then the choice of \\( f \\) seems to uniquely determine the value of \\( g(b) \\) for every \\( b \in B \\), since $$ a \leq g(b) \Leftrightarrow f(a) \leq b $$ EDIT: To clarify, suppose \\( d : A \rightarrow \mathcal P (A) \\) defined by \\( d(x) = \\{ a \in A | a \leq x \\} \\) has a left inverse \\( h \\). Then \\( g(b) = h(d(g(b))) = h( \\{ a \in A | a \leq g(b) \\} ) = h( \\{ a \in A | f(a) \leq b \\} ) \\)`

Scaling by a nonnegative integer is a monotone mapping from the integers into the integers (using the standard ordering).

`Scaling by a nonnegative integer is a monotone mapping from the integers into the integers (using the standard ordering).`

And scaling by a negative integer is an antimonotone mapping.

`And scaling by a negative integer is an antimonotone mapping.`

Example of a monotone mapping: a function that maps \(\mathbb{Z}\) to \(\mathbb{Z}\) by adding a constant \(c\) to the input integer, i.e., the translation function lambda x: x + c.

`Example of a monotone mapping: a function that maps \\(\mathbb{Z}\\) to \\(\mathbb{Z}\\) by adding a constant \\(c\\) to the input integer, i.e., the translation function lambda x: x + c.`

Example of a monotone mapping:

Let T be the nodes of a tree, ordered by the following relation: \(x \le y\) means \(x\) is an ancestor of \(y\) in the tree.

Let \(h(n)\) be the height of the node in the tree, i.e. the number of edges in the path from the root to the node.

Then \(h: T \rightarrow \mathbb{N}\) is a monotone mapping.

`Example of a monotone mapping: Let T be the nodes of a tree, ordered by the following relation: \\(x \le y\\) means \\(x\\) is an ancestor of \\(y\\) in the tree. Let \\(h(n)\\) be the height of the node in the tree, i.e. the number of edges in the path from the root to the node. Then \\(h: T \rightarrow \mathbb{N}\\) is a monotone mapping.`

I have a question: are there interesting things I can learn about (co)monads by studying adjoint monotone functions composed this way or that way?

`I have a question: are there interesting things I can learn about (co)monads by studying adjoint monotone functions composed this way or that way?`

Galois connections are adjoint functors for the category of preordered sets. You can show that whenever \(F \dashv G\) then \(G \circ F\) is a monad and \(F \circ G\) is a comonad.

We've been thinking about this in the Categories for the Working Hacker discussion group if you are interested.

`> I have a question: are there interesting things I can learn about (co)monads by studying adjoint monotone functions composed this way or that way? Galois connections are [adjoint functors](https://en.wikipedia.org/wiki/Adjoint_functors) for the category of preordered sets. You can show that whenever \\(F \dashv G\\) then \\(G \circ F\\) is a monad and \\(F \circ G\\) is a comonad. We've been thinking about this in the [Categories for the Working Hacker](https://forum.azimuthproject.org/discussion/comment/16072/#Comment_16072) discussion group if you are interested.`

Here's one inside a proof:

The Schröder–Bernstein Theorem. Let \(f: X \rightarrowtail Y\) and \(g: Y \rightarrowtail X\) be a pair of injections. There exists a bijection \(h: X \to Y\).Proof.Let \(f[A] := \{f(a)\ :\ a \in A\}\) denote the image of \(f\) and similarly let \(g[\cdot]\) denote the image of \(g\).

Define \(F: \mathcal{P}(X) \to \mathcal{P}(X)\) as follows:

$$ F(S) := X - g[Y - f[S]] $$

\(F\) is amonotone mapon \(\mathcal{P}(X)\) when ordered by set containment.Define \(\mu F\) to be:

$$ \mu F := \bigcap \{A \subseteq X\ :\ F(A) \subseteq A\} $$ Then \(F(\mu F) = \mu F\). This is the Knaster-Tarski Theorem and generalizes to any monotone map on any complete lattice to itself.

Finally, define \(h: X \to Y\):

$$h(x) := \begin{cases} f(x) & x \in \mu F \\ g^{-1}(x) & x \not\in \mu F \end{cases} $$ Then \(h\) is the desired bijection, and its inverse is given by:

$$h^{-1}(y) := \begin{cases} f^-1(y) & y \in f[\mu F] \\ g(y) & y \not\in f[\mu F] \end{cases} $$ It's straight forward to check these are both well defined, injective and indeed inverses.

\(\Box\)

`> **Puzzle 10.** There are many examples of monotone maps between posets. List a few interesting ones! Here's one inside a proof: **The Schröder–Bernstein Theorem**. Let \\(f: X \rightarrowtail Y\\) and \\(g: Y \rightarrowtail X\\) be a pair of injections. There exists a bijection \\(h: X \to Y\\). **Proof**. Let \\(f[A] := \\{f(a)\ :\ a \in A\\}\\) denote the image of \\(f\\) and similarly let \\(g[\cdot]\\) denote the image of \\(g\\). Define \\(F: \mathcal{P}(X) \to \mathcal{P}(X)\\) as follows: $$ F(S) := X - g[Y - f[S]] $$ *\\(F\\) is a **monotone map** on \\(\mathcal{P}(X)\\) when ordered by set containment.* Define \\(\mu F\\) to be: $$ \mu F := \bigcap \\{A \subseteq X\ :\ F(A) \subseteq A\\} $$ Then \\(F(\mu F) = \mu F\\). This is the [Knaster-Tarski Theorem](https://en.wikipedia.org/wiki/Knaster%E2%80%93Tarski_theorem) and generalizes to any monotone map on any complete lattice to itself. Finally, define \\(h: X \to Y\\): $$h(x) := \begin{cases} f(x) & x \in \mu F \\\\ g^{-1}(x) & x \not\in \mu F \end{cases} $$ Then \\(h\\) is the desired bijection, and its inverse is given by: $$h^{-1}(y) := \begin{cases} f^-1(y) & y \in f[\mu F] \\\\ g(y) & y \not\in f[\mu F] \end{cases} $$ It's straight forward to check these are both well defined, injective and indeed inverses. \\(\Box\\)`

One example of a monotone map would the simple substitution cipher mapping letters to numbers, so given \( (A,\le_A) \)= ({a,b, ... , z}, alphabetical order ) and \( (B,\le_B) \) = ({1,2, ... , 26}, numerical order), then the

monotone mapfrom \(A\) to \(B\) is \(f : a \to 1 , b \to 2 , ... , z \to 26 \).apologies if my mathematical notation isn't correct...

`One example of a monotone map would the simple substitution cipher mapping letters to numbers, so given \\( (A,\le_A) \\)= ({a,b, ... , z}, alphabetical order ) and \\( (B,\le_B) \\) = ({1,2, ... , 26}, numerical order), then the **monotone map** from \\(A\\) to \\(B\\) is \\(f : a \to 1 , b \to 2 , ... , z \to 26 \\). apologies if my mathematical notation isn't correct...`

Related to

Puzzle 11.. Is it true that for a monotone map f:X->Y that has an inverse g:Y->X, there will always exist a monotone map h:Y->X [not necessarily g]?I see from the example in https://forum.azimuthproject.org/discussion/comment/16151/#Comment_16151 . The problem is that the preorder Y may be equipped with arrows that are not representable in X. Can you describe what type of arrows are problematic?

`Related to **Puzzle 11.**. Is it true that for a monotone map f:X->Y that has an inverse g:Y->X, there will always exist a monotone map h:Y->X [not necessarily g]? I see from the example in https://forum.azimuthproject.org/discussion/comment/16151/#Comment_16151 . The problem is that the preorder Y may be equipped with arrows that are not representable in X. Can you describe what type of arrows are problematic?`

Fredrick Eisele wrote:

I'm assuming you're looking for a monotone map \(h\) in the same direction as \(g\), that is, if \(f:A\to B\) is an invertible monotone map, is there always a monotone map \(h:B\to A\)? The answer is yes, but in general \(h\) doesn't need to have much to do with \(f\) or \(g\).

The reason is that as long as \(A\) isn't empty, there's always a monotone map \(h:B\to A\)—just pick any one element of \(A\) and send everything there! If \(A\) is empty, there aren't any monotone maps \(B\to A\) from nonempty \(B\)'s, but fortunately, in that case, the existence of the bijective function \(f:A\to B\) tells you that \(B\) must be empty too. Then the empty function \(B\to A\) is monotone, like you want.

`Fredrick Eisele wrote: > Related to **Puzzle 11.**. Is it true that for a monotone map f that has an inverse g, there will always exist a monotone map h [not necessarily g]? I'm assuming you're looking for a monotone map \\(h\\) in the same direction as \\(g\\), that is, if \\(f:A\to B\\) is an invertible monotone map, is there always a monotone map \\(h:B\to A\\)? The answer is yes, but in general \\(h\\) doesn't need to have much to do with \\(f\\) or \\(g\\). The reason is that as long as \\(A\\) isn't empty, there's always a monotone map \\(h:B\to A\\)—just pick any one element of \\(A\\) and send everything there! If \\(A\\) is empty, there aren't any monotone maps \\(B\to A\\) from nonempty \\(B\\)'s, but fortunately, in that case, the existence of the bijective function \\(f:A\to B\\) tells you that \\(B\\) must be empty too. Then the empty function \\(B\to A\\) is monotone, like you want.`

I see a pattern which I'm sharing just to make sure I'm understanding correctly. Starting with \(2x\) and repeatedly getting the right adjoint, I see:

\(2x\), \(\lfloor\frac{n}{2}\rfloor\), \(2x+1\), \(\lfloor\frac{n-1}{2}\rfloor\), \(2x+2\), \(\lfloor\frac{n-2}{2}\rfloor\), ...

So Puzzle 12 would be \(\lfloor\frac{n}{2}\rfloor\) and Puzzle 13 would be \(\lfloor\frac{n+1}{2}\rfloor\). Am I crazy?

`I see a pattern which I'm sharing just to make sure I'm understanding correctly. Starting with \\(2x\\) and repeatedly getting the right adjoint, I see: \\(2x\\), \\(\lfloor\frac{n}{2}\rfloor\\), \\(2x+1\\), \\(\lfloor\frac{n-1}{2}\rfloor\\), \\(2x+2\\), \\(\lfloor\frac{n-2}{2}\rfloor\\), ... So Puzzle 12 would be \\(\lfloor\frac{n}{2}\rfloor\\) and Puzzle 13 would be \\(\lfloor\frac{n+1}{2}\rfloor\\). Am I crazy?`

Alex Varga - I haven't carefully checked your answers, but you're certainly not crazy: it works something like this.

`Alex Varga - I haven't carefully checked your answers, but you're certainly not crazy: it works something like this.`

Ken Scambler wrote::

Yes! I'm assuming from your question that you know preorders are secretly categories of a special sort and Galois connection are secretly adjoint functors of a special sort. So, you are in a position to think about things like this:

Puzzle:if we think of a preorder \(A\) as a category, what does a monad on \(A\) amount to?Usually a monad on \(A\) consists of a functor \(T : A \to A\) together with some natural transformations obeying some properties. So, when \(A\) is a preorder, we know a monad on \(A\) will consist of a monotone function \(T: A \to A\) equipped with some extra bells and whistles. But preorders are so simple compared to categories in general that a lot of these bells and whistles will become trivial! But not everything: a monad on a preorder is more than just an arbitrary monotone function \(T : A \to A\). It's actually something incredibly interesting and important. And you can have a lot of fun figuring this out yourself.

Once you figure this out, there's more fun to be had by seeing what comonads are like in this context,

and by studying monads and comonads that come from composing adjoint monotone functions this way or that way.

`[Ken Scambler wrote:](https://forum.azimuthproject.org/discussion/comment/16256/#Comment_16256): > I have a question: are there interesting things I can learn about (co)monads by studying adjoint monotone functions composed this way or that way? Yes! I'm assuming from your question that you know preorders are secretly categories of a special sort and Galois connection are secretly adjoint functors of a special sort. So, you are in a position to think about things like this: **Puzzle:** if we think of a preorder \\(A\\) as a category, what does a monad on \\(A\\) amount to? Usually a monad on \\(A\\) consists of a functor \\(T : A \to A\\) together with some natural transformations obeying some properties. So, when \\(A\\) is a preorder, we know a monad on \\(A\\) will consist of a monotone function \\(T: A \to A\\) equipped with some extra bells and whistles. But preorders are so simple compared to categories in general that a lot of these bells and whistles will become trivial! But not everything: a monad on a preorder is more than just an arbitrary monotone function \\(T : A \to A\\). It's actually something incredibly interesting and important. And you can have a lot of fun figuring this out yourself. Once you figure this out, there's more fun to be had by seeing what comonads are like in this context, and by studying monads and comonads that come from composing adjoint monotone functions this way or that way.`

Puzzle 10:A baseball owner prints 1-4 stars by his players' names on the program based on which quartile their batting average is in (4 stars being best), and 0 stars by the names of players whose batting average is undefined (0 official at-bats). The mapping from players (ordered by batting average, if any) to number of stars (standard ordering) is monotone.Puzzle JW1:In this example, theconverseof the monotone mapping condition can fail in two ways. What are they?Puzzle JW2:Is the mapping still monotone if the players with undefined averages are lumped in with the 2-star players (i.e. given 2 stars instead of 0)?`**Puzzle 10:** A baseball owner prints 1-4 stars by his players' names on the program based on which quartile their batting average is in (4 stars being best), and 0 stars by the names of players whose batting average is undefined (0 official at-bats). The mapping from players (ordered by batting average, if any) to number of stars (standard ordering) is monotone. **Puzzle JW1:** In this example, the *converse* of the monotone mapping condition can fail in two ways. What are they? **Puzzle JW2:** Is the mapping still monotone if the players with undefined averages are lumped in with the 2-star players (i.e. given 2 stars instead of 0)?`

By the way, I encourage everyone to create puzzles for everyone else to solve, but we'll need a system to refer to these. Jerry's system is a reasonable start at this, as long as there's only one "JW" in town.

`By the way, I encourage everyone to create puzzles for everyone else to solve, but we'll need a system to refer to these. Jerry's system is a reasonable start at this, as long as there's only one "JW" in town.`

One doubt here, in 1.5.2, a Galois connection between the posets of partions of two sets \(S,T\) is built, given any function \(g:S \to T\). Can this construction be generalized for arbitrary relations \(G \subseteq S \times T\), so one still attains a Galois connection as before?

`One doubt here, in 1.5.2, a Galois connection between the posets of partions of two sets \\(S,T\\) is built, given any function \\(g:S \to T\\). Can this construction be generalized for arbitrary relations \\(G \subseteq S \times T\\), so one still attains a Galois connection as before?`

JS1The up and down tracks of a railway run in parallel, diverge symmetrically and then converge back to being parallel. How do you describe the gap between the tracks?`**JS1** The up and down tracks of a railway run in parallel, diverge symmetrically and then converge back to being parallel. How do you describe the gap between the tracks?`

As to the puzzle, we can check the idea that a closure operator is a monad of a monotone map \(T:P \to P\) defined in a poset \((P,\leq)\). The unit law implies that \(\forall p\in P: p \leq T(p)\), that's OK, but the multiplication law gives only \(\forall p \in P: T.T(p) \leq T(p)\), while we need equality \(T.T(p)=T(p)\). I cheated and went to the nLab for "closure operator", and there they demand that the monad be idempotent also, and that give us the equality.

`As to the puzzle, we can check the idea that a closure operator is a monad of a monotone map \\(T:P \to P\\) defined in a poset \\(\(P,\leq\)\\). The unit law implies that \\(\forall p\in P: p \leq T(p)\\), that's OK, but the multiplication law gives only \\(\forall p \in P: T.T(p) \leq T(p)\\), while we need equality \\(T.T(p)=T(p)\\). I cheated and went to the nLab for "closure operator", and there they demand that the monad be idempotent also, and that give us the equality.`

Jesus Lopez wrote:

That's a great question, but I don't instantly know the answer: I'd have to think about it for a while. For starters, I bet there are a couple of ways you could take a relation \(G \subseteq S \times T\) and a partition of \(S\) and get a partition of \(T\). I'd have to start by investigating the properties of these ways, though surely it's been done before, so if I were feeling lazy I'd just do a literature search or ask my pals.

Did you have a specific way in mind?

`[Jesus Lopez wrote](https://forum.azimuthproject.org/discussion/comment/16333/#Comment_16333): > Galois connection between the posets of partions of two sets \\(S,T\\) is built, given any function \\(g:S \to T\\). Can this construction be generalized for arbitrary relations \\(G \subseteq S \times T\\), so one still attains a Galois connection as before? That's a great question, but I don't instantly know the answer: I'd have to think about it for a while. For starters, I bet there are a couple of ways you could take a relation \\(G \subseteq S \times T\\) and a partition of \\(S\\) and get a partition of \\(T\\). I'd have to start by investigating the properties of these ways, though surely it's been done before, so if I were feeling lazy I'd just do a literature search or ask my pals. Did you have a specific way in mind?`

Alex Varga wrote:

For Puzzle 13 you seem to be saying that for natural numbers \(m\) and \(n\),

$$ \lfloor \frac{m+1}{2}\rfloor \le n \textrm{ if and only if } m \le 2n .$$ Is that what you're saying? It seems that Patrick O'Neill is claiming this solution to Puzzle 13:

$$ \lfloor \frac{m}{2}\rfloor \le n \textrm{ if and only if } m \le 2n .$$

`[Alex Varga wrote:](https://forum.azimuthproject.org/discussion/comment/16316/#Comment_16316) > So Puzzle 12 would be \\(\lfloor\frac{n}{2}\rfloor\\) and Puzzle 13 would be \\(\lfloor\frac{n+1}{2}\rfloor\\). Am I crazy? For Puzzle 13 you seem to be saying that for natural numbers \\(m\\) and \\(n\\), $$ \lfloor \frac{m+1}{2}\rfloor \le n \textrm{ if and only if } m \le 2n .$$ Is that what you're saying? It seems that [Patrick O'Neill](https://forum.azimuthproject.org/profile/1926/Patrick%20O%27Neill) is claiming this solution to Puzzle 13: $$ \lfloor \frac{m}{2}\rfloor \le n \textrm{ if and only if } m \le 2n .$$`

That is what I'm saying. Try both of those solutions with \( m = 1, n = 0 \).

Using Proposition 1.81, it suffices to prove \( f(g(n)) \le n \le g(f(n)) \) for all \( n \in \mathbb{N} \) with \( f(n) = \lfloor \frac{n+1}{2}\rfloor \) and \( g(n) = 2n \).

This gives \( \lfloor \frac{2n+1}{2} \rfloor \le n \le 2 \lfloor \frac{n+1}{2} \rfloor \) which checks out.

`That is what I'm saying. Try both of those solutions with \\( m = 1, n = 0 \\). Using Proposition 1.81, it suffices to prove \\( f(g(n)) \le n \le g(f(n)) \\) for all \\( n \in \mathbb{N} \\) with \\( f(n) = \lfloor \frac{n+1}{2}\rfloor \\) and \\( g(n) = 2n \\). This gives \\( \lfloor \frac{2n+1}{2} \rfloor \le n \le 2 \lfloor \frac{n+1}{2} \rfloor \\) which checks out.`

About #36, I was thinking in representing the relation \(G \subseteq S \times T\) as a function \(\hat{g} :S \to \mathcal{P}(T)\) and adapt the definition of page 21, so \(\forall s \in S, t \in T: s G t \iff t \in \hat{g}(s)\). Then define as there the partition in \(T\) in terms of the relation \(\sim\) given by \(\forall t_1, t_2 \in T: t_1 \sim t_2 \iff \exists s_1, s_2 \in S\) such that \(s_1 \sim s_2\) with \(t_1 \in \hat{g}(s_1)\) and \(t_2 \in \hat{g}(s_2)\), and forming its transitve closure.

`About #36, I was thinking in representing the relation \\(G \subseteq S \times T\\) as a function \\(\hat{g} :S \to \mathcal{P}(T)\\) and adapt the definition of page 21, so \\(\forall s \in S, t \in T: s G t \iff t \in \hat{g}(s)\\). Then define as there the partition in \\(T\\) in terms of the relation \\(\sim\\) given by \\(\forall t_1, t_2 \in T: t_1 \sim t_2 \iff \exists s_1, s_2 \in S\\) such that \\(s_1 \sim s_2\\) with \\(t_1 \in \hat{g}(s_1)\\) and \\(t_2 \in \hat{g}(s_2)\\), and forming its transitve closure.`

@Alex #38

I get a different form of the answer to Puzzle 13: \(g(n) = \lceil \frac{n}{2} \rceil\). But \( \lfloor \frac{n+1}{2} \rfloor\) is the same as \(\lceil \frac{n}{2} \rceil \): if n is even, we get \(\frac{n}{2}\); if n is odd, we get \(\frac{(n+1)}{2}\). So I think we agree (obviously still assuming \(f, g : \mathbb{N} \to \mathbb{N} \)).

Is there a name for this kind of "gauge"-like transformation between functions? Our forms are different but in the given domain and range, they behave identically.

`@Alex #38 > So Puzzle 12 would be \\(\lfloor\frac{n}{2}\rfloor\\) and Puzzle 13 would be \\(\lfloor\frac{n+1}{2}\rfloor\\). Am I crazy? I get a different form of the answer to Puzzle 13: \\(g(n) = \lceil \frac{n}{2} \rceil\\). But \\( \lfloor \frac{n+1}{2} \rfloor\\) is the same as \\(\lceil \frac{n}{2} \rceil \\): if n is even, we get \\(\frac{n}{2}\\); if n is odd, we get \\(\frac{(n+1)}{2}\\). So I think we agree (obviously still assuming \\(f, g : \mathbb{N} \to \mathbb{N} \\)). Is there a name for this kind of "gauge"-like transformation between functions? Our forms are different but in the given domain and range, they behave identically.`

I like the look of \(\lceil \frac{n}{2} \rceil\) a lot more than \( \lfloor \frac{n+1}{2} \rfloor \), because it goes along better with my story about the "best approximation from above" to \(\frac{n}{2}\). That's why I was so confused by Alex Varga's answer. But they're equal! You learn something new every day.

I don't know a name for this phenomenon, Cole.

`I like the look of \\(\lceil \frac{n}{2} \rceil\\) a lot more than \\( \lfloor \frac{n+1}{2} \\rfloor \\), because it goes along better with my story about the "best approximation from above" to \\(\frac{n}{2}\\). That's why I was so confused by Alex Varga's answer. But they're equal! You learn something new every day. I don't know a name for this phenomenon, Cole.`

Boolean algebras are an important kind of poset. The power set functor defines an (contravariant) equivalence \(P: \text{Set}^{\text{op}} \to \text{Bool}\): any function \(f: X \to Y\) corresponds to the

preimagemap \(f*: PY \to PX\), which is a monotone map, and also a boolean algebra homomorphism, meaning it preserves meets and joins (the very important fact that preimage preserves set operations).Even more interesting, this preimage has a left and right adjoint!

Puzzle CW: What are they?`Boolean algebras are an important kind of poset. The power set functor defines an (contravariant) equivalence \\(P: \text{Set}^{\text{op}} \to \text{Bool}\\): any function \\(f: X \to Y\\) corresponds to the *preimage* map \\(f*: PY \to PX\\), which is a monotone map, and also a boolean algebra homomorphism, meaning it preserves meets and joins (the very important fact that preimage preserves set operations). Even more interesting, this preimage has a left and right adjoint! **Puzzle CW**: What are they?`

Example 1: Order preserving string compression.

"... The index terms in an index tree, e.g. a B-tree [1],can store the order preserved compressed keys instead of the uncompressed variants. This permits a binary search within the index node, while facilitating increased fanout. This is particularly important when dealing with multifield keys [3]. Without being able to eliminate the storage used by the pad characters, the fixed size keys must be represented in full. Such multifield keys can destroy index node fanout. This leads to increased index tree height and reduced search performance, as well as greatly increasing the storage consumed by each index. ..."

'94 Antoshekov, Lomet, Murray

http://bitsavers.trailing-edge.com/pdf/dec/tech_reports/CRL-94-3.pdf

In general, most of the non-lossy encoding/compression techniques, I think, are monotone maps. And because they allow to go back to the original (they have inverses) it would also mean that they are Galois connections.

`> Puzzle 10. There are many examples of monotone maps between posets. List a few interesting ones! Example 1: Order preserving string compression. "... The index terms in an index tree, e.g. a B-tree [1],can store the order preserved compressed keys instead of the uncompressed variants. This permits a binary search within the index node, while facilitating increased fanout. This is particularly important when dealing with multifield keys [3]. Without being able to eliminate the storage used by the pad characters, the fixed size keys must be represented in full. Such multifield keys can destroy index node fanout. This leads to increased index tree height and reduced search performance, as well as greatly increasing the storage consumed by each index. ..." '94 Antoshekov, Lomet, Murray http://bitsavers.trailing-edge.com/pdf/dec/tech_reports/CRL-94-3.pdf In general, most of the non-lossy encoding/compression techniques, I think, are monotone maps. And because they allow to go back to the original (they have inverses) it would also mean that they are Galois connections.`

It looks like I need help wrt left and right adjoins.

When thinking about Puzzle 12, I am coming up with the following (and I think it is wrong): $$f(x) = x*10$$ and $$g(x) = x/2$$ So, my 'f' maps any natural number from set \(A\) into a set of numbers divisible by 10, my set \(B\).

My 'g', takes any element of the set of numbers divisible by 10 (the set \(B\) ), and maps into some natural number in set \(A\)

In my mind, these form a 'Galois connection'. Because (1) -- they are monotone maps (bigger input produces bigger output), and (2), they satisfy the $$ f(a) \le_B b \textrm{ if and only if } a \le_A g(b) $$

That is (as an example): \(f(5)=50\) and \(g(50)=25\). a = 5, b = 50

However, reading this Wikipedia page, it says that these functions should be inverses of each other (which is not the case in my example).

I have to be missing pieces, appreciate, in advance, help with this.

`It looks like I need help wrt left and right adjoins. When thinking about Puzzle 12, I am coming up with the following (and I think it is wrong): $$f(x) = x*10$$ and $$g(x) = x/2$$ So, my 'f' maps any natural number from set \\(A\\) into a set of numbers divisible by 10, my set \\(B\\). My 'g', takes any element of the set of numbers divisible by 10 (the set \\(B\\) ), and maps into some natural number in set \\(A\\) In my mind, these form a 'Galois connection'. Because (1) -- they are monotone maps (bigger input produces bigger output), and (2), they satisfy the $$ f(a) \le_B b \textrm{ if and only if } a \le_A g(b) $$ That is (as an example): \\(f(5)=50\\) and \\(g(50)=25\\). a = 5, b = 50 However, reading this [Wikipedia page](https://en.wikipedia.org/wiki/Galois_connection), it says that these functions should be inverses of each other (which is not the case in my example). I have to be missing pieces, appreciate, in advance, help with this.`

I'm glad you brought up that example, Vladislav Papayan! It's only for f(x)=2x that the left and right adjoints fit so snugly together.

Of course it's not the case that f and g have to be inverses of each other, but they have to be a little more like inverses than your g establishes.

`I'm glad you brought up that example, Vladislav Papayan! It's only for f(x)=2x that the left and right adjoints fit so snugly together. Of course it's not the case that f and g have to be inverses of each other, but they have to be a little more like inverses than your g establishes.`

\( 10a \leq b \Leftrightarrow a \leq b/10\) is not true iff \(a \leq b/2\), for example try a=10, b=20 which satisfies the latter but not the former inequality. So your f and g are not an adjoint pair.

`\\( 10a \leq b \Leftrightarrow a \leq b/10\\) is not true iff \\(a \leq b/2\\), for example try a=10, b=20 which satisfies the latter but not the former inequality. So your f and g are not an adjoint pair.`

Thank you @ValterSorana.

I think my 'bug' was, that I did understand how x, y (or a, b) are selected to work within $$ f(a) \le_B b \textrm{ if and only if } a \le_A g(b) $$ For some reason, I thought that f(a) = b . Which is why, it never entered my mind, to try b to be some other arbitrary number...

But when I re-read John's definition at the beginning of this lecture, there was a definition of a monotone map, right above the definition of the Galois connection. And in that definition, there was:

for

allelements \(x,y \in A\),So my two functions needed to work for

anyx, y -- which is clearly not the case with my g and f.But then, it seems like there are not a lot of pairs of functions that can do the above. At least, I am trying to develop, as per John's ask, some intuition -- of how to find those functions. And all I can come up with so far is: find monotone functions that have inverses. Then see if the inverse part of the relationship can be relaxed, while retaining the need Galois connection properties.

So f(x) = x*2 and f(x)=x/2 seem to work. However this, probably, too trivial to be useful. So I am not sure if I am on the right track in developing the needed intuition.

I also found this (by searching, no intuition) that inverse operation of strictly diagonally dominant matrix is monotone But not sure where to even start to see if that operation forms a galois connection.

`Thank you @ValterSorana. I think my 'bug' was, that I did understand how x, y (or a, b) are selected to work within $$ f(a) \le_B b \textrm{ if and only if } a \le_A g(b) $$ For some reason, I thought that f(a) = b . Which is why, it never entered my mind, to try b to be some other arbitrary number... But when I re-read John's definition at the beginning of this lecture, there was a definition of a monotone map, right above the definition of the Galois connection. And in that definition, there was: for *all* elements \\(x,y \in A\\), So my two functions needed to work for *any* x, y -- which is clearly not the case with my g and f. But then, it seems like there are not a lot of pairs of functions that can do the above. At least, I am trying to develop, as per John's ask, some intuition -- of how to find those functions. And all I can come up with so far is: find monotone functions that have inverses. Then see if the inverse part of the relationship can be relaxed, while retaining the need Galois connection properties. So f(x) = x*2 and f(x)=x/2 seem to work. However this, probably, too trivial to be useful. So I am not sure if I am on the right track in developing the needed intuition. I also found this (by searching, no intuition) that inverse operation of strictly diagonally dominant matrix is [monotone](https://math.stackexchange.com/questions/972725/show-that-the-inverse-of-a-strictly-diagonally-dominant-matrix-is-monotone?rq=1) But not sure where to even start to see if that operation forms a galois connection.`

Vladimir: if you take \(f : \mathbb{N} \to \mathbb{N}\) to be multiplication by 10:

$$ f(x) = 10 x $$ you can check that its right adjoint \(g: \mathbb{N} \to \mathbb{N}\) is

$$ g(x) = \lfloor \frac{x}{10} \rfloor $$ since for

allnatural numbers \(a\) and \(b\)$$ 10 a \le b \textrm{ if and only if } a \le \lfloor \frac{b}{10} \rfloor .$$ (Check this!) This fits nicely with our intuition that the right adjoint is the "best approximation from below" to the nonexistent inverse of \(f\).

Puzzle.What's the left adjoint of this function \(f\)?But you can also do other things. For example, let \(B\) be the set of natural numbers divisible by 10, and create a new function \(F : \mathbb{N} \to B \) defined by

$$ F(x) = 10 x $$ It looks like the same function, but it's different because it maps to a different set.

Puzzle.Does this function \(F\) have a right adjoint? If so, what is it?Puzzle.Does this function \(F\) have a left adjoint? If so, what is it?`Vladimir: if you take \\(f : \mathbb{N} \to \mathbb{N}\\) to be multiplication by 10: $$ f(x) = 10 x $$ you can check that its right adjoint \\(g: \mathbb{N} \to \mathbb{N}\\) is $$ g(x) = \lfloor \frac{x}{10} \rfloor $$ since for _all_ natural numbers \\(a\\) and \\(b\\) $$ 10 a \le b \textrm{ if and only if } a \le \lfloor \frac{b}{10} \rfloor .$$ (Check this!) This fits nicely with our intuition that the right adjoint is the "best approximation from below" to the nonexistent inverse of \\(f\\). **Puzzle.** What's the left adjoint of this function \\(f\\)? But you can also do other things. For example, let \\(B\\) be the set of natural numbers divisible by 10, and create a new function \\(F : \mathbb{N} \to B \\) defined by $$ F(x) = 10 x $$ It looks like the same function, but it's different because it maps to a different set. **Puzzle.** Does this function \\(F\\) have a right adjoint? If so, what is it? **Puzzle.** Does this function \\(F\\) have a left adjoint? If so, what is it?`

Thank you John. A question, if I may.

Why cannot g be just $$ g(x) = \frac{x}{10} $$ That is, without the floor?

is that because the pure less-than \(<\) part of the relation, must work as well? Or is it because, we are allowed to start our 'checks' with any b (say b=44) ? (because in that scenario, the \(g=x/10\) does not work, but \( g(x) = \lfloor \frac{x}{10} \rfloor \) does)

`Thank you John. A question, if I may. Why cannot g be just $$ g(x) = \frac{x}{10} $$ That is, without the floor? is that because the pure less-than \\(<\\) part of the relation, must work as well? Or is it because, we are allowed to start our 'checks' with any b (say b=44) ? (because in that scenario, the \\(g=x/10\\) does not work, but \\( g(x) = \lfloor \frac{x}{10} \rfloor \\) does)`

Vladislav wrote:

The problem is that \(x/10\) is not usually a natural number when \(x\) is a natural number. You're looking for the right adjoint of a function \(f : \mathbb{N} \to \mathbb{N}\). This must be a function \(g : \mathbb{N} \to \mathbb{N}\), that is, a function that takes natural numbers and gives natural numbers. So, \(g(x) = \frac{x}{10} \) can't possibly work!

Remember the definition:

Definition.Given preorders \((A,\le_A)\) and \((B,\le_B)\), aGalois connectionis a monotone map \(f : A \to B\) together with a monotone map \(g: B \to A\) such that$$ f(a) \le_B b \textrm{ if and only if } a \le_A g(b) $$ for all \(a \in A, b \in B\). In this situation we call \(f\) the

left adjointand \(g\) theright adjoint.`Vladislav wrote: > Why cannot g be just > $$ g(x) = \frac{x}{10} $$ > That is, without the floor? The problem is that \\(x/10\\) is not usually a natural number when \\(x\\) is a natural number. You're looking for the right adjoint of a function \\(f : \mathbb{N} \to \mathbb{N}\\). This must be a function \\(g : \mathbb{N} \to \mathbb{N}\\), that is, a function that takes natural numbers and gives natural numbers. So, \\(g(x) = \frac{x}{10} \\) can't possibly work! Remember the definition: **Definition.** Given preorders \\((A,\le_A)\\) and \\((B,\le_B)\\), a **Galois connection** is a monotone map \\(f : A \to B\\) together with a monotone map \\(g: B \to A\\) such that $$ f(a) \le_B b \textrm{ if and only if } a \le_A g(b) $$ for all \\(a \in A, b \in B\\). In this situation we call \\(f\\) the **left adjoint** and \\(g\\) the **right adjoint**.`