Let $A$ be a nonempty set. Prove that if $f$ maps $\>P (A)$ to $A$ then $f$ is not one-to-one.
Related Topics: Pigeonhole Principle
Let $A$ be a nonempty set. Prove that if $f$ maps $\>P (A)$ to $A$ then $f$ is not one-to-one.
Related Topics: Pigeonhole Principle
One can modify the standard proof of Cantor's theorem to show directly that no $f:\mathcal P(A)\to A$ is injective. In effect, given any $f$, consider $ X=\{a\in A\mid \exists Y\,(a=f(Y)\notin Y)\}=\{f(Y)\mid Y\subseteq A\land f(Y)\notin Y\}, $ and set $a_0=f(X)$. If $a_0\notin X$, then $Y=X$ witnesses that $a_0\in X$, contradiction. It follows that $a_0\in X$, and any witness set $Y$ necessarily satisfies $Y\ne X$ and $f(Y)=f(X)$.
This solves the problem, but leads to a new question, namely, whether we can define a set $Y\ne X$ such that $f(X)=f(Y)$. I asked about this on MathOverflow, and Ewan Delanoy gave a nice argument: Curiously, the answer is no in general. More precisely, it is independent of the usual axioms of set theory (including choice) whether such a set $Y$ is always definable.
There is another natural question this suggests, namely, whether we can define from $f$ a pair of sets $B\ne C$ such that $f(B)=f(C)$. The answer to this is yes. This is an argument due to Zermelo: Given any $f:\mathcal P(A)\to A$, there is a unique subset $W$ of $A$ and a unique well-ordering $<$ of $W$ with the following two properties:
Here, $\mbox{pred}_<(w)$ is the set of predecessors of $w$ in $W$, that is, the set of $y\in W$ such that $y
Then $W\ne \mbox{pred}_<(f(W))$ and $f(W)=f(\mbox{pred}_<(f(W)))$. This answer to another question in MathOverflow provides additional details and references.
Cantor's theorem states that there is no surjection from $A$ onto $P(A)$.
Proposition. If $f\colon A\to B$ is an injection, and $A\neq\varnothing$, then there exists a surjection $g\colon B\to A$.
Try to prove this yourself, the proof is hidden by spoiler tags below.
Proof. $A$ is non-empty, therefore there is some $a\in A$. Define $g$ as follows: $g(b)=\begin{cases} f^{-1}(b) & b\in\operatorname{rng}(f)\\ a & b\notin\operatorname{rng}(f)\end{cases}$
Then $g$ is surjective. Given $a\in A$, $f(a)\in B$ and of course $f(a)\in\operatorname{rng}(f)$, therefore $g(f(a))=a$.
Suppose now that there was an injection from $P(A)$ into $A$ then by the proposition above there would be a surjection from $A$ onto $P(A)$ in contradiction to Cantor's theorem. Therefore there is no injection from $P(A)$ into $A$.