1.4.9: Sets of Different Sizes, and Cantor’s Theorem

\(\def\Assign#1#2{ { #1^{\Struct{#2}} } }\)
\(\def\Atom#1#2{ { \mathord{#1}(#2) } }\)
\(\def\Bin{ {\mathbb{B}} }\)
\(\def\cardeq#1#2{ { #1 \approx #2 } }\)
\(\def\cardle#1#2{ { #1 \preceq #2 } }\)
\(\def\cardless#1#2{ { #1 \prec #2 } }\)
\(\def\cardneq#1#2{ { #1 \not\approx #2 } }\)
\(\def\comp#1#2{ { #2 \circ #1 } }\)
\(\def\concat{ { \;\frown\; } }\)
\(\def\Cut{ { \text{Cut} } }\)
\(\def\Discharge#1#2{ { [#1]^#2 } }\)
\(\def\DischargeRule#1#2{ { \RightLabel{#1}\LeftLabel{\scriptsize{#2} } } }\)
\(\def\dom#1{ {\operatorname{dom}(#1)} }\)
\(\def\Domain#1{ {\left| \Struct{#1} \right|} }\)
\(\def\Elim#1{ { {#1}\mathrm{Elim} } }\)
\(\newcommand{\Entails}{\vDash}\)
\(\newcommand{\EntailsN}{\nvDash}\)
\(\def\eq[#1][#2]{ { #1 = #2 } }\)
\(\def\eqN[#1][#2]{ { #1 \neq #2 } }\)
\(\def\equivclass#1#2{ { #1/_{#2} } }\)
\(\def\equivrep#1#2{ { [#1]_{#2} } }\)
\(\def\Exchange{ { \text{X} } }\)
\(\def\False{ { \mathbb{F} } }\)
\(\def\FalseCl{ { \lfalse_C } }\)
\(\def\FalseInt{ { \lfalse_I } }\)
\(\def\fCenter{ { \,\Sequent\, } }\)
\(\def\fdefined{ { \;\downarrow } }\)
\(\def\fn#1{ { \operatorname{#1} } }\)
\(\def\Frm[#1]{ {\operatorname{Frm}(\Lang #1)} }\)
\(\def\fundefined{ { \;\uparrow } }\)
\(\def\funimage#1#2{ { #1[#2] } }\)
\(\def\funrestrictionto#1#2{ { #1 \restriction_{#2} } }\)
\(\newcommand{\ident}{\equiv}\)
\(\newcommand{\indcase}[2]{#1 \ident #2\text{:}}\)
\(\newcommand{\indcaseA}[2]{#1 \text{ is atomic:}}\)
\(\def\indfrm{ { A } }\)
\(\def\indfrmp{ { A } }\)
\(\def\joinrel{\mathrel{\mkern-3mu}}\)
\(\def\lambd[#1][#2]{\lambda #1 . #2}\)
\(\def\Lang#1{ { \mathcal{#1} } }\)
\(\def\LeftR#1{ { {#1}\mathrm{L} } }\)
\(\def\len#1{ {\operatorname{len}(#1)} }\)
\(\def\lexists#1#2{ { \exists #1\, #2 } }\)
\(\def\lfalse{ {\bot} }\)
\(\def\lforall#1#2{ { \forall#1\, #2 } }\)
\(\newcommand{\lif}{\rightarrow}\)
\(\newcommand{\liff}{\leftrightarrow}\)
\(\def\Log#1{ { \mathbf{#1} } }\)
\(\def\ltrue{ {\top} }\)
\(\def\Id#1{ {\operatorname{Id}_#1} }\)
\(\def\Int{ {\mathbb{Z}} }\)
\(\def\Intro#1{ { {#1}\mathrm{Intro} } }\)
\(\def\mModel#1{ { \mathfrak{#1} } }\)
\(\newcommand{\mSat}[3][{}]{\mModel{#2}{#1}\Vdash{#3}}\)
\(\newcommand{\mSatN}[3][{}]{\mModel{#2}{#1}\nVdash{#3}}\)
\(\def\Nat{ {\mathbb{N}} }\)
\(\def\nicefrac#1#2{ {{}^#1/_#2} }\)
\(\def\num#1{ { \overline{#1} } }\)

\(\def\ran#1{ {\operatorname{ran}(#1)} }\)
\(\newcommand{\Obj}[1]{\mathsf{#1}}\)
\(\def\Rat{ {\mathbb{Q}} }\)
\(\def\Real{ {\mathbb{R}} }\)
\(\def\RightR#1{ { {#1}\mathrm{R} } }\)
\(\def\Part#1#2{ { \Atom{\Obj P}{#1, #2} } }\)
\(\def\pto{ { \hspace{0.1 cm}\to\hspace{-0.44 cm}\vcenter{\tiny{\hbox{|}}}\hspace{0.35 cm} } }\)
\(\def\PosInt{ {\mathbb{Z}^+} }\)
\(\def\Pow#1{ {\wp(#1)} }\)
\(\newcommand{\Proves}{\vdash}\)
\(\newcommand{\ProvesN}{\nvdash}\)
\(\def\Relbar{\mathrel{=}}\)
\(\newcommand{\Sat}[3][{}]{\Struct{#2}{#1}\vDash{#3}}\)
\(\newcommand{\SatN}[3][{}]{\Struct{#2}{#1}\nvDash{#3}}\)
\(\newcommand{\Sequent}{\Rightarrow}\)
\(\def\Setabs#1#2{ { \{#1:#2\} } }\)
\(\newcommand{\sFmla}[2]{#1\,#2}\)
\(\def\Struct#1{ {#1} }\)
\(\def\subst#1#2{ { #1/#2 } }\)
\(\def\Subst#1#2#3{ { #1[\subst{#2}{#3}] } }\)
\(\def\TMblank{ { 0 } }\)
\(\newcommand{\TMendtape}{\triangleright}\)
\(\def\TMleft{ { L } }\)
\(\def\TMright{ { R } }\)
\(\def\TMstay{ { N } }\)
\(\def\TMstroke{ { 1 } }\)
\(\def\TMtrans#1#2#3{ { #1,#2,#3 } }\)
\(\def\Trm[#1]{ {\operatorname{Trm}(\Lang #1)} }\)
\(\def\True{ { \mathbb{T} } }\)
\(\newcommand{\TRule}[2]{#2#1}\)
\(\def\tuple#1{ {\langle #1 \rangle} }\)
\(\newcommand{\Value}[3][\,]{\mathrm{Val}_{#1}^{#3}(#2)}\)
\(\def\Var{ { \mathrm{Var} } }\)
\(\newcommand{\varAssign}[3]{#1 \sim_{#3} #2}\)
\(\def\Weakening{ { \text{W} } }\)

We have offered a precise statement of the idea that two sets have the same size. We can also offer a precise statement of the idea that one set is smaller than another. Our definition of “is smaller than (or equinumerous)” will require, instead of a bijection between the sets, an injection from the first set to the second. If such a function exists, the size of the first set is less than or equal to the size of the second. Intuitively, an injection from one set to another guarantees that the range of the function has at least as many elements as the domain, since no two elements of the domain map to the same element of the range.

Definition \(\PageIndex{1}\)

\(A\) is no larger than \(B\), written \(\cardle{A}{B}\), iff there is an injection \(f \colon A \to B\).

It is clear that this is a reflexive and transitive relation, but that it is not symmetric (this is left as an exercise). We can also introduce a notion, which states that one set is (strictly) smaller than another.

Definition \(\PageIndex{2}\)

\(A\) is smaller than \(B\), written \(\cardless{A}{B}\), iff there is an injection \(f\colon A \to B\) but no bijection \(g\colon A \to B\), i.e., \(\cardle{A}{B}\) and \(\cardneq{A}{B}\).

It is clear that this relation is anti-reflexive and transitive. (This is left as an exercise.) Using this notation, we can say that a set \(A\) is enumerable iff \(\cardle{A}{\Nat}\), and that \(A\) is non-enumerable iff \(\cardless{\Nat}{A}\). This allows us to restate Theorem 4.6.2 as the observation that \(\cardless{\Nat}{\Pow{\Nat}}\). In fact, Cantor (1892) proved that this last point is perfectly general:

Theorem \(\PageIndex{1}\) (Cantor)

\(\cardless{A}{\Pow{A}}\), for any set \(A\).

Proof. The map \(f(x) = \{x\}\) is an injection \(f \colon A \to \Pow{A}\), since if \(x \neq y\), then also \(\{x\} \neq \{y\}\) by extensionality, and so \(f(x) \neq f(y)\). So we have that \(\cardle{A}{\Pow{A}}\).

We show that there cannot be a surjective function \(g\colon A \to \Pow{A}\), let alone a bijective one, and hence that \(\cardneq{A}{\Pow{A}}\). For suppose that \(g\colon A \to \Pow{A}\). Since \(g\) is total, every \(x \in A\) is mapped to a subset \(g(x) \subseteq A\). We show that \(g\) cannot be surjective. To do this, we define a subset \(\overline{A} \subseteq A\) which by definition cannot be in the range of \(g\). Let \[\overline{A} = \Setabs{x \in A}{x \notin g(x)}.\nonumber\] Since \(g(x)\) is defined for all \(x \in A\), \(\overline{A}\) is clearly a well-defined subset of \(A\). But, it cannot be in the range of \(g\). Let \(x \in A\) be arbitrary, we show that \(\overline{A} \neq g(x)\). If \(x \in g(x)\), then it does not satisfy \(x \notin g(x)\), and so by the definition of \(\overline{A}\), we have \(x \notin \overline{A}\). If \(x \in \overline{A}\), it must satisfy the defining property of \(\overline{A}\), i.e., \(x \in A\) and \(x \notin g(x)\). Since \(x\) was arbitrary, this shows that for each \(x \in \overline{A}\), \(x \in g(x)\) iff \(x \notin \overline{A}\), and so \(g(x) \neq \overline{A}\). In other words, \(\overline{A}\) cannot be in the range of \(g\), contradicting the assumption that \(g\) is surjective. ◻

It’s instructive to compare the proof of Theorem \(\PageIndex{1}\) to that of Theorem 4.6.2. There we showed that for any list \(Z_1\), \(Z_2\), …, of subsets of \(\PosInt\) one can construct a set \(\overline{Z}\) of numbers guaranteed not to be on the list. It was guaranteed not to be on the list because, for every \(n \in \PosInt\), \(n \in Z_n\) iff \(n \notin \overline{Z}\). This way, there is always some number that is an element of one of \(Z_n\) or \(\overline{Z}\) but not the other. We follow the same idea here, except the indices \(n\) are now elements of \(A\) instead of \(\PosInt\). The set \(\overline{B}\) is defined so that it is different from \(g(x)\) for each \(x \in A\), because \(x \in g(x)\) iff \(x \notin \overline{B}\). Again, there is always an element of \(A\) which is an element of one of \(g(x)\) and \(\overline{B}\) but not the other. And just as \(\overline{Z}\) therefore cannot be on the list \(Z_1\), \(Z_2\), …, \(\overline{B}\) cannot be in the range of \(g\).

The proof is also worth comparing with the proof of Russell’s Paradox, Theorem 1.6.1. Indeed, Cantor’s Theorem was the inspiration for Russell’s own paradox.

Problem \(\PageIndex{1}\)

Show that there cannot be an injection \(g\colon \Pow{A} \to A\), for any set \(A\). Hint: Suppose \(g\colon \Pow{A} \to A\) is injective. Consider \(D = \Setabs{g(B)}{B \subseteq A \text{ and } g(B) \notin B}\). Let \(x = g(D)\). Use the fact that \(g\) is injective to derive a contradiction.