Proving Cantor's theorem

$\DeclareMathOperator{\card}{card}$From Problem-Solvers Topology

Prove the following:

CANTOR'S THEOREM

If $A$ is a set, then $$\card A < \card \mathcal{P}(A)$$

where $\card A$ stands for the cardinality of set $A$.

My Answer

If $A = \emptyset$, then $\card A =0$ and $\card \mathcal{P}(A)=1$.

If $A = \{a\}$, then $\card A=1$ and $\card \mathcal{P}(A)=2$.

So suppose that $A$ has at least two elements.

Define a function $f: A \rightarrow \mathcal{P}(A)$ such that $f(x) = \{x\}$ for all $x \in A$.

Then $f$ is injective. But it cannot be surjective, because for any two distinct elements $a,b \in A$, there is no element in $A$ that is sent to the set $\{a,b\}$ in $\mathcal{P}(A)$. Therefore, there is no bijection, and $\card A < \card\mathcal{P}(A)$.

Do you think my answer is correct?

Thanks in advance

Solution 1:

You only proved that there is a function that is not a surjection $A \to \mathcal{P}(A)$, not that there is no function that is a surjection $A \to \mathcal{P}(A)$.

Solution 2:

$\DeclareMathOperator{\card}{card}$No. Your answer is not correct. Between any two sets (both having two elements or more) there is a non-surjective map. Your task is to show that every set $A$ and every function from $A$ to $\mathcal P(A)$ is not surjective.

To clarify the point you're missing, the argument in your proof amounts to the following "proof":

"Theorem": There is no bijection between $\{0,1\}$ and $\{2,3\}$.

"Proof". Consider the function $f(0)=f(1)=2$. It is clearly not surjective, therefore it is not a bijection. And therefore $\card(\{0,1\})\neq\card(\{2,3\})$.

Solution 3:

Your argument works when the set is finite, provided one relies on some simple facts about finite sets.

Infinite sets can behave differently. There can be two injections $f:A\to B$ and $g:B\to A$ that both fail to be surjective. That cannot happen with finite sets. (For example, Let $A$ be the interval $[-1,1]$ and let $B$ be the interval $(-1,1)$. Then for $x\in A$ let $f(x)=x/2$, and for $x\in B$ let $g(x)=x$. Both are injective; neither is surjective.

Or for $x\in\{1,2,3,4,5,\ldots\}$, let $f(x)=x^2$. Then $f$ is an injection from this set into itself that is not surjective, and yet a bijection from this set to itself exists (many such bijections exist).

A standard proof of Cantor's theorem (that is not a proof by contradiction, but contains a proof by contradiction within it) goes like this: Let $f$ be any injection from $A$ into the set of all subsets of $A$. Consider the set $$ C=\{x\in A: x\not\in f(x)\}. $$ Then prove by contradiction that there is no $x\in A$ such that $f(x)=C$. (I leave the details of this part as an exercise.)

Note: I did not say which function $f$ is. Therefore this applies to ALL functions from $A$ to the power-set of $A$ that are injective. So ALL of them fail to be surjective.