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