Options

Exercise 83 - Chapter 1

edited April 2018 in Exercises

Show that if \(f: P \to Q\) has a right adjoint \(g\), then it is unique up to isomorphism. That means, for any other right adjoint \(g'\), we have \(g(q)\) isomorphic to \(g'(q)\) for all \(q \in Q\).

Is the same true for left adjoints? That is, if \(h: P \to Q\) has a left adjoint, is it necessarily unique?

Comments

  • 1.

    I don't have the solution for this exercise yet. I hope to hear other people's ideas. It seems to me that to prove isomorphism here we are expected to construct it from f, g, and g', but this is where i get stuck.

    Comment Source:I don't have the solution for this exercise yet. I hope to hear other people's ideas. It seems to me that to prove isomorphism here we are expected to construct it from f, g, and g', but this is where i get stuck.
  • 2.

    Hint (I hope): consider that both g(p) and g'(p) are joins.

    Comment Source:Hint (I hope): consider that both g(p) and g'(p) are joins.
  • 3.

    This is really nice exercise. I think, to not fall into some pitfall here it would be useful to read "Lecture 5 - Chapter 1: Galois Connections" and discussion in this thread. To give some hint on how it can be solved (assuming, that my solution is correct): it may be worth to try compare values of g and another g' on the same argument, use definition of Galois connection and take some advantage of Proposition 1.81

    Comment Source:This is really nice exercise. I think, to not fall into some pitfall here it would be useful to read "Lecture 5 - Chapter 1: Galois Connections" and discussion in this thread. To give some hint on how it can be solved (assuming, that my solution is correct): <spoiler> it may be worth to try compare values of g and another g' on the same argument, use definition of Galois connection and take some advantage of Proposition 1.81 </spoiler>
  • 4.
    edited April 2018

    It's helpful to know that two elements \(x \) and \(y\) of any preorder are isomorphic if \(x \le y\) and \(y \le x\). So, the exercise is asking you to prove two inequalities.

    One way to do this is to use joins, as Dennis Loumas suggests. But this is rather subtle, since joins are only unique when our preorders are posets. I think it's easier to just use the definition of "right adjoint" and "left adjoint".

    It sounds like Artur used this strategy.

    Comment Source:It's helpful to know that two elements \\(x \\) and \\(y\\) of any preorder are **isomorphic** if \\(x \le y\\) and \\(y \le x\\). So, the exercise is asking you to prove two inequalities. One way to do this is to use joins, as Dennis Loumas suggests. But this is rather subtle, since joins are only unique when our preorders are posets. I think it's easier to just use the definition of "right adjoint" and "left adjoint". It sounds like Artur used this strategy.
  • 5.
    edited April 2018

    I think once you understand the goal (which John helpfully pointed out) it becomes much simpler. I was able to solve this with just applications of Proposition 1.81 (and reflexivity). Since the process is nearly unchanged for the case of left adjoint I'm thinking that yes, left adjoints are also unique up to isomorphism.

    Comment Source:I think once you understand the goal (which John helpfully pointed out) it becomes much simpler. I was able to solve this with just applications of Proposition 1.81 (and reflexivity). Since the process is nearly unchanged for the case of left adjoint I'm thinking that yes, left adjoints are also unique up to isomorphism.
  • 6.
    edited August 2018

    Assume there are two right adjoints \( g_0, g_1 \) [the prime is hard for my old eyes].

    Applying the definition of an adjoint pair twice $$ \forall p \in P, q \in Q \; $$ $$ f(p) \le q \iff p \le g_0(q) $$ and $$f(p) \le q \iff p \le g_1(q) $$ do we get ? $$ p \le g_0(q) \iff p \le g_1(q) $$ Not quite, but it gives some intuition for the following.

    figure

    This diagram introduces some helper sets, \( C, D \), and some functions \( m, n, s, t \) the arrows \( g, f, s, t \) being montone-maps and chosen so that the following are true.

    $$ [L1] (n.f)(z) \le m(z) \iff n(z) \le (m.g)(z) $$ $$ [L2] (g.t)(z) \le s(z) \iff t(z) \le (f.s)(z) $$ If you squint a bit you can see that the introduction of the sets and functions induces new adjoint pairs (one for L1 and one for L2) that operate over a preorder of functions.

    $$ f(p) $$ $$ \implies \begin{cases} \text{ reflexivity } f(p) = f_0(p) = f_1(p) \end{cases} $$ $$ f_0(p) \le f_1(p) $$ $$ \equiv \begin{cases} L1 : f=f_0, g=g_0, m=f_1, n=1_B, z=p \\ (n.f)(z) \le m(z) \iff n(z) \le (m.g)(z) \\ (1_B.f_0)(p) \le f_1(p) \iff 1_B(p) \le (f_1.g_0)(p) \\ f_0(p) \le f_1(p) \iff p \le (f_1.g_0)(p) \end{cases} $$ $$ p \le (f_1.g_0)(p) $$ $$ \equiv \begin{cases} L2 : f=f_1, g=g_1, s=g_0, t=1_B, z=p \\ (g.t)(z) \le s(z) \iff t(z) \le (f.s)(z) \\ (g_1.1_B)(p) \le g_0(p) \iff 1_B(p) \le (f_1.g_0)(p) \\ g_1(p) \le g_0(p) \iff p \le (f_1.g_0)(p) \end{cases} $$ $$ g_1(p) \le g_0(p) $$ The choice for \( f_0 \) and \( f_1 \) was arbitrary so changing it results in $$ g_0(p) \le g_1(p) $$ Together the two results gives what we are looking for

    $$ g_1(p) \iff g_0(p) $$ The two right adjoints are isomorphic. \( \blacksquare \)

    Comment Source:Assume there are two right adjoints \\( g_0, g_1 \\) [the prime is hard for my old eyes]. Applying the definition of an adjoint pair twice \[ \forall p \in P, q \in Q \; \] \[ f(p) \le q \iff p \le g_0(q) \] and \[f(p) \le q \iff p \le g_1(q) \] do we get ? \[ p \le g_0(q) \iff p \le g_1(q) \] Not quite, but it gives some intuition for the following. ![figure](https://docs.google.com/drawings/d/e/2PACX-1vTKBk0nQ2emMZzXlonxHiJIH7m7JPT6fHmx8AN6PfPB87HcI9dWILlNqcVRyowxltrGUuu6ws3bGBsg/pub?w=294&h=281) This diagram introduces some helper sets, \\( C, D \\), and some functions \\( m, n, s, t \\) the arrows \\( g, f, s, t \\) being montone-maps and chosen so that the following are true. \[ [L1] (n.f)(z) \le m(z) \iff n(z) \le (m.g)(z) \] \[ [L2] (g.t)(z) \le s(z) \iff t(z) \le (f.s)(z) \] If you squint a bit you can see that the introduction of the sets and functions induces new adjoint pairs (one for L1 and one for L2) that operate over a preorder of functions. $$ f(p) $$ $$ \implies \begin{cases} \text{ reflexivity } f(p) = f_0(p) = f_1(p) \end{cases} $$ $$ f_0(p) \le f_1(p) $$ $$ \equiv \begin{cases} L1 : f=f_0, g=g_0, m=f_1, n=1_B, z=p \\\\ (n.f)(z) \le m(z) \iff n(z) \le (m.g)(z) \\\\ (1_B.f_0)(p) \le f_1(p) \iff 1_B(p) \le (f_1.g_0)(p) \\\\ f_0(p) \le f_1(p) \iff p \le (f_1.g_0)(p) \end{cases} $$ $$ p \le (f_1.g_0)(p) $$ $$ \equiv \begin{cases} L2 : f=f_1, g=g_1, s=g_0, t=1_B, z=p \\\\ (g.t)(z) \le s(z) \iff t(z) \le (f.s)(z) \\\\ (g_1.1_B)(p) \le g_0(p) \iff 1_B(p) \le (f_1.g_0)(p) \\\\ g_1(p) \le g_0(p) \iff p \le (f_1.g_0)(p) \end{cases} $$ $$ g_1(p) \le g_0(p) $$ The choice for \\( f_0 \\) and \\( f_1 \\) was arbitrary so changing it results in $$ g_0(p) \le g_1(p) $$ Together the two results gives what we are looking for $$ g_1(p) \iff g_0(p) $$ The two right adjoints are isomorphic. \\( \blacksquare \\)
  • 7.

    Why not QED? Just take \(p = g_0(q)\) and then \(p = g_1(q)\), no?

    Comment Source:Why not QED? Just take \\(p = g_0(q)\\) and then \\(p = g_1(q)\\), no?
  • 8.
    edited April 2018

    The problem is that if we are working with something like a preorder there is no guarantee that two right adjoints produce equal results. $$ g_0(p) \cong g_1(p) \text{ but } g_0(p) \neq g_1(p) $$ This would never happen in a poset [partial order] or toset [total order] which have the skeletality property. So I think that aligning functions rather than values does the trick.

    Figure

    The brown arrow indicates both \(g_0\) and \(g_1\) .

    Comment Source:The problem is that if we are working with something like a preorder there is no guarantee that two right adjoints produce equal results. $$ g_0(p) \cong g_1(p) \text{ but } g_0(p) \neq g_1(p) $$ This would never happen in a poset [partial order] or toset [total order] which have the skeletality property. So I think that aligning functions rather than values does the trick. ![Figure](https://docs.google.com/drawings/d/e/2PACX-1vTdceEsQYXxMfVdf51DwgqA7MoA-zpvFHnWevaB-hheIU7n6rHDO57QO_8sfiBs-1x1yl5cgbtm-Qe1/pub?w=646&h=353) The brown arrow indicates both \\(g_0\\) and \\(g_1\\) .
  • 9.
    edited April 2018

    But they don’t have to be equal - that’s why I said to first consider the case where p is equal to one of the two (and prove the inequality in one direction), then the case in which p is equal to the other (and prove the inequality in the other direction).

    Edit: I understand now that my use of "equal to \(p\)" was too informal and bound to lead to misinterpretation. What I meant was the following: you have already shown that for all \(x\) and \(y\), \( x \leq g_0(y) \iff x \leq g_1(y) \); this must be true also when we choose \(x\) to be \(g_0(q)\) and \(y\) to be \(q\), so \( g_0(q) \leq g_0(q) \iff g_0(q) \leq g_1(q) \); since \( g_0(q) \leq g_0(q)\) is necessarily true, then \( g_0(q) \leq g_1(q) \). The opposite inequality is established in the same way by choosing \(x\) to be \(g_1(q)\).

    Comment Source:But they don’t have to be equal - that’s why I said to first consider the case where p is equal to one of the two (and prove the inequality in one direction), then the case in which p is equal to the other (and prove the inequality in the other direction). Edit: I understand now that my use of "equal to \\(p\\)" was too informal and bound to lead to misinterpretation. What I meant was the following: you have already shown that for all \\(x\\) and \\(y\\), \\( x \leq g_0(y) \iff x \leq g_1(y) \\); this must be true also when we choose \\(x\\) to be \\(g_0(q)\\) and \\(y\\) to be \\(q\\), so \\( g_0(q) \leq g_0(q) \iff g_0(q) \leq g_1(q) \\); since \\( g_0(q) \leq g_0(q)\\) is necessarily true, then \\( g_0(q) \leq g_1(q) \\). The opposite inequality is established in the same way by choosing \\(x\\) to be \\(g_1(q)\\).
  • 10.
    edited April 2018

    @ValterSorana Let me see if I follow your proof.

    Starting with left adjoint \( f : A \rightarrow B \) . Given two right adjoints \( g_0 : B \rightarrow A \) and \( g_1 : B \rightarrow A \) which means. $$ f(p) \le q \iff p \le g_0(q) \tag{D0} $$ $$ f(p) \le q \iff p \le g_1(q) \tag{D1} $$ $$ f(g_0(q)) \le q \tag{L0a} $$ $$ p \le g_0(f(p)) \tag{L0b} $$ $$ f(g_1(q)) \le q \tag{L1a} $$ $$ p \le g_1(f(p)) \tag{L1b} $$ Select an arbitrary \(x,z \in A\) such that $$ x \le z \tag{A2} $$ $$ z \le g_0(f(z)) \iff z \le g_1(f(z)) \tag{ E2 : L0b and L1b Do I need to prove this? } $$ $$ \text {define } y = f(z) $$ $$ x \le z \le g_0(y) \iff x \le z \le g_1(y) \tag{ E3: A2 and E2 } $$ $$ x \le g_0(y) \iff x \le g_1(y) \tag{ E4} $$ $$ \text{ set } x = g_0(y) $$ $$ g_0(y) \le g_0(y) \iff g_0(y) \le g_1(y) \tag{ E4 } $$ $$ g_0(y) \le g_1(y) \tag{ E5 } $$ $$ \text{ set } x = g_1(y) $$ $$ g_1(y) \le g_0(y) \iff g_1(y) \le g_1(y) \tag{ E4 } $$ $$ g_1(y) \le g_0(y) \tag{ E6 } $$ $$ g_0(y) \iff g_1(y) \tag{ E5 & E6 } $$ I think you are right QED.

    [Do you know how to label latex equations?]

    Comment Source:@ValterSorana Let me see if I follow your proof. Starting with left adjoint \\( f : A \rightarrow B \\) . Given two right adjoints \\( g_0 : B \rightarrow A \\) and \\( g_1 : B \rightarrow A \\) which means. $$ f(p) \le q \iff p \le g_0(q) \tag{D0} $$ $$ f(p) \le q \iff p \le g_1(q) \tag{D1} $$ $$ f(g_0(q)) \le q \tag{L0a} $$ $$ p \le g_0(f(p)) \tag{L0b} $$ $$ f(g_1(q)) \le q \tag{L1a} $$ $$ p \le g_1(f(p)) \tag{L1b} $$ Select an arbitrary \\(x,z \in A\\) such that $$ x \le z \tag{A2} $$ $$ z \le g_0(f(z)) \iff z \le g_1(f(z)) \tag{ E2 : L0b and L1b Do I need to prove this? } $$ $$ \text {define } y = f(z) $$ $$ x \le z \le g_0(y) \iff x \le z \le g_1(y) \tag{ E3: A2 and E2 } $$ $$ x \le g_0(y) \iff x \le g_1(y) \tag{ E4} $$ $$ \text{ set } x = g_0(y) $$ $$ g_0(y) \le g_0(y) \iff g_0(y) \le g_1(y) \tag{ E4 } $$ $$ g_0(y) \le g_1(y) \tag{ E5 } $$ $$ \text{ set } x = g_1(y) $$ $$ g_1(y) \le g_0(y) \iff g_1(y) \le g_1(y) \tag{ E4 } $$ $$ g_1(y) \le g_0(y) \tag{ E6 } $$ $$ g_0(y) \iff g_1(y) \tag{ E5 & E6 } $$ I think you are right QED. [Do you know how to label latex equations?]
  • 11.

    I don't know how to label LaTeX equations in this particular installation of MathJax. It's annoying! In some, $$ $$ produces unlabeled displayed equations while \[ \] produces sequentially numbered displayed equations. But not here.

    Comment Source:I don't know how to label LaTeX equations in this particular installation of MathJax. It's annoying! In some, `$$ $$` produces unlabeled displayed equations while `\[ \]` produces sequentially numbered displayed equations. But not here.
  • 12.

    @FredrickEisele I am afraid I got lost in your proof now! :-? Btw, I made a couple of changes to my previous comment (mostly changing some p's into q's), so hopefully it is clearer now.

    Comment Source:@FredrickEisele I am afraid I got lost in your proof now! :-? Btw, I made a couple of changes to my previous comment (mostly changing some p's into q's), so hopefully it is clearer now.
  • 13.
    edited April 2018

    @ValterSorana Much of what I did in the proof was to get to E4: \(x \le g_0(y) \iff x \le g_1(y) \) [which is where you start]. From there out it is just detailing what you said. D0, D1, L0a, L0b, L1a, & L1b are just the theorems for adjunctions.

    @JohnBaez The \tag{} seems to do the trick.

    Comment Source:@ValterSorana Much of what I did in the proof was to get to E4: \\(x \le g_0(y) \iff x \le g_1(y) \\) [which is where you start]. From there out it is just detailing what you said. D0, D1, L0a, L0b, L1a, & L1b are just the theorems for adjunctions. @JohnBaez The \\tag{} seems to do the trick.
  • 14.

    Thanks for telling me about \tag{}.

    Comment Source:Thanks for telling me about \tag{}.
  • 15.
    edited May 2018

    @FrederickEisele, I'm having trouble following your proof. At line E4, you've proved \(x \leq g_0(x) \Longleftrightarrow x \leq g_1(y)\) for arbitrary \(x \leq z\), but then you choose \(x = g_0(y)\). How do we know that \(g_0(y) \leq z\)?

    Comment Source:@FrederickEisele, I'm having trouble following your proof. At line E4, you've proved \\(x \leq g_0(x) \Longleftrightarrow x \leq g_1(y)\\) for arbitrary \\(x \leq z\\), but then you choose \\(x = g_0(y)\\). How do we know that \\(g_0(y) \leq z\\)?
  • 16.

    @RifASaurous We are picking a specific \( x \) from among all possible, namely the one where \( x = z = g_0(y) \).

    Comment Source:@RifASaurous We are picking a specific \\( x \\) from among all possible, namely the one where \\( x = z = g_0(y) \\).
Sign In or Register to comment.