Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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. –  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

2 Answers 2

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.