-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

  • 1
    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.2012-11-19
  • 0
    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.2012-11-19
  • 0
    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.2012-11-19
  • 0
    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.2012-11-19
  • 0
    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$.2012-11-19
  • 0
    @UH1 If you know the theorem that $A$ cant map onto $2^A$, then since we already know we have an injection from $A$ into $2^A$, if we had an injection from $2^A$ into $A$, then Cantor-Schroder-Bernstein would give an onto map from $A$ to $2^A$ a contradiction!2012-11-19
  • 0
    The Cantor-Schroder-Bernstein theorem is not really necessary for this. If you know an injective function $f: A\rightarrow B$ it's easy to get a surjective function $g: B \rightarrow A$.2012-11-19
  • 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

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