6.1.2-6.3 Cantor's theorem, continuum, and choice

The previous note compared sizes of sets using bijections and injections. This note begins with the first genuinely large-set theorem of the chapter: Cantor's theorem. It shows that every set is strictly smaller than its power set.

That result immediately gives a proof that the real numbers are uncountable. The same pages then move to two foundational statements: the continuum hypothesis and the axiom of choice. The course does not prove their deep metamathematical facts, but it states clearly how they enter the theory.

Power sets and Cantor's theorem

The notation $2^X$ is suggestive: if $X$ has n elements, then its power set has $2^n$ subsets. Cantor's theorem says that the power set is larger not only for finite sets, but for every set.

The proof has two parts.

First, there is an injection

$$X\to 2^X,\qquad x\mapsto \{x\}.$$

So $|X|\le |2^X|$.

Second, there is no bijection from $X$ to $2^X$. Suppose, for contradiction, that $f:X\to 2^X$ were a bijection. Define the diagonal set

$$T=\{x\in X\mid x\notin f(x)\}.$$

Since $T$ is a subset of $X$, we have $T\in 2^X$. If f were surjective, there would be some $y\in X$ such that

$$f(y)=T.$$

Now ask whether $y\in T$.

• If $y\in T$, then by definition of $T$, $y\notin f(y)=T$, a contradiction.
• If $y\notin T$, then by definition of $T$, $y\in f(y)=T$, again a contradiction.

Both cases are impossible. Therefore no bijection $X\to 2^X$ exists, and hence $|X|<|2^X|$.

A diagonal lab

The widget below is meant to support the proof, not replace it. Use it to see how the set $T$ is forced to disagree with each attempted list of subsets.

Figure. The diagonal set is constructed by reversing the membership decision on the diagonal, so it cannot equal any row of the proposed list.

The real numbers are uncountable

The proof uses Cantor's theorem and an injection from $2^N$ into $R$.

By Cantor's theorem,

$$|N|<|2^N|.$$

So it is enough to show

$$|2^N|\le |R|.$$

Given a subset $S\subseteq N$, encode it by a sequence of zeros and ones:

$$a_n= \begin{cases} 1, & n\in S,\\ 0, & n\notin S. \end{cases}$$

Then define

$$\phi(S)=\sum_{n=0}^{\infty}\frac{a_n}{3^{n+1}}\in [0,1].$$

This sends each subset of $N$ to a real number.

Why use base 3 rather than base 2? Base 3 is useful so that distinct zero-one sequences cannot be cancelled by the tail.

If $S\ne S'$, let k be the first index where the two associated sequences differ. At index k, the two sums differ by exactly

$$\frac1{3^{k+1}}.$$

The total possible contribution from all later terms is smaller than that leading difference. Therefore the two real numbers are not equal. Hence $\phi$ is injective, and $|2^N|\le |R|$.

Combining this with Cantor's theorem gives

$$|N|<|2^N|\le |R|,$$

so $R$ is uncountable.

The continuum hypothesis

This is a natural guess after seeing that $R$ is larger than $N$: perhaps there is no intermediate size between the countably infinite cardinality and the cardinality of the continuum.

This guess has a surprising formal status. The continuum hypothesis is independent of the usual axioms of set theory, ZFC. Godel showed in 1940 that it is consistent with ZFC, and Cohen showed in 1963, using forcing, that its negation is also consistent with ZFC. Therefore it can neither be proved nor disproved from the standard axioms alone.

For this course, the important point is not to prove those results. It is to recognize that cardinal arithmetic quickly reaches foundational questions where axioms matter.

Choice functions and the axiom of choice

Before stating the axiom of choice, define how to take a union of a set whose elements are themselves sets:

$$\bigcup S=\{x\mid \exists X\in S\text{ such that }x\in X\}.$$

A choice function chooses one element from each set in the family $S$.

If $S$ contained the empty set, no choice function could exist, because there is no element to choose from the empty set. That is why the definition assumes that the members of $S$ are nonempty.

This is an axiom, not a theorem. Like the continuum hypothesis, its truth or falsehood is independent of the other axioms of set theory.

Surjections and cardinal inequalities

To prove this, we need an injection $g:Y\to X$.

For each $y\in Y$, the fiber

$$f^{-1}(y)\subseteq X$$

is nonempty because f is surjective. Let

$$S=\{f^{-1}(y)\mid y\in Y\}.$$

This is a set of nonempty subsets of $X$. By the axiom of choice, choose one element from each fiber. Define

$$g(y)=\text{the chosen element of }f^{-1}(y).$$

Then $g:Y\to X$ is injective. Indeed, if $g(y)=g(y')$, then the same element of $X$ lies in both fibers, so

$$f(g(y))=y \qquad\text{and}\qquad f(g(y'))=y'.$$

Since $g(y)=g(y')$, it follows that $y=y'$.

This explains the earlier warning: the implication from surjection to reverse cardinal inequality uses choice when infinitely many fibers may need to be selected simultaneously.

Countable unions of countable sets

The proof is organized by surjections. Since each $A_n$ is countable, choose a surjection

$$f_n:N\to A_n.$$

If $A_n$ is finite, one may repeat the last element indefinitely to obtain such a surjection. The axiom of choice is used to choose the whole family of maps ${f_n}$ simultaneously.

Now define

$$F:N\times N\to A,\qquad F(n,m)=f_n(m).$$

This map is surjective: every element of the union lies in some $A_n$, and then is hit by the corresponding $f_n$.

Finally, $N\times N$ is countable by a diagonal argument analogous to the proof that $Q$ is countable. Therefore there is a surjection

$$N\to N\times N.$$

Composing gives a surjection $N\to A$, so $A$ is countable.

Chains, maximal elements, and Zorn's lemma

The final part of the assigned pages states Zorn's lemma, which is equivalent to the axiom of choice.

A maximal element need not be greater than all other elements. This is different from a maximum, which must satisfy $m\ge x$ for every $x\in X$.

The course states this result as a foundational tool. Its full proof belongs to a more advanced treatment, but the definitions should be read carefully now: Zorn's lemma is about partial orders, chains, upper bounds for chains, and the existence of maximal elements.

Common mistakes and subtle points

Quick checks

Exercises

Related notes

Read this after 6.1 Cardinality, countability, and cardinal inequalities and 2.2 Functions and relations. The next course section begins with intervals, so this note closes the big-set foundations used in Chapter 6.1-6.3.