-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