1
$\begingroup$

OK, I have read two different proofs of the following theorem both of which I can't quite wrap my mind around. So, I tried to write a proof that makes sense to me, and hopefully to others with the same difficulty. Please let me know if this is an accurate proof an how I might fix it. Sorry, about the length I have been thinking about this proof all day! Thanks for your time.

Cantor's Theorem: $|A|< |\mathscr{P}(A)|$. Or, in particular there exists no surjection from $A$ onto $\mathscr{P}(A)$.

First, we show that $|A|\leq |\mathscr{P}(A)|$ by showing that there exsists a injective function from $A$ to $\mathscr{P}(A)$. Let, $f:A\to \mathscr{P}(A)$ be defined by the function $a\mapsto \{a\} $ that is that every element $a \in A$ is mapped to the singleton set in $\mathscr{P}(A)$ containing the element $a$. Thus we have found an injection from $A$ to $\mathscr{P}(A)$ and therefore $|A|\leq |\mathscr{P}(A)|$.

Now, in order to show that $|A|<|\mathscr{P}(A)|$ we must show that there does not exist a surjective function from $A$ to $\mathscr{P}(A)$. Let, us suppose that there does exist a surjective function $f:A\to \mathscr{P}(A)$ then it is implied (by the nature of this mapping) that $(\forall a\in A)(f(a) \subseteq A)$. Now, let us define a set $B:=\{x\in A : x\notin f(x)\}$. We want to show two things: first we want to show that $B\subseteq A$, and secondly we want that $B \not\subseteq\mathscr{P}(A)$. If the set $B=\emptyset$ then $B\subseteq A$ since the empty set is a subset of all sets. If $B\not =\emptyset$ then $B\subseteq A$ by the definition of $B$. Consequently, there must be an element $x'\in A$ such that $f(x')=B$ or otherwise $B\not\subseteq \mathscr{P}(A)$. In other words there must exist an an element $x'$ in $A$ such that the image of $x'$ under $f$, $f(x')$ , belongs to $B$ in order for $B \subseteq \mathscr{P}(A)$, or otherwise the opposite is true. Since we have already determined that $B \subseteq A$ then it must be true that $x'\in B$ or that $x \notin B$. If $x'\in B$ then $x' \notin f(x')$ which means that $x' \notin B$ since $f(x')=B$. Likewise, if $x' \notin B$ then $x' \in f(x) = B$. So, either way we arrive at a contradiction, and therefore it must be true that $B \not\subseteq \mathscr{P}(A)$. Hence, $f$ is not surjetive.

In conclusion, we showed that $|A|\leq |\mathscr{P}(A)|$, and since the function $f$ was arbitrary mapping it must be true that there does not exist a surjective mapping from $A$ to $\mathscr{P}(A)$. And therefore we have that $|A|< |\mathscr{P}(A)|$ is always true.

I am not sure, if there are any flaws in my logic please let me know. I would like to edit the post so that a detailed proof will be available for other who have struggled with this proof.

$\endgroup$
2
$\begingroup$

The argument is basically just a slightly more detailed than usual version of the standard proof, but you’ve made one consistent error throughout, writing $\nsubseteq\wp(A)$ when you actually mean $\notin\operatorname{ran}f$.

We want to show two things: first we want to show that $B\subseteq A$, and secondly we want that $B\nsubseteq\wp(A)$.

No, we want to show that $B\subseteq A$ and that $B\notin\operatorname{ran}f$, thereby showing that the function $f$ is not a surjection. There’s no need to split the proof that $B\subseteq A$ into two cases: you defined $B$ to be $\{x\in A:x\notin f(x)\}$, which automatically makes $B$ a subset of $A$.

Consequently, there must be an element $x'\in A$ such that $f(x')=B$ or otherwise $B\nsubseteq\wp(A)$.

The last bit should be $B\notin\operatorname{ran}f$. We know that $B\subseteq A$ and hence that $B\in\wp(A)$, and we’re assuming that $f$ is a surjection, so that everything in $\wp(A)$ is in the range of $f$. And since $B$ is not in general a collection of subsets of $A$, it cannot in general be a subset of $\wp(A)$; it’s an element of $\wp(A)$. (There are special circumstances in which $B$ might turn out, more or less by accident, to be a subset of $A$).

In other words there must exist an an element $x'$ in $A$ such that the image of $x'$ under $f$, $f(x')$, belongs to $B$ in order for $B\subseteq\wp(A)$, or otherwise the opposite is true.

Again, we know that $B\subseteq A$, i.e., that $B\in\wp(A)$; $B$ is certainly not in general a subset of $\wp(A)$. What you should be saying here is:

In other words, there must be an element $x'$ of $A$ such that the image of $x'$ under $f$, $f(x')$, is $B$ in order for $B\in\operatorname{ran}f$ to be true; otherwise, the opposite is true, and $f$ is not a surjection.

The next sentence has an unnecessary bit whose presence might actually confuse some, if they thought that it actually was relevant:

Since we have already determined that $B\subseteq A$ then it must be true that $x'\in B$ or that $x\notin B$.

The hypothesis is unnecessary: no matter what $x'$ and $B$ are, exactly one of the statements $x'in B$ and $x'\notin B$ is true.

So, either way we arrive at a contradiction, and therefore it must be true that $B\nsubseteq\wp(A)$.

This is the same mistake that you’ve made in several other places: it should read ‘and therefore it must be true that $B\notin\operatorname{ran}f$’.

$\endgroup$
  • $\begingroup$ If $A$ is transitive then certainly $B\subseteq\mathcal P(A)$. $\endgroup$ – Asaf Karagila Jul 6 '13 at 6:53
  • $\begingroup$ @Asaf: Okay, I probably shouldn’t indulge in white lies even for pædagogical reasons. Fixed. $\endgroup$ – Brian M. Scott Jul 6 '13 at 7:01
  • $\begingroup$ @BrianM.Scott Thanks for this! I rewrote the proof below, and it finally make sense. Could you suggest an accessible, yet thorough, Set Theory book that would go well with a reading in Elementary Analysis, and Elementary Abstract Algebra? $\endgroup$ – JimmyJackson Jul 6 '13 at 8:10
3
$\begingroup$

One mistake that wasn't covered by Brian's extensive answer, is the formulation of the theorem. It is a common mistake, especially by beginners.

Cantor's theorem tells us there is no surjection from a set onto its power set. In particular there is no bijection.

This is a delicate issue, but under some (advanced) set theoretical assumptions it is possible to have an injection from $A$ to $B$, a surjection from $A$ onto $B$, and yet no bijection between the two sets. But even in that framework Cantor's theorem is provable and true.

$\endgroup$
  • $\begingroup$ Thanks for this extra information as well, My Real Analysis assumes that I know a lot of things that I don't really know. Do you know any accessible, but rigorous books on set theory that might be useful before diving into Real Analysis. Or should I just keep learning as I go asking questions on here? $\endgroup$ – JimmyJackson Jul 6 '13 at 7:17
  • $\begingroup$ Well, you should learn the things at the same time. It helps, I believe. Here are two relevant threads: math.stackexchange.com/questions/11177/… and math.stackexchange.com/questions/264252/the-way-into-set-theory $\endgroup$ – Asaf Karagila Jul 6 '13 at 8:17
  • $\begingroup$ Thanks, I will check these out tomorrow. Take care. $\endgroup$ – JimmyJackson Jul 6 '13 at 8:23
0
$\begingroup$

Cantor's Theorem: $|A|< |\mathscr{P}(A)|$. In Particular there exists no surjection from $A$ onto $\mathscr{P}(A)$.

First, we show that $|A|\leq |\mathscr{P}(A)|$ by showing that there exsists a injective function from $A$ to $\mathscr{P}(A)$. Let, $f:A\to \mathscr{P}(A)$ be defined by the function $a\mapsto \{a\} $ that is that every element $a \in A$ is mapped to the singleton set in $\mathscr{P}(A)$ containing the element $a$. Thus we have found an injections from $A$ to $\mathscr{P}(A)$ and therefore $|A|\leq |\mathscr{P}(A)|$.

Now in order to show that $|A|<|\mathscr{P}(A)|$ we must show that there does not exist a surjective function from $A$ to $\mathscr{P}(A)$. Let, us suppose that there does exist a surjective function $f:A\to \mathscr{P}(A)$. Now, let us define a set $B:=\{x\in A : x\notin f(x)\}$. We want to show two things: first we want to show that $B\subseteq A$, and secondly we want that $B \notin \text{ran} f$. We know that $ B \subseteq A$ by the definition of $B$. Consequently, there must be an element $x'\in A$ such that $f(x')=B$ or otherwise $B\notin \text{ran} f$. In other words there must exist an an element $x'$ in $A$ such that the image of $x'$ under $f$, $f(x')$ , is equal to $B$ in order for $B \in \text{ran} f$ to be true; otherwise, the opposite is true, $B\notin \text{ran} f$. Now, for any element in $A$ it must be true that $x'\in B$ or that $x' \notin B$; if $x'\in B$ then $x' \notin f(x')$ which means that $x' \notin B$ since $f(x')=B$. Likewise, if $x' \notin B$ then $x' \in f(x) = B$. So, either way we arrive at a contradiction, and therefore it must be true that $B \notin \text{ran} f$. Hence, $f$ is not surjetive.

In conclusion, we showed that $|A|\leq |\mathscr{P}(A)|$, and since the function $f$ was arbitrary mapping it must be true that there does not exist a surjective mapping from $A$ to $\mathscr{P}(A)$. And therefore we have that $|A|< |\mathscr{P}(A)|$ is always true.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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