I was reading Simmons' book and he states that there are infinite cardinal numbers > $\mathfrak{c}$ where $\mathfrak{c}$ denotes the number of Real Numbers.
For this, he states that we can construct a class consisting of the subsets of the set of Real Numbers and that it is not possible to have one-to-one correspondence with the 2 sets thus proving that there are numbers of higher cardinality.
What I don't understand is how he went about proving the absence of 1-to-1 correspondence. He assumes that it is possible then establishes it via contradiction. ( I did not follow the proof at all but that's another story).
Why can't we simply prove it by induction? If we take a set of 1 element, the "number of elements" in the set and the set of all it's subsets is different. (2^n specifically) so 1-to-1 correspondence is not possible. So, base case is proved. If we assume for k, k+1 th case is proved similarly. So, can't we state that for ANY set, 1-to-1 correspondence is not possible with the set of it's subsets?
Best Answer
Suppose you have a set $S$. Let $T$ be the family of all subsets of $S$. We will prove that there is no one-to-one correspondence between $S$ and $T$.
Suppose we have some function from $S$ to $T$, say $f$. Then for each $x\in S$ we have $f(x)$ is some element of $T$, which is a subset of $S$. The element $x$ might be an element of this subset, or it might not.
Now for each $x$, we will paint $x$ blue if $x\in f(x)$, or green if $x\notin f(x)$. Every element of $S$ is now painted blue or green.
Let $G$ be the set of all green elements of $S$. $G$ is a subset of $S$ and since $T$ is the family of all subsets of $S$, $G$ is an element of $T$.
I claim there is no element $g$ such that $f(g) = G$. Let's suppose that there were and see what happens.
Every element of $S$ is painted blue or green. If there were a $g$ with $f(g) = G$, then $g$ would be either blue or green.
If $g$ were green, it would be an element of $G$, the set of all green elements. But we would have painted $g$ green only if we found that $g\notin f(g) = G$. So $g$ cannot be green.
Perhaps $g$ is blue. We would have painted $g$ blue if we found that $g\in f(g) = G$. But $G$ is the set of all green elements, so if $g$ is blue, it is not in $G$, and we would not have painted it blue in the first place. So again we have a contradiction.
Something is seriously wrong. Certainly we can paint the elements as we said. The only plausible error is our claim that there is a $g$ for which $f(g)= G$. So the function $f$ is not in fact a one-to-one correspondence because there is no $g$ for which $f(g) = G$.
We can apply this argument for any proposed function $f$ and show that $f$ is not a one-to-one correspondence. And the argument works for any set $S$.
If you're still puzzled, try doing this construction for a finite set, such as $\{\mathrm{fish}, \mathrm{dog}, \mathrm{carrot}\}$.
Addendum: The argument above proves that there's no one-to-one correspondence between $S$ and $T$, but it's at least conceivable that $S$ is bigger than $T$. But the obvious mapping that takes $x$ to the set $\{x\}$ shows that there is a proper subset of $T$ that is the same size as $S$, so $T$ is at least as big.
Interesting note: We don't need to assume the existence of a bijective function and then show there is a contradiction. Instead we let $f$ be an arbitrary function and then show constructively that it is not a surjection by producing a specific example of an element not in its range. This is a stronger result than the proof by contradiction would have been.