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