Regarding the **Puzzle.** Denote by \$$f^\*\$$ the preimage of \$$f\$$, for any function \$$f\$$. Then surjections \$$f : A \to P\$$ and \$$g : A \to Q\$$ determine the same partition of \$$A\$$ iff for all \$$a \in A\$$ we have \$$f^\*(\\{f(a)\\}) = g^\*(\\{g(a)\\})\$$.

This is almost too literal of an answer, since \$$f(\cdot)\$$ gives exactly the associated part label in \$$P\$$, and \$$f^\*(\\{\cdot\\})\$$ takes this part label to the part it denotes; and if the different label sets identify the same set of parts, then the partitions are the same.

I rather prefer Valter's isomorphism-based answer, even if it might take some more thought to produce a clean proof. There does seem to be something functorial about it: we aren't just mapping between \$$P\$$ and \$$Q\$$, but also between \$$A \to P\$$ and \$$A \to Q\$$, making sure that \$$f \cong g\$$.