Corrections to the Proof of Cantor’s Theorem

I was reading my absolute favorite book on mathematics, Mathematical Problems and Proofs, and it mentions Cantor’s Theorem, that the cardinality of a set is always less than the cardinality of its power set. So for example, the cardinality of $|\{1,2\}| = 2$ , which is less than $|\{ \{\emptyset \}, \{1\}, \{2\}, \{1,2\}\}| = 4$ . There is however no proof in that book of the general case, and instead only a proof of the finite case, expressed as a counting argument. I looked up proofs, and all the proofs I could find seem to have the same hole, which I’ll discuss.

Let $A$ be a set, and let $P(A)$ denote the power set of $A$ , i.e., the set of all of its subsets. Now assume that $|A| \geq |P(A)|$ . That is, we are assuming arguendo that the cardinality of $A$ is not less than the cardinality of its power set, in contradiction to Cantor’s Theorem. It follows that there must be some function $\psi: A \rightarrow P(A)$ such that $\psi$ is surjective, which means that all elements of $P(A)$ are mapped to by $\psi$ , and such a function must exist, because we have assumed that $|A| \geq |P(A)|$ . That is, because $|A| \geq |P(A)|$ , there are enough elements in $A$ to map to every element in $P(A)$ .

Now the next step of the proof (at least the few versions I saw this morning) all universally define the set $B$ below, without addressing the possibility that the set is empty, though it’s possible the original proof addresses this case. My issue with this, is that there doesn’t seem to be any difference between an empty set, and a set that is provably non-existent. As such, I don’t think empty sets should be used as the basis of a proof, unless the proof follows only from the non-existence of the set, and other true theorems, true axioms, or additional assumptions (in the case of a line of reasoning being considered arguendo). In this case, proving the set in question is non-empty, changes the scope of the proof, in that it only applies to sets with a cardinality of two or greater. Most importantly, consistent with this, the accepted proof fails in the case of the power set of the empty set, and in the case of the power set of a singleton, because of this hole. This is very serious, the proof is literally wrong, and fails in two cases, that are plainly intended to be covered by the proof.

The Modified Proof

Specifically, proofs of Cantor’s theorem define $B = \{x \in A | x \notin \psi(x)\}$ . That is, because we know $\psi$ (defined above) must exist, we know that we can define $B$ , using $\psi$ . However, it’s possible that $B$ is empty, since there might not be any such $x \in A$ . That said, a simple additional step will prove that we can always define $\hat{\psi}$ , which will produce a non-empty set $\hat{B}$ .

Assume that $B$ is empty and that $|A| \geq 2$ . Because $A \subset P(A)$ , there must be $x,y \in P(A)$ , such that $x \neq y$ , and $x,y \in A$ . Because $\psi$ is surjective, there must be $a,b$ such that $\psi(a) = x$ and $\psi(b) = y$ . If $a \notin x$ or $b \notin y$ , then $B$ is non-empty. As such, assume that $a \in x$ and $b \in y$ . Now define $\hat{\psi}$ , such that $\hat{\psi}(x) = y$ and $\hat{\psi}(y) = x$ , but otherwise $\hat{\psi}(z) = \psi(z)$ for $z \notin \{x,y\}$ . If $x$ and $y$ are both singletons, then $x \notin y$ and $y \notin x$ . If either is not a singleton (or both are not singletons), then it must be the case that either $x \notin y$ or $y \notin x$ , or both. This implies that $\hat{B}$ is not empty. Because this can be done for any surjective function $\psi$ , we are always guaranteed a non-empty set $\hat{B}.$ Note that $\hat{\psi}$ is still surjective.

Now we can complete the proof as it is usually stated. Because $\hat{\psi}$ is surjective, there must be some $x_0$ such that $\hat{\psi}(x_0) = \hat{B} \subset P(A)$ . It must be the case that either $x_0 \in \hat{B}$ or $x_0 \notin \hat{B}$ . If $x_0 \in \hat{B}$ , then $x_0$ fails the criteria for inclusion in $\hat{B}$ , namely $\hat{B} = \{x \in A | x \notin \hat{\psi}(x)\}$ , since by definition, $\hat{\psi}(x_0) = \hat{B}$ . If $x_0 \notin \hat{B}$ , then $x_0$ satisfies the criteria for inclusion in $\hat{B}$ . In both cases, we have a contradiction. The assumption that $|A| \geq |P(A)|$ implies the existence of $\psi$ , which in turn implies the existence of $\hat{\psi}$ and $\hat{B}$ , which leads to a contradiction. In order to resolve this contradiction, we must therefore assume instead that $|A| < |P(A)|$ , which completes the proof.

The Case of the Empty Set

Now assume that $A = \emptyset$ , and let’s apply the proof above. Generally speaking, we would assume that the power set of the empty set contains one element, namely a set that contains the empty set as a singleton, represented as $P(A) = \{\{\emptyset\}\}$ . Assuming we can even define $\psi$ in this case, it must be that $\psi(\emptyset) = \{\emptyset\}$ . Because $\emptyset \in \{\emptyset\}$ , it must be the case that $B = \emptyset$ . However, if we want $A \neq P(A)$ , it must be the case that $\emptyset \neq \{\emptyset\}$ , even though $\emptyset \in \{\emptyset\}$ . Therefore, $\emptyset \notin P(A)$ , and instead, $\emptyset \in \{\emptyset\}$ , and as a result, the proof fails in the case of $|A| = 0$ since $B = \emptyset \notin P(A)$ . That is, the accepted proof assumes $B$ is contained in the power set, which is just not true in this case, suggesting that there really are problems deriving theorems from empty sets.

The Case of a Singleton

Now assume that $A = \{x\}$ , and let’s apply the proof above. The power set of a singleton is generally defined as $P(A) = \{ \{\emptyset\}, \{x\}\}$ . Because the accepted proof does not explicitly define $\psi$ , we are free to define $\psi(x) = \{x\}$ . Because $x \in \{x\}$ , $B = \emptyset$ . As noted above, $\emptyset \neq \{\emptyset\}$ , and therefore, $B \notin P(A)$ . Again, the accepted proof fails.

Because the accepted proof fails in two cases where $B$ is empty, my axiom above requiring sets to be non-empty in order to derive theorems, must be true. Nothing else above within the proof is subject to meaningful criticism. Again, I have no idea whether Cantor’s original proof addressed these points, but it’s surprising that no one has bothered to apply these proofs to the case of the empty set and a singleton, which would make it clear it doesn’t work.

Discover more from Information Overload

Subscribe to get the latest posts sent to your email.

Discover more from Information Overload

Share this:

Related

Leave a comment Cancel reply