3

I've just saw the Cantor's theorem some days ago, but I really can't get my head around the proof. I read everywhere the same thing on Wikipedia, YouTube, and in class. The only thing I know that it is to be proved by contradiction and that we are proving that it's not surjective. I tried to do an example by like creating a set $A=\{1,2\}$ and try see what is going on with the set, but I just can't understand.

The proof:Proof

I would like a stage by stage going through the proof with my set so that I can see what is really going on. Explanations are very welcome. Thanks in advance.

Xander Henderson
  • 29,772
Valentin
  • 147
  • If you use $A = { 0, 1}$ instead, the picture at the top on Wikipedia demonstrates the idea. If something is unclear there you can ask a more specific question and we can hopefully help set things straight. – Alex Oct 15 '18 at 21:48
  • 1
    @Alex Cantor's theorem asserts that the powerset of a set is of larger cardinality than the set itself. What you have linked to is Cantor's diagonalization argument, which is different. You may want to refer to this page, instead. – Xander Henderson Oct 15 '18 at 21:51
  • I have saw the thing that they do in the proof is defining a set B={x in A :x not in f(x)} this is blocking me because I really don't know anything about f(x) or why would you want x which are not in f(x). – Valentin Oct 15 '18 at 21:53
  • 1
    Indeed, you are not supposed to "know anything" about $f$, besides the fact that is maps $A$ to its powerset. The proof works by showing that for every $A$, no matter how you choose $f$, a set is going to miss from its range. It gives you the recipe to build such missing set that works for any $f$. You can read the details of the proof in Noah's answer. – Fabio Somenzi Oct 15 '18 at 22:23

2 Answers2

4

Cantor's theorem says, "Any map from $A$ to $2^A$ is non-surjective;" that is, for any $f:A\rightarrow\mathcal{P}(A)$, there is some $X\subseteq A$ such that $X\not\in ran(f)$. Specifically, we can take $X=\{a\in A: a\not\in f(a)\}$.

Before I explain why this works, let's see a couple examples to convince ourselves that it does work (or at least has a chance of working). For simplicity, let's look at $A=\{1,2\}$. Then here are a few examples of $f$s and the corresponding $X$s they generate:

  • $f$ sends $1$ to $\{1\}$ and $2$ to $\{2\}$. Then $X$ is $\emptyset$ (we always have $a\in f(a)$). And $X$ is not in the range of $f$: the only things $f$ "spits out" are $\{1\}$ and $\{2\}$, and neither of these is the empty set.

  • $f$ sends $1$ to $\{2\}$ and $2$ to $\{1\}$. Then $X=\{1,2\}$, and again $X\not\in ran(f)$.

  • $f$ sends $1$ to $\emptyset$ and $2$ to $\{1,2\}$. Then $X=\{1\}$: we have $1\not\in \emptyset=f(1)$, so $1\in X$, and $2\in\{1,2\}=f(2)$, so $2\not\in X$. And as expected, this $X$ is not in the range of this $f$ either.

The point is that no matter what $f:A\rightarrow\mathcal{P}(A)$ you pick, I'll always be able to find some subset of $A$ not in the range of $f$ - namely, the $X$ defined above.

So why does this work?

Well, to show $X\not\in ran(f)$ we need to show that, for each $Y\in ran(f)$, $X\not=Y$.

But this can be rephrased as: for every $a\in A$, $X\not=f(a)$.

Now think about how $X$ is defined. For any $a\in A$, we have $a\in X\iff a\not\in f(a)$. But this means that $X\not=f(a)$: two sets are equal only if they have the same elements, and $X$ and $f(a)$ disagree about $a$.

