-2
$\begingroup$

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

  • 0
    It is unlikely that the problem is hinting at using the pigeonhole principle if it is meant for infinite sets, as well...2012-11-27

2 Answers 2

4

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

2

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