Options

Exercise 103 - Chapter 1

Suppose that if \( f \) is left adjoint to \( g \) . Use Proposition 1.91 to show the following.

  1. \( p \le ( f .g)(p) \)
  2. \( ( f .g. f .g)(p) \cong ( f .g)(p) \). To prove this, show inequalities in both directions, \( \le \) and \( \ge \) .

Proposition 1.91. Suppose that \( f : P \rightarrow Q \) and \( g: Q \rightarrow P \) are functions. The following are equivalent

  1. \( f \) and \( g \) form a Galois connection where \( f \) is left adjoint to \( g \),
  2. for every \( p \in P \) and \( q \in Q \) we have \( f (g(q)) \le q \) and \( p \le g( f (p)) \) .

Definition [Equation]. A Galois connection between preorders P and Q is a pair of monotone maps. We say that \(f \) is the left adjoint and \(g\) is the right adjoint.

\( f : P \rightarrow Q \) and \( g : Q \rightarrow P \) such that \( f(p) \le q \iff p \le g(q) \).

Comments

  • 1.
    edited April 12

    The first point \( p \le (f.g)(p) \) comes directly from Proposition 1.81:1 with a change in notation \( (f.g)(p) = (g \circ f)(p) = g(f(p)) \).

    The second point proceeds in two steps, showing inequality in both directions.

    First show \( (f.g)(p) \le (f.g.f.g)(p) \).

    Let \( r = (f.g)(p) \) .

    Then by associativity of composition and substitution \( (f.g.f.g)(p) = (f.g)((f.g)(p)) = (f.g)(r) \).

    Taking \( r \le (f.g)(r) \) and substituting shows \( (f.g)(p) \le (f.g.f.g)(p) \).

    It remains to be shown that \( (f.g.f.g)(p) \le (f.g)(p) \).

    Exercise 83 - Chapter 1 shows that if there exists a right adjoint any other right adjoint will be isomorphic to the first.

    Comment Source:The first point \\( p \le (f.g)(p) \\) comes directly from Proposition 1.81:1 with a change in notation \\( (f.g)(p) = (g \circ f)(p) = g(f(p)) \\). The second point proceeds in two steps, showing inequality in both directions. First show \\( (f.g)(p) \le (f.g.f.g)(p) \\). Let \\( r = (f.g)(p) \\) . Then by associativity of composition and substitution \\( (f.g.f.g)(p) = (f.g)((f.g)(p)) = (f.g)(r) \\). Taking \\( r \le (f.g)(r) \\) and substituting shows \\( (f.g)(p) \le (f.g.f.g)(p) \\). It remains to be shown that \\( (f.g.f.g)(p) \le (f.g)(p) \\). [Exercise 83 - Chapter 1](https://forum.azimuthproject.org/discussion/1923) shows that if there exists a right adjoint any other right adjoint will be isomorphic to the first.
  • 2.

    Fredrick, the \((f.g)(p)≤(f.g.f.g)(p)\) part is indeed easy, however I'm struggling to see how right adjoint isomorphism works out here. I suspect that this is due to the fact that I'm not pretty sure what isomorphism between adjoints means. It should preserve some structure (meets?), but it seems that there is no need for bijection here, right? Because it is easy to find counter-examples for injective left adjoint, which have a number of right adjoints, mapping different \(q \in Q\) to different \(p \in P\), while still being monotone and preserving meets.

    Comment Source:[Fredrick](https://forum.azimuthproject.org/profile/2031/Fredrick%20Eisele), the \\((f.g)(p)≤(f.g.f.g)(p)\\) part is indeed easy, however I'm struggling to see how right adjoint isomorphism works out here. I suspect that this is due to the fact that I'm not pretty sure what isomorphism between adjoints means. It should preserve some structure (meets?), but it seems that there is no need for bijection here, right? Because it is easy to find counter-examples for injective left adjoint, which have a number of right adjoints, mapping different \\(q \in Q\\) to different \\(p \in P\\), while still being monotone and preserving meets.
  • 3.
    edited April 15

    Igor, the isomorphism is between the two right adjoint, not between right and left adjoints. But two right adjoints can be isomorphic (and not identical) only in a preorder (\( g(r) \le g'(r) \) and \( g(r) \ge g'(r) \) but \( g(r) \neq g'(r) \) ), in a poset RA are unique (when they exist). In other words, two monotone functions on a poset are isomorphic iff they are equal. (as Fredrick said, see Ex 83 - Ch 1)

    Comment Source:Igor, the isomorphism is between the two right adjoint, not between right and left adjoints. But two right adjoints can be isomorphic (and not identical) only in a preorder (\\( g(r) \le g'(r) \\) and \\( g(r) \ge g'(r) \\) but \\( g(r) \neq g'(r) \\) ), in a poset RA are unique (when they exist). In other words, two monotone functions on a poset are isomorphic iff they are equal. (as Fredrick said, see [Ex 83 - Ch 1](https://forum.azimuthproject.org/discussion/1923/exercise-83-chapter-1))
  • 4.

    Thank you Matias, of course I mean isomorphism between right adjoints, I apologize if something in my question pointed you to this sad conclusion :) Yes, indeed now I notice that in question we are talking about preorders, and indeed for posets there is no such notion, this was the source of my confusion - I couldn't imagine how these different functions may be isomorphic, and indeed they can't.

    Comment Source:Thank you [Matias](https://forum.azimuthproject.org/profile/1662/Matias%20Bossa), of course I mean isomorphism between right adjoints, I apologize if something in my question pointed you to this sad conclusion :) Yes, indeed now I notice that in question we are talking about preorders, and indeed for posets there is no such notion, this was the source of my confusion - I couldn't imagine how these different functions may be isomorphic, and indeed they can't.
  • 5.

    It is very interesting how allowing cycles in the graph (preorder) gives rise to this generation of right adjoints. Effectively, if one collapses the cycle to a single node, transforming the preorder to poset, all nodes belonged to the cycle (and giving rise to all these isomorphic right adjoints) become the same, collapsing right adjoints too into a unique one.

    Comment Source:It is very interesting how allowing cycles in the graph (preorder) gives rise to this generation of right adjoints. Effectively, if one collapses the cycle to a single node, transforming the preorder to poset, all nodes belonged to the cycle (and giving rise to all these isomorphic right adjoints) become the same, collapsing right adjoints too into a unique one.
  • 6.
    edited April 21

    Okay, still I feel like my understanding of the closure operator is not complete :) If anybody would be able to shed some light on the following, I would really appreciate. So I introduced two linear posets P and Q, P consisting of 3 elements, Q of 2, and I also defined left adjoint \(f\) (blue) and right adjoint \(g\) (orange) as below:

    PQPQ

    So \(f.g\) maps {1, 2} to {1}, and {3} is mapped to {2}. However, \(f.g.f.g\) maps {3} to {1}, while {1, 2} are still mapped to {1}. And for me these two operators, \(f.g\) and \(f.g.f.g\) look quite different, because they produce different mappings, and therefore they cannot be isomorphic to each other.

    Comment Source:Okay, still I feel like my understanding of the closure operator is not complete :) If anybody would be able to shed some light on the following, I would really appreciate. So I introduced two linear posets P and Q, P consisting of 3 elements, Q of 2, and I also defined left adjoint \\(f\\) (blue) and right adjoint \\(g\\) (orange) as below: ![PQPQ](https://raw.githubusercontent.com/ikshv/categories/master/PQPQ.svg?sanitize=true) So \\(f.g\\) maps {1, 2} to {1}, and {3} is mapped to {2}. However, \\(f.g.f.g\\) maps {3} to {1}, while {1, 2} are still mapped to {1}. And for me these two operators, \\(f.g\\) and \\(f.g.f.g\\) look quite different, because they produce different mappings, and therefore they cannot be isomorphic to each other.
  • 7.
    edited April 21

    Igor, I don’t believe \(g\) is the correct right adjoint to \(f\). Let’s label the elements of \(Q\) by \(1.5\) and \(2.5\) to correspond with your picture. Consider the set \(\{a \in P : f(a) \le 1.5\}\), which is \(\{1, 2\}\). We require that \(g(1.5)\) be a least upper bound of this set, so \(g(1.5) = 2\), not \(1\) as in your diagram.

    Comment Source:Igor, I don’t believe \\(g\\) is the correct right adjoint to \\(f\\). Let’s label the elements of \\(Q\\) by \\(1.5\\) and \\(2.5\\) to correspond with your picture. Consider the set \\(\\{a \in P : f(a) \le 1.5\\}\\), which is \\(\\{1, 2\\}\\). We require that \\(g(1.5)\\) be a least upper bound of this set, so \\(g(1.5) = 2\\), not \\(1\\) as in your diagram.
  • 8.

    Thanks @Jonathan, this is a nice catch! To make up this example I followed some assertion that function arrows shouldn't intersect to form adjoints, clearly this condition is not sufficient, and the example is indeed not a Galois connection.

    Comment Source:Thanks @Jonathan, this is a nice catch! To make up this example I followed some assertion that function arrows shouldn't intersect to form adjoints, clearly this condition is not sufficient, and the example is indeed not a Galois connection.
  • 9.
    edited April 22

    @Igor I think the arrows of g are going to the wrong elements of P if g is a right adjoint. The bottom should point to 3 I think. And the set P needs an order which is not clear in your diagram (up or down?)

    Also I think it’d be interesting to try an injective function too.

    Comment Source:@Igor I think the arrows of g are going to the wrong elements of P if g is a right adjoint. The bottom should point to 3 I think. And the set P needs an order which is not clear in your diagram (up or down?) Also I think it’d be interesting to try an injective function too.
  • 10.

    (btw, this has become exercise 1.96 in the latest draft - dated 20 April 2018)

    I still can't see how to exploit the isomorphism of right adjoints here, but I found the Wikipedia page on Galois connections quite useful. Here's what I got:

    1) Putting \(g(q)\) in the place of \(p\) in \(p \leq g(f(p))\) we get \(g(q) \leq g(f(g(q)))\).

    2) Applying the monotone function \(g\) to \(f(g(q))\leq q\) we get \(g(f(g(q)))\leq g(q)\).

    The above must hold for all \(q \in Y\).

    So, if we are working with posets, anti-symmetry of \(\leq\) would then give us \(g \circ f \circ g = g \). Apart from being interesting in its own right, this also gives the idempotence of \(g \circ f \) and \( f \circ g \) - just apply \(f\) on the right to get \(g \circ f \circ g \circ f= g \circ f\) and apply it on the left to get \(f \circ g \circ f \circ g = f \circ g\).

    If we do the same when we are working with preorders (and thus cannot rely on anti-symmetry), we don't quite get idempotence, but only isomorphisms: \(g \circ f \circ g \circ f \cong g \circ f\) and \(f \circ g \circ f \circ g \cong f \circ g\).

    Comment Source:(btw, this has become exercise 1.96 in the latest draft - dated 20 April 2018) I still can't see how to exploit the isomorphism of right adjoints here, but I found the Wikipedia page on [Galois connections](https://en.wikipedia.org/wiki/Galois_connection) quite useful. Here's what I got: 1) Putting \\(g(q)\\) in the place of \\(p\\) in \\(p \leq g(f(p))\\) we get \\(g(q) \leq g(f(g(q)))\\). 2) Applying the monotone function \\(g\\) to \\(f(g(q))\leq q\\) we get \\(g(f(g(q)))\leq g(q)\\). The above must hold for all \\(q \in Y\\). So, if we are working with posets, anti-symmetry of \\(\leq\\) would then give us \\(g \circ f \circ g = g \\). Apart from being interesting in its own right, this also gives the idempotence of \\(g \circ f \\) and \\( f \circ g \\) - just apply \\(f\\) on the right to get \\(g \circ f \circ g \circ f= g \circ f\\) and apply it on the left to get \\(f \circ g \circ f \circ g = f \circ g\\). If we do the same when we are working with preorders (and thus cannot rely on anti-symmetry), we don't quite get idempotence, but only isomorphisms: \\(g \circ f \circ g \circ f \cong g \circ f\\) and \\(f \circ g \circ f \circ g \cong f \circ g\\).
  • 11.
    edited April 26

    We can call property 1 "inflation" and property 2 "idempotence", in analogy with closure operators (which is what \(g \circ f\) would be for posets). Proposition 1.81 gives us inflation for free, so all we must show is that \(g(f(g(f(x)))) \cong g(f(x))\).

    Recall that \(g(f(x))\) is a least upper bound of \(\{z \mid f(z) \le f(x)\}\). Notably, so is \(x\). Therefore, \(f(g(f(x))) \cong f(x)\); by monotonicity, \(g(f(g(f(x)))) \cong g(f(x))\). Thus, \(g \circ f\) is idempotent.

    I am... not entirely certain of this argument. I find it very hard sometimes to keep these sets and the adjoints straight in my head.

    Comment Source:We can call property 1 "inflation" and property 2 "idempotence", in analogy with closure operators (which is what \\(g \circ f\\) would be for posets). Proposition 1.81 gives us inflation for free, so all we must show is that \\(g(f(g(f(x)))) \cong g(f(x))\\). Recall that \\(g(f(x))\\) is a least upper bound of \\(\\{z \mid f(z) \le f(x)\\}\\). Notably, so is \\(x\\). Therefore, \\(f(g(f(x))) \cong f(x)\\); by monotonicity, \\(g(f(g(f(x)))) \cong g(f(x))\\). Thus, \\(g \circ f\\) is idempotent. I am... not entirely certain of this argument. I find it very hard sometimes to keep these sets and the adjoints straight in my head.
  • 12.
    edited April 26

    Igor wrote:

    To make up this example I followed some assertion that function arrows shouldn't intersect to form adjoints, clearly this condition is not sufficient, and the example is indeed not a Galois connection.

    Right, that condition is not sufficient.

    It's very helpful to compute left and right adjoints of monotone mappings using just the definition: \( f : P \rightarrow Q \) is the left adjoint of \( g : Q \rightarrow P \) and \(g\) is the right adjoint of \(f\) iff

    $$ f(p) \le q \iff p \le g(q) $$ for all \(p \in P, q \in Q\). If it seems hard to use this definition to compute adjoints, then it's good to practice! Eventually it becomes easy.

    Comment Source:Igor wrote: > To make up this example I followed some assertion that function arrows shouldn't intersect to form adjoints, clearly this condition is not sufficient, and the example is indeed not a Galois connection. Right, that condition is not sufficient. It's very helpful to compute left and right adjoints of monotone mappings using just the definition: \\( f : P \rightarrow Q \\) is the left adjoint of \\( g : Q \rightarrow P \\) and \\(g\\) is the right adjoint of \\(f\\) iff $$ f(p) \le q \iff p \le g(q) $$ for all \\(p \in P, q \in Q\\). If it seems hard to use this definition to compute adjoints, then it's good to practice! Eventually it becomes easy.
  • 13.

    @JonathanCastello: you wrote

    \(g(f(g(f(x)))) \cong g(f(x))\). Thus, \(g \circ f\) is idempotent

    I think the "Thus" is not justified: "\(g \circ f\) is idempotent" means \(g(f(g(f(x)))) = g(f(x))\) with "=", not just "\( \cong \)". The two are the same in a poset, but not in a preorder.

    Comment Source:@JonathanCastello: you wrote > > \\(g(f(g(f(x)))) \cong g(f(x))\\). Thus, \\(g \circ f\\) is idempotent I think the "Thus" is not justified: "\\(g \circ f\\) is idempotent" means \\(g(f(g(f(x)))) = g(f(x))\\) with "=", not just "\\( \cong \\)". The two are the same in a poset, but not in a preorder.
  • 14.

    Valter, that's why I prefaced with this:

    We can call property 1 "inflation" and property 2 "idempotence", in analogy with closure operators (which is what g∘f would be for posets).

    I merely wanted to call it something other than "property 2".

    Comment Source:Valter, that's why I prefaced with this: > We can call property 1 "inflation" and property 2 "idempotence", in analogy with closure operators (which is what g∘f would be for posets). I merely wanted to call it something other than "property 2".
  • 15.

    @JonathanCastello : oh, I see! Sorry, I had not understood what the 1 and 2 referred to.

    Anyway, since idempotence already has a generally accepted definition (\(f \circ f = f\)), why don’t we call it, say, “isopotence”?

    Comment Source:@JonathanCastello : oh, I see! Sorry, I had not understood what the 1 and 2 referred to. Anyway, since idempotence already has a generally accepted definition (\\(f \circ f = f\\)), why don’t we call it, say, “isopotence”?
Sign In or Register to comment.