Options

Exercise 91 - Chapter 1

Suppose that if \( f \) is left adjoint to \( g \) . Use Proposition 1.81 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.81. 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 1.70 [Equation 1.5]. 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.
Sign In or Register to comment.