Limits of Logic #1: Cantor's Theorem

From: Limits of Logic (Jeffrey Sanford Russell)

1.5.3 Exercise: Cantor's Theorem

For any set $A$, there is no onto function from $A$ to $PA$.

Proof:

Consider a function $f:A→PA$ and assume for contradiction that it is an onto function. That means, for any subset $X⊆A$, there is some $a∈A$ such that $f(a)=X$.

Consider $X={a∈A|a∉f(a)}$.

Since $f$ is an onto function (by assumption), there is some $a0∈A$ such that $f(a0)=X$.

Now, either $a0∈X$ or $a0∉X$.

If $a0∈X$, then by the criteria of membership in $X$, we have that $a0∈X⟹a0∉f(a0)⟹a0∉X$ which is a contradiction.

If $a0∉X$, then by the criteria of membership in $X$, we have that $a0∉X⟹a0∈f(a0)⟹a0X$ which is a contradiction.

And so, there is no such $a0∈A$ such that $f(a0)=X$, which implies that $f$ is not onto, and this contradicts our assumption.

Therefore, there is no onto function from a set $A$ to its power set $PA$. $∎$

This is a theorem about how sets work, fundamentally. Particularly, it is expressing a fact about sizes of sets -- a set is always smaller than its power set.

Why is this theorem interesting?

The theorem is immediately interesting because it expresses that the power set operation on any set takes us to another set that is strictly larger than the original one. This takes us to different sizes of infinities. For example, the set of natural numbers $ℕ$ is infinite, which means its powerset $Pℕ$ is of an even larger infinite size.

But there's something interesting beyond just moving to larger and larger sets. Sometimes we care about two things thing-1 (with set representation $X$) and thing-2 (with set representation $PX$) where the fact that there's always something "left over" in thing-2 when mapping to it from thing-1 expresses an interesting fact about the non set theoretic relationship between the two things.

1.5.4 Example: Undefinable Sets

Let $S$ be a set of strings of symbols. Let $L$ be a set of "descriptions" ( $L⊆S$ ).

Any $d∈L$ is a "description" such that for any string $s∈S$, $d$ is either "true of" $s$ or not.

Call a set of strings $X$ is definable if and only if there is some $d∈L$ such that $d$ is "true of" all $s∈X$.

A consequence of Cantor's theorem is that there'll always be some set of strings that is undefinable.

Consider any function $f:L→PS$ and not that since $L⊆S$, the function cannot be onto.

Now let $f$ be such that for $d∈L$, $f(d)=X$ such that $d$ is "true of" all $s∈X$. Therefore, the range of $f$ is the set of all definable sets of strings. Since $f$ cannot be onto, there is always some $X⊆S$ that is not definable.

And so, we can immediately draw an interesting conclusion about (this informal sense of) definability and truth from Cantor's theorem. There is at least one set of strings such that no one description is true of all strings of that set -- an undefinable set.

Of course, there is much more to say about truth, definability, the set of all strings and their formal senses. That said, the example's strngth has nothing to do with considering a set of strings, or the "true of" relation. The example can be stated in a generic form.

Let $A$ be a non-empty set. For any two place relation $R$, call an $X⊆A$ definable iff there is some $a∈A$ such that $aRx$ for all $x∈X$. There will always be some undefinable subset $X⊆A$.

It's also interesting to relate Cantor's theorem to Russell's paradox. Informally stated as the "barber paradox":

The barber shaves all men in the community who do not shave themselves, and only them.

Now, does the barber shave himself? If yes, then the barber does shave someone who shaves himself -- a contradiction. If no, then the barber does not shave all men who do not shave themselves -- a contradiction as well.

Therefore, our statement cannot be true. This gives us Cantor's theorem when we consider the statement as a stand-in for a set

$X={x∈A|x∉f(x)}$

where $A$ is the set of "all men in the community" and the function $f:A→PA$ takes a man in the community $a∈A$ to the set of men that he shaves $f(a)⊆A$. This makes $X$ the set of all men who only shave those who don't shave themselves.

Is it a paradox that $X$ exists? No, the existence of $X$ is not a paradox; it simply expresses that the "shaves" relation (or any function from a set to the power set) is not onto -- Cantor's theorem.