# There are no injections from $P(A)$ to $A$.

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

-
Your title is not a great one: it does not describe at all what you are asking! It is a great service to the community to think a bit and come up with a more representative title. remember: it is the first thing people see of your question. –  Mariano Suárez-Alvarez Nov 19 '12 at 5:00
For all sets $A$, including infinite sets, this is a famous theorem of Cantor, proved using diagonalization. But you are probably supposed to do it for finite sets only. Then you need to prove, probably by induction, that $2^n\gt n$. After that, Pigeonhole. –  André Nicolas Nov 19 '12 at 5:01
Let $X=\{x\in A:f(S)\ne x\text{ when }x\in S\}$. Write $y=f(X)$. If $y$ were in $X$ then $f(X)$ would not equal $y$, a contradiction. Thus, $y\not\in X$ and so there is some $Z\subset A$ for which both $y\in Z$ and $f(Z)=y$. Therefore, $f$ is not one-to-one. –  peoplepower Nov 19 '12 at 5:09
I think what you are referring to as Cantor's theorem is the following: Let A be a set. If f maps A to 2^A (set of all subsets of A) then f is not onto. And the problem does not specify for what kind of sets so i think A can be infinite as well. –  UH1 Nov 19 '12 at 5:10
The original version of Cantor's Theorem is that there is no one to one correspondence between $A$ and the powerset of $A$, often called nowadays $2^A$. –  André Nicolas Nov 19 '12 at 5:32

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:

1. For any $w\in W$, $w=f(\mbox{pred}_<(w))$, and
2. $f(W)\in W$.

Here, $\mbox{pred}_<(w)$ is the set of predecessors of $w$ in $W$, that is, the set of $y\in W$ such that $y<w$. (One builds $W$ by recursion, nothing that there is really no leeway: $f(\emptyset)$ is the least element of $W$, $f(\{f(\emptyset)\})$ is the next element of $W$ unless already $f(\{f(\emptyset)\})=f(\emptyset)$, etc.)

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

-