Noah Schweber
  • 245,398
  • Excuse me, I am a bit beginner, how would you define f(a), and is that function and a set? Because you have said there :a∉f(a). – Valentin Oct 15 '18 at 22:17
  • 2
    @BurLeXyOOnuTz Cantor's theorem says no matter what $f$ is, it won't be a surjection from $A$ to $\mathcal{P}(A)$; and in particular, one of the sets it won't output will be ${a: a\not\in f(a)}$. The set $X$ depends on the function $f$; the point is that regardless of what $f$ is, we'll always have $X\not\in ran(f)$. Do you understand the specific examples I've given (e.g. why, if $f$ sends $1$ to ${1}$ and $2$ to ${2}$, then $X=\emptyset$, and that this $X$ is not in the range of this $f$)? – Noah Schweber Oct 15 '18 at 22:33
  • 1
    @BurLeXyOOnuTz In particular, note that $f$ is a function from elements of $A$ to subsets of $A$. That may feel a bit weird, but it's fine: there's no reason why functions can't "change types" like that. – Noah Schweber Oct 15 '18 at 22:34
  • Is "a∉f(a)" meaning that there doesn't exist an element a for the image f(a)? – Valentin Oct 16 '18 at 18:16
  • @BurLeXyOOnuTz No: $f(a)$ is a set, and we're saying $a$ isn't in it. E.g. in the very first example I gave, we had $f(1)={1}$ - that is, the function $f$ takes in the number $1$ and spits out the set ${1}$. Clearly $1\in{1}$; that is, $1\in f(1)$. It may feel odd to consider functions which send numbers (or rather, elements of $A$) to sets (or rather, subsets of $A$), but they're perfectly fine objects, and they're the sort of thing Cantor's theorem is about: (cont'd) – Noah Schweber Oct 16 '18 at 18:49
  • we're trying to prove something about all functions which take in elements of $A$ and spit out subsets of $A$ (namely, that none of them are surjective). – Noah Schweber Oct 16 '18 at 18:49
  • excuse me, why does "X∉ran(f)" because I thought X has elements of A and A has elements of P(A), so wouldn't it be X in ran(f)? – Valentin Oct 16 '18 at 20:33
  • 1
    @BurLeXyOOnuTz I'm not sure what you're trying to say. $X$ is a subset of $A$. The function $f$ outputs some, but possibly not all, subsets of $A$. $X$ is not one of the subsets which $f$ outputs. That is, $X\not\in ran(f)$, and so $f$ is not surjective. – Noah Schweber Oct 16 '18 at 20:35
  • Look at the concrete examples I gave. Do you understand in the first example - where $f(1)={1}$ and $f(2)={2}$ - why: (i) $X=\emptyset$, (ii) $ran(f)={{1}, {2}}$, and (ii) $X\not\in ran(f)$? If not, which part don't you understand? – Noah Schweber Oct 16 '18 at 20:36
  • I don't really get what is the X role in that proof. I cannot get my head around like why would you need to compare values from the A with ran( f(a)) to show that it's not a surjective map. In your first example you compared X with range f(a), what does that have to do with surjectivity? – Valentin Oct 16 '18 at 21:15
  • @BurLeXyOOnuTz I didn't compare $X$ with $ran(f)$ (not "$ran(f(a))$" by the way); I said - do you understand why this is true? - that $X\not\in ran(f)$. That's exactly what non-surjectivity is: there's something in the codomain (in this case, $\mathcal{P}(A)$) which isn't in the range. Namely, $X$. Again: in the first example, does it make sense that $X$ (which is $\emptyset$) is not an element of $ran(f)$ (which is ${{1},{\2}}$) and hence $f$ is not surjective? – Noah Schweber Oct 16 '18 at 21:20
  • That is, our goal is to show that $f:A\rightarrow\mathcal{P}(A)$ isn't surjective. This means exactly that we want to find some $X\in\mathcal{P}(A)$ which is not in the range of $f$ (that's just what non-surjectivity means). So there will be exactly two steps: (i) define some $X\in\mathcal{P}(A)$ and (ii) show that this $X$ isn't in the range of $f$. – Noah Schweber Oct 16 '18 at 21:21
  • Alright so you first selected from the domain by defining B where "a∉f(a)" which means that you wanted something else other than the images or the range. Then you took that B and compared it with our ran(f) and you showed that an element of the codomain isn't image of anything in A. Therefore not surjective. – Valentin Oct 16 '18 at 21:29
  • I think I understand it. The main thing is to show that there is an other element in the codomain which isn't an image of anything that is how the set B helped us. Is that right? – Valentin Oct 16 '18 at 21:32
  • @BurLeXyOOnuTz Yup. Incidentally, you can think of it as a game. I claim: "No function from $A$ to $\mathcal{P}(A)$ is surjective." You say: "Prove it. Show me that this function $f$ isn't surjective!" I say: "OK, let $X$ be [this weird set]. I claim $X\not\in ran(f)$." If I can do that last bit, then I've shown that $f$ isn't surjective. The fact that I can win no matter what $f$ you pick means that no $f$ is surjective, that is, the claim I made was true. – Noah Schweber Oct 16 '18 at 21:35
  • Thank you very much. I really appreciate your help. – Valentin Oct 16 '18 at 21:37
  • @NoahSchweber Perfect explanation. Thanks for this great answer – Srijan Oct 06 '23 at 03:33
1

Power set is always strictly larger than the set:

Thm (Cantor): Let ${ A }$ be a set. Then ${ \vert A \vert < \vert \mathcal{P}(A) \vert }.$

Pf: The injection ${ A \to \mathcal{P}(A) , a \mapsto \lbrace a \rbrace}$ gives ${ \vert A \vert \leq \vert \mathcal{P}(A) \vert }.$
Can ${ \vert A \vert = \vert \mathcal{P}(A) \vert }$ ? Say there is a bijection ${ f : A \to \mathcal{P}(A) }.$ We can write ${ f(a) = S _{a} (\subseteq A) },$ to emphasise mentally the images are sets. Considering ${ \lbrace a \in A : a \notin S _a \rbrace },$ there is a unique ${ b \in A }$ such that ${ S _b = \lbrace a \in A : a \notin S _a \rbrace }.$ Does ${ b \in S _b }$ ? No, gives a contradiction. Does ${ b \notin S _b }$ ? No, gives a contradiction. Hence such an ${ f }$ cannot exist.

So we have ${ \vert \mathbb{R} \vert < \vert \mathcal{P}(\mathbb{R}) \vert < \vert \mathcal{P}(\mathcal{P}(\mathbb{R})) \vert < \ldots }$ as an example.

Venkata Karthik Bandaru
  • 964