Another typo, I think: Where John wrote

> So by our Theorem, we see that \\(f^* : P(Y) \to P(X)\\) _cannot_ be a left adjoint.

I think he meant \\(f^\ast: \mathcal{E}(Y)\to \mathcal{E}(X)\\).

**Puzzle 44**: To check that \\(f_!\\) is the left adjoint of \\(f^\ast\\), we need to show that for any two partitions \\(P\\) of \\(X\\) and \\(Q\\) of \\(Y\\), the two inequalities \\(P \leq f^\ast(Q)\\) and \\(f_!(P) \leq Q\\) are equivalent.

In the language of equivalence relations, let's suppose we have equivalence relations \\(\sim_P\\) on \\(X\\) and \\(\sim_Q\\) on \\(Y\\), and that \\(x_1\sim_P x_2\implies x_1\sim_{f^\ast(Q)} x_2\\). The latter is equivalent to saying that \\(f(x_1)\sim_Q f(x_2)\\), so the assumption \\(P \leq f^\ast(Q)\\) is equivalent to

\\[x_1\sim_P x_2 \implies f(x_1)\sim_Q f(x_2).\\]

On the other hand, let's consider the inequality \\(f_!(P) \leq Q\\). Since \\(\sim_{f_!(P)}\\) is the smallest equivalence relation containing the relation \\(\sim\\) defined by "\\(y_1\sim y_2\\) iff \\(x_1\sim_P x_2\\) for some \\(x_1\\) and \\(x_2\\) with \\(f(x_1)=y_1\\) and \\(f(x_2)=y_2\\)", and since \\(\sim_Q\\) is an equivalence relation, the inequality \\(f_!(P)\leq Q\\) says exactly "For all \\(y_1\\) and \\(y_2\\), if \\(x_1\sim_P x_2\\) for some \\(x_1\\) and \\(x_2\\) with \\(f(x_1)=y_1\\) and \\(f(x_2)=y_2\\), then \\(y_1\sim_Q y_2\\)." Or in other words, "For all \\(x_1\\) and \\(x_2\\), if \\(x_1\sim_P x_2\\) then \\(f(x_1)\sim_Q f(x_2)\\)." But this is exactly the statement

\\[x_1\sim_P x_2 \implies f(x_1)\sim_Q f(x_2)\\]

we said was equivalent to \\(P\leq f^\ast(Q)\\). Therefore \\(P\leq f^\ast(Q) \iff f_!(P)\leq Q\\).

> So by our Theorem, we see that \\(f^* : P(Y) \to P(X)\\) _cannot_ be a left adjoint.

I think he meant \\(f^\ast: \mathcal{E}(Y)\to \mathcal{E}(X)\\).

**Puzzle 44**: To check that \\(f_!\\) is the left adjoint of \\(f^\ast\\), we need to show that for any two partitions \\(P\\) of \\(X\\) and \\(Q\\) of \\(Y\\), the two inequalities \\(P \leq f^\ast(Q)\\) and \\(f_!(P) \leq Q\\) are equivalent.

In the language of equivalence relations, let's suppose we have equivalence relations \\(\sim_P\\) on \\(X\\) and \\(\sim_Q\\) on \\(Y\\), and that \\(x_1\sim_P x_2\implies x_1\sim_{f^\ast(Q)} x_2\\). The latter is equivalent to saying that \\(f(x_1)\sim_Q f(x_2)\\), so the assumption \\(P \leq f^\ast(Q)\\) is equivalent to

\\[x_1\sim_P x_2 \implies f(x_1)\sim_Q f(x_2).\\]

On the other hand, let's consider the inequality \\(f_!(P) \leq Q\\). Since \\(\sim_{f_!(P)}\\) is the smallest equivalence relation containing the relation \\(\sim\\) defined by "\\(y_1\sim y_2\\) iff \\(x_1\sim_P x_2\\) for some \\(x_1\\) and \\(x_2\\) with \\(f(x_1)=y_1\\) and \\(f(x_2)=y_2\\)", and since \\(\sim_Q\\) is an equivalence relation, the inequality \\(f_!(P)\leq Q\\) says exactly "For all \\(y_1\\) and \\(y_2\\), if \\(x_1\sim_P x_2\\) for some \\(x_1\\) and \\(x_2\\) with \\(f(x_1)=y_1\\) and \\(f(x_2)=y_2\\), then \\(y_1\sim_Q y_2\\)." Or in other words, "For all \\(x_1\\) and \\(x_2\\), if \\(x_1\sim_P x_2\\) then \\(f(x_1)\sim_Q f(x_2)\\)." But this is exactly the statement

\\[x_1\sim_P x_2 \implies f(x_1)\sim_Q f(x_2)\\]

we said was equivalent to \\(P\leq f^\ast(Q)\\). Therefore \\(P\leq f^\ast(Q) \iff f_!(P)\leq Q\\).