Options

Lecture 4 - Chapter 1: Galois Connections

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 posets. 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?

To read other lectures go here.

«1

Comments

  • 1.
    edited March 29

    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 the age 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 mother 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.

    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.

    Comment Source:<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.
  • 2.

    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.

    Comment Source: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.
  • 3.
    edited March 29

    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.

    Comment Source: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.
  • 4.

    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?

    Comment Source: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?
  • 5.
    edited March 29

    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"

    Comment Source: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"
  • 6.
    edited March 29

    Thanks Thomas, that's a much clearer counterexample.

    Comment Source:Thanks Thomas, that's a much clearer counterexample.
  • 7.

    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": that is, they're described by operations obeying identities. Preorders are not: they're described by a relation obeying certain rules.

    Comment Source: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.
  • 8.
    edited March 29

    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.

    Comment Source: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.
  • 9.

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

    Comment Source:A constant function from one preorder into a another is a monotone function.
  • 10.

    The identity function on a preorder is a monotone function.

    Comment Source:The identity function on a preorder is a monotone function.
  • 11.
    edited March 29

    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...

    Comment Source: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...
  • 12.
    edited March 29

    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!

    Comment Source: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!
  • 13.

    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.

    Comment Source: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.
  • 14.

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

    Comment Source:Lingo: monotone functions are also called order-preserving functions. The dual notion is an order-reversing function, aka an anti-monotone function.
  • 15.
    edited March 29

    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.

    Comment Source:**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.
  • 16.
    edited March 29

    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.

    Comment Source: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.
  • 17.
    edited March 29

    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 \} ) \)

    Comment Source: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 \\} ) \\)
  • 18.

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

    Comment Source:Scaling by a nonnegative integer is a monotone mapping from the integers into the integers (using the standard ordering).
  • 19.

    And scaling by a negative integer is an antimonotone mapping.

    Comment Source:And scaling by a negative integer is an antimonotone mapping.
  • 20.

    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.

    Comment Source: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.
  • 21.
    edited March 29

    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.

    Comment Source: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.
  • 22.

    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?

    Comment Source: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?
  • 23.

    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.

    Comment Source:> 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.
  • 24.
    edited March 30

    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 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\)

    Comment Source:> **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\\)
  • 25.
    edited March 30

    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...

    Comment Source: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...
  • 26.
    edited March 31

    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?

    Comment Source: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?
  • 27.

    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.

    Comment Source: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.
  • 28.

    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?

    Comment Source: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?
  • 29.

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

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

    Ken Scambler wrote::

    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.

    Comment Source:[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.
  • 31.

    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)?

    Comment Source:**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)?
  • 32.

    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.

    Comment Source: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.
  • 33.

    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?

    Comment Source: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?
  • 34.
    edited March 31

    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?

    Comment Source:**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?
  • 35.
    edited April 7

    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.

    Comment Source: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.
  • 36.
    edited April 1

    Jesus Lopez wrote:

    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?

    Comment Source:[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?
  • 37.
    edited April 1

    Alex Varga wrote:

    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 is claiming this solution to Puzzle 13:

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

    Comment Source:[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 .$$
  • 38.

    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.

    Comment Source: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.
  • 39.
    edited April 2

    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.

    Comment Source: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.
  • 40.
    edited April 4

    @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.

    Comment Source:@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.
  • 41.

    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.

    Comment Source: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.
  • 42.
    edited April 8

    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?

    Comment Source: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?
  • 43.

    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.

    Comment Source:> 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.
  • 44.
    edited April 7

    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.

    Comment Source: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.
  • 45.
    edited April 7

    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.

    Comment Source: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.
  • 46.
    edited April 7

    \( 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.

    Comment Source:\\( 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.
  • 47.
    edited April 8

    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 But not sure where to even start to see if that operation forms a galois connection.

    Comment Source: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.
  • 48.
    edited April 8

    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?

    Comment Source: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?
  • 49.

    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)

    Comment Source: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)
  • 50.
    edited April 9

    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.

    Comment Source: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**.
Sign In or Register to comment.