Exercise 83 - Chapter 1

Thrina Burana

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?

Thrina Burana

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.

Dennis Lomas

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

Artur Poplawski

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

John Baez

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.

Daniel Wang

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.

Fredrick Eisele

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.

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

Valter Sorana

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

Fredrick Eisele

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.

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

Valter Sorana

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

Fredrick Eisele

@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?]

John Baez

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.

Valter Sorana

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

Fredrick Eisele

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

John Baez

Thanks for telling me about \tag{}.

Rif A. Saurous

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

Fredrick Eisele

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