Prove that R and P(R) does not have the same cardinality.

Question

How can I show such a thing in an elegant, valid way? I know it shouldn't be hard. Well it does have to be plausible and mathematically logic, but I guess I am not expected to rediscover the great, massive proof founded by Cantor. If I am to use what he says, what's the point then? I mean, how can I prove this elegantly as an "Introduction to Set Theory" mere student? I'd appreciate your help.

Answer 1

The basic idea of the proof of Cantor's Theorem is, I think, accessible even to you. Here it is:

We say two sets $A$ and $B$ have the same cardinality if there is at least one bijection $f : A \to B$. That is, $f$ has to be a one-to-one and onto map from $A$ to $B$.

So, to prove any set $R$ and its powerset, $\mathcal{P}(R)$, do not have the same cardinality, we just need to prove that there is no bijection between $R$ and $\mathcal{P}(R)$. But since bijections are one-to-one and onto, one of these conditions must fail for every map from $R$ to $\mathcal{P}(R)$ (otherwise, if there is some map that exhibits both of these, that would be a bijection).

But the map $h : R \to \mathcal{P}(R)$ sending $a \in R$ to $\{a \} \in \mathcal{P}(R)$ is an injection...

So that means an injection exists, and maybe more than one does. And some of those injections might also be surjections...in which case, we would have a bijection between $R$ and $\mathcal{P}(R)$. So how can we check that all of these injections aren't surjections? Well, Cantor had the idea that no map from $R$ to $\mathcal{P}(R)$, whether injective or not, is surjective, and that's what will be shown below.

---

Okay, so let $f : R \to \mathcal{P}(R)$ be any map. We want to prove $f$ cannot be surjective. That means we should be able to find an element $z \in \mathcal{P}(R)$ such that there is no $a \in R$ with $f(a) = z$.

Hmm...maybe we can construct this element $z$. What does the map $f$ do on a basic level? It sends an element in $R$ to an element in $\mathcal{P}(R)$, i.e., an element in $R$ to a subset of $R$.

Okay, well, maybe we can observe where each element in $R$ is being sent to under $f$...and maybe we can include that element in the set we are constructing if it isn't already in the subset it is being mapped to, but if it is in the subset it is being mapped to, we can leave it out. That way, the subset we are constructing will be different from every subset being hit by $f$...

That is, let $z = \{ a \in R \mid a \not \in f(a) \}$. In English, this says: let $z$ be the set of elements in $R$ that are not in the subset of $R$ that they are mapped to. In some sense, we are constructing $z$ by looking at each element of $R$, and making sure $z$ is different from the subset each element is mapped to. Clearly, $z$ is a subset of $R$, and since $z$ is not equal to $f(a)$ for each $a \in R$ (by construction!), then $z \not \in f(R) \subseteq \mathcal{P}(R)$. But that means we found a subset of $R$ that is not hit under $f$, so $f$ is not surjective. (Another way to see this is: if $g : A \to B$ is surjective, then $g(A) = B$. But we just showed $f(R) \neq \mathcal{P}(R)$ since $z \in \mathcal{P}(R)$ but $z \not \in f(R)$.)

Since $f$ was any arbitrary map, we can conclude there is no surjection from $R$ to $\mathcal{P}(R)$, so their cardinalities are different

Answer 2

You can show that any map $f : R \to P(R)$ is not onto as follows: for each $r \in R$, $f(r)$ is a subset of $R$. Thus either $r \in f(r)$ or not. Define $$E = \{r \in R : r \notin f(r) \}.$$ Can you show that $E = f(e)$ for some $e \in R$ leads to a contradiction?

Answer 3

Show that there is no bijective function between a set $X$ and $P(X)$ by contradictions. You just need the definition of bijective and then conclude that there cannot exists such a function. Then this follows as a lemma.

Answer 4

If $R$ = $∅$, $℘$($R$) = { {$∅$} }. Suppose that $R$ ≠ ∅. Then, there is a one-to-one mapping $ƒ$, $R$ onto ℘($R$). We now consider the set of elements of $R$ which are not mapped to the subset of R under $ƒ$. Let $B$ = {$r$ $∈$ $R$ ; $r$ $∉$ $ƒ$($r$)}. We will try to arrive at some contradiction. Suppose $x$ $∈$ $B$. $⇒$ $x$ $∈$ {$r$ $∈$ $R$ ; $r$ $∉$ $ƒ$($r$)} $⇒$ $x$ $∉$ $ƒ$($x$) $=$ $B$. Next, suppose $x$ $∉$ $B$. Then $x$ $∉$ $ƒ$($x$) and so $x$ $∈$ {$r$ $∈$ $R$ ; $r$ $∉$ $ƒ$($r$)} $=$ $B$, a contradiction.