What makes the proof of Cantor's theroem, for countably infinite sets, inapplicable to infinite sets?

Question

(This may be a naive question born out of ignorance, so bear with me)

What is the reason that Cantor's theorem can't be proven for infinite sets "simply" by indicating that for every element $ a $ added to set $ A$, $ P(A) $ will double its cardinality, resulting in an inability to satisfy surjection from $A$ to $P(A)$? (each added element in $A$ can only be mapped to one element in $P(A)$, whereas $P(A)$ has necessarily expanded by more than one element)

In other words, why isn't the $ n < 2^n $ argument regarding $ A $ and $P(A)$ cardinality sufficient?

Thanks!

Answer 1

That could form the basis for a solid induction argument that would show $|A| \le |P(A)|$ for all finite sets $A$. Note that, at no point do you deal with an infinite set; the sets you're dealing with are just larger and larger finite sets. This way, if you formalised this argument with induction, you could deal with every possible finite set, but there's no path to infinite sets.

Remember how induction works:

• You establish a base case, i.e. prove what you want to prove for some specific $n$, usually $0$ or $1$,
• You show that if the $n$th case works, then so must the $(n+1)$th case (the induction step).

This way, you have shown that any (finite) case works. Because you proved it for $n = 0$, you therefore know, from the inductive step, that the $n = 1$ case works too. From this case, you know that $n = 2$ case works, and the $n = 3$ case, and the $n = 4$ case, etc, etc. If you wanted a self-contained, induction-free proof that the $n = 200$ case worked, you could write down the $n = 0$ case, then write the induction step down $200$ times, incrementing $n$ each time.

Essentially, there needs to be a finite path from your base case to whichever case you want to establish. The $n = 200$ case has a path of $200$ induction steps. It's long, but it's there.

No such path exists from an infinite set to a finite set, by removing single elements from the set. Every time you remove a single element from an infinite set, you get a set that, as it turns out, is equally large as the set you started with. Removing a single element does not get you any closer to your base case, as it has no effect on the cardinality of the set, or indeed its power set.

If you want an example where this reasoning can go wrong, compare $A$ and $A \times A$ (for $|A| \ge 2$). While $|A|$ grows linearly, $|A \times A|$ grows quadratically, outpacing $|A|$. For every one element we add to $A$, we are adding $2|A| + 1 > 1$ elements to $|A \times A|$. By the same reasoning, we might expect $|A \times A| > |A|$ for infinite sets too. But, this is not the case; $\Bbb{N} \times \Bbb{N}$ has the same cardinality as $\Bbb{N}$.

Answer 2

Suppose you did have a surjection $f$ from $A$ to $P(A)$.

And now you want to prove that there is no surjection $g$ from $A\cup\{a\}$ to $P(A\cup\{a\})$.

From your question, it appears that you are assuming you "just" have to find an image for $a$, and $g(x)$ will always be the same as $f(x)$ for $x\in A$. This is by no means the case, $g$ could in principle be an entirely new function. This is what is missing from your suggested proof.