6.2 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. We then study 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

Definition

Power set notation

For a set $X$, the notation $2^X$ denotes the set of all subsets of $X$.

Thus

$$T\in 2^X$$

means exactly that $T\subseteq X$.

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.

For the empty set this notation is already informative:

$$2^\varnothing=\{\varnothing\}.$$

There is one subset of the empty set, namely the empty set itself. Thus the finite pattern $|2^X| = 2^{|X|}$ starts with $2^0=1$. The theorem below is stronger than this finite counting rule: it compares cardinalities even when there is no finite number that counts the elements.

Theorem

Cantor's theorem

Let $X$ be a set. Then

$$|X|\lt |2^X|.$$

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|\lt |2^X|$.

The contradiction is driven by surjectivity. The singleton map already gives the injection needed for $|X|\le |2^X|$; we do not need to show that every subset is a singleton. To rule out equality, assume a bijection and therefore the surjective statement that every subset of $X$, including $T$, must equal some $f(y)$. The two membership cases then exhaust all possibilities, including the case $X=\varnothing$: in that case there is no function value that could be surjective onto the one-element set $2^\varnothing$, so the assumed bijection fails immediately.

Proof X-Ray

What the Cantor proof has to establish

The proof has two independent obligations. The singleton map proves $|X|\le |2^X|$. The diagonal construction proves that equality is impossible by making a subset that disagrees with $f(x)$ at the coordinate $x$. In the contradiction, the equation $f(y)=T$ comes from surjectivity, and the final case split uses only the definition of membership in $T$.

Reading the diagonal as a membership table

The singleton injection proves the non-strict inequality. For example, when $X=\{a,b\}$, it selects two of the four subsets $\varnothing,\{a\},\{b\},\{a,b\}$. The diagonal construction explains why no proposed assignment can hit every subset, even for an infinite set.

Here is a finite illustration with $X=\{a,b,c\}$. Each row records one proposed value of $f$; a $1$ means that the column element belongs to that subset, and a $0$ means that it does not. The bold entries in the first three rows lie on the diagonal.

Read the diagonal as $1,0,1$ and reverse each decision to obtain $0,1,0$. Thus $T=\{b\}$. It differs from $f(a)$ at $a$, from $f(b)$ at $b$, and from $f(c)$ at $c$. Agreement at other positions cannot repair even one of these differences.

For an arbitrary set, the same rule is $x\in T$ exactly when $x\notin f(x)$. No numerical ordering of $X$ is needed. The table illustrates the mechanism; the proof above supplies the quantifiers for every set, including the empty set.

Explore diagonal disagreement

Use the table below to track which membership decision prevents each row from being the diagonal set. Keep the row index and column element distinct.

Previous rowNext rowk = 0

Change the diagonal entry in every row

f(k)	0	1	2	3	4	5
f(0)	1	0	1	0	1	0
f(1)	1	1	0	1	0	1
f(2)	0	0	1	1	0	0
f(3)	1	0	0	0	1	0
f(4)	0	1	0	0	1	1
f(5)	0	0	0	0	0	0
T	0	0	0	1	0	1

$0\in f(0)$, $0\notin T$; $T\ne f(0)$.

A 1 means membership and a 0 means non-membership. Define $T=\{n\in\mathbb N:n\notin f(n)\}$. For any row $k$, its diagonal bit is opposite to the bit of $T$ at $k$, hence $T\ne f(k)$. The six columns are only a finite illustration: the proof applies to every natural number, with no final row.

The real numbers are uncountable

Theorem

The reals are uncountable

The set $R$ of real numbers is uncountable. In particular,

$$|N|\lt |R|.$$

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

By Cantor's theorem,

$$|N|\lt |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.

Worked example

Encoding a subset of N

If

$$S=\{0,2,5,\ldots\},$$

then the beginning of the sequence is

$$a_0=1,\quad a_1=0,\quad a_2=1,\quad a_3=0,\quad a_4=0,\quad a_5=1.$$

The corresponding real number begins as

$$\phi(S)=\frac13+\frac1{3^3}+\frac1{3^6}+\cdots .$$

The proof does not need to describe this number by a decimal expansion. It only needs the fact that the infinite series determines 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 at most

$$\sum_{n=k+1}^{\infty}\frac1{3^{n+1}} =\frac1{2\cdot 3^{k+1}},$$

which is strictly smaller than the first differing contribution. 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|\lt |2^N|\le |R|,$$

so $R$ is uncountable.

Common mistake

The proof only needs an injection into R

To prove $|2^N|\le |R|$, we do not need every real number to be hit by $\phi$. We only need distinct subsets of $N$ to produce distinct real numbers.

Worked example

A finite version of the ternary separation

Take two binary sequences which first differ at index $k=2$. The contribution at that index has size $1/27$. Even if every later binary digit favours the other sequence, the total later contribution is

$$\frac1{3^4}+\frac1{3^5}+\cdots=\frac1{54},$$

which is only half as large. Thus the first disagreement cannot be cancelled. The same geometric-series estimate works for any first differing index.

The continuum hypothesis

Hypothesis — Continuum hypothesis.

The continuum hypothesis says that there is no set $S$ such that

$$|N|\lt |S|\lt |R|.$$

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. More precisely, if ZFC is consistent, then neither CH nor its negation is provable from ZFC: Godel's result gives the relative consistency of ZFC+CH, and Cohen's forcing result gives the relative consistency of $ZFC+\neg\mathrm{CH}$. These are metamathematical consistency results, not proofs of CH or of its negation inside this course.

For this course, the point is not to prove those metamathematical results but to recognize where axioms matter. Cantor's theorem and real uncountability remain ZFC theorems; CH asks for a sharper comparison between them. In later proofs, record map directions and mark any use of choice or maximality.

Thus “independent” does not mean that CH is meaningless or that every cardinal statement is undecidable. It means that the usual ZFC axioms do not settle this particular intermediate-size question; CH itself is an additional hypothesis.

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\}.$$

Definition

Choice function

Let $S$ be a set whose elements are nonempty sets. A choice function for $S$ is a function

$$f:S\to \bigcup S$$

such that

$$f(X)\in X$$

for every $X\in S$.

A choice function chooses one element from each set in $S$. For an indexed family $(A_i)_{i\in I}$, the same idea is a map

$$c:I\to\bigcup_{i\in I}A_i,\qquad c(i)\in A_i.$$

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.

For a finite family, this selection can be justified by repeatedly applying the ordinary existence of an element in a nonempty set. The axiom of choice addresses an arbitrary family of nonempty sets, especially one with infinitely many members, when no single explicit rule for selecting an element has been provided. The empty family itself has the unique empty choice function; the obstruction is a family that contains an empty member.

Axiom — Axiom of choice.

Let $S$ be a set whose elements are nonempty sets. Then $S$ has a choice function.

This is an axiom, not a theorem proved from the other axioms in the course. The important logical distinction here is between a finite list of choices, which can be built step by step in ZF, and one simultaneous choice from an arbitrary indexed family.

At the metamathematical level, if ZF is consistent, then neither AC nor $\neg\mathrm{AC}$ is provable from ZF. This relative-consistency statement is reported here, not proved here; the working content for this note is the exact choice-function statement and the point where later constructions invoke it.

Worked example

What a choice function does

Let

$$S=\{\{1,2\},\{3,4,5\},\{6\}\}.$$

A choice function might choose

$$f(\{1,2\})=1,\qquad f(\{3,4,5\})=4,\qquad f(\{6\})=6.$$

The function does not have to choose the smallest element. It only has to choose one member of each nonempty set.

The indexed notation makes the same example less ambiguous. Let $I=\{1,2,3\}$ and $A_1=\{1,2\}$, $A_2=\{3,4,5\}$, and $A_3=\{6\}$. Then the displayed choices define a function with domain $I$:

$$c(1)=1,\qquad c(2)=4,\qquad c(3)=6.$$

The condition is checked index by index: $c(1)\in A_1$, $c(2)\in A_2$, and $c(3)\in A_3$. This is a finite family, so the choices can be written down one at a time. For an infinite family, the axiom of choice asserts that a function with the same membership condition exists even when the family does not come with a canonical “first” element in each set.

Surjections and cardinal inequalities

Theorem

Surjections give reverse cardinal inequalities with choice

Assuming the axiom of choice, let $f:X\to Y$ be a surjective function. Then

$$|X|\ge |Y|.$$

To prove this, we need an injection $g:Y\to X$; selecting one representative from every fiber is exactly where choice enters for an arbitrary family.

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 is the earlier warning in concrete form: the original surjection remains many-to-one; choice supplies only one selected preimage per target.

The fibers are pairwise disjoint: if an element belonged to both $f^{-1}(y)$ and $f^{-1}(y')$, applying $f$ would give $y=y'$. Consequently the representatives selected for distinct targets cannot coincide, which is exactly the injectivity of $g$; it is not an inverse of $f$.

Countable unions of countable sets

Theorem

A countable union of countable sets is countable

Assuming the axiom of choice, if ${A_n}_{n\in N}$ is a countable family of countable sets, then

$$A=\bigcup_{n\in N} A_n$$

is countable.

The empty-union case is immediate: if $A=\varnothing$, the empty function is an injection into $N$. Now assume $A$ is nonempty. Since each $A_n$ is countable, for each index $n$ there exists an injection

$$i_n:A_n\to N.$$

When $A_n=\varnothing$, the unique empty function is such an injection. We use the axiom of choice to choose the whole family of injections ${i_n}$ simultaneously, including those empty-member cases. This is a choice issue about the family of witnesses; it is not a claim that a countable union of arbitrary uncountable sets is countable.

Now define

$$h:A\to N\times N,\qquad h(x)=(n(x),i_{n(x)}(x)),$$

where

$$n(x)=\min\{n\in N\mid x\in A_n\}.$$

The minimum exists because $x$ belongs to at least one member of the union and $N$ is well-ordered. The map $h$ is injective. If $h(x)=h(x')$, equality of the first coordinates gives $n(x)=n(x')=n$. Equality of the second coordinates then gives $i_n(x)=i_n(x')$, and the injectivity of $i_n$ gives $x=x'$.

Finally, diagonal enumeration gives an injection $N\times N\to N$, so composing it with $h$ makes $A$ countable. List $(0,0)$, then the pairs whose coordinates sum to $1$, then those whose coordinates sum to $2$, and so on; each pair appears at a finite stage. The index set and every member must be countable: an uncountable index set of singletons, or one uncountable member, can make the union uncountable. Empty members contribute no element.

Common mistake

Countable union is not the same as arbitrary union

The theorem here is about a countable family ${A_n}$. It does not say that an arbitrary union of countable sets must be countable.

Chains, maximal elements, and Zorn's lemma

Zorn's lemma expresses the axiom of choice through the existence of maximal elements.

Definition

Chain

Let $X$ be a partially ordered set. A chain $S\subseteq X$ is a totally ordered subset: for every $a,b\in S$, either

$$a\le b \qquad\text{or}\qquad b\le a.$$

Definition

Maximal element

An element $m\in X$ is called a maximal element if there is no $x\in X$ with

$$x\gt m.$$

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$.

Worked example

Maximal is weaker than maximum

In a partially ordered set, two elements may be incomparable. If neither is above the other, both can be maximal in a small subset even though neither is a maximum.

So "maximal" means "cannot be extended upward from here," not "dominates every element."

Theorem

Zorn's lemma

The axiom of choice is equivalent to the following statement:

if $X$ is a nonempty partially ordered set in which every chain has an upper bound in $X$, then $X$ has a maximal element.

The course states this as a foundational tool; its full proof belongs to a more advanced treatment. Its hypotheses concern partial orders, chains, their upper bounds, and maximal elements.

The quantifiers in Zorn's lemma are easy to reverse accidentally. It does not say that every subset has a maximum, and it does not require one element to bound the entire partially ordered set. It says that for each chain $C\subseteq X$, there exists some $u\in X$ with $c\le u$ for every $c\in C$. Under that hypothesis, at least one element of $X$ cannot be extended strictly upward. The upper bound may depend on the chain.

For a finite illustration, order the proper subsets of $E=\{1,2,3\}$ by inclusion. A chain such as $\varnothing\subset\{1\}\subset\{1,2\}$ has upper bound $\{1,2\}$ inside the same poset, and $\{1,2\}$ is maximal there because adding the remaining element would leave the collection of proper subsets. The set $\{1,2\}$ is not a maximum: the incomparable subset $\{1,3\}$ is not contained in it. This small example separates the vocabulary that the general lemma uses.

Thus a later argument invoking a maximal object must identify its poset, describe its chains, and verify an upper bound for each chain; this is how the abstract choice principle connects to a concrete construction.

Common mistakes and subtle points

Common mistake

Do not treat Cantor's theorem as only finite arithmetic

For finite sets, $2^n\gt n$ is familiar. Cantor's theorem is stronger: it applies to every set, including infinite sets.

Common mistake

Do not confuse maximal with maximum

A maximum is above every element. A maximal element merely has no strictly larger element above it. In partial orders these are different ideas.

Common mistake

Do not hide the role of choice

Choosing one element from each of infinitely many nonempty sets is exactly the kind of step the axiom of choice is designed to justify.

Quick checks

Checkpoint

Why is base 3 used in the injection from $2^N$ to $R$?

Think about the first differing index and the possible tail contribution.

Solution · Answer

Base $3$ makes the first differing term larger than the total possible remaining tail. Therefore two different zero-one sequences cannot define the same real number by cancellation.

Checkpoint

What does a choice function choose?

Mention both the family of sets and the chosen element.

Solution · Answer

For each nonempty set $X$ in a family $S$, a choice function chooses one element $f(X)\in X$.

Checkpoint

Why does the diagonal contradiction need surjectivity?

Identify the step that produces an element $y$ with $f(y)=T$.

Solution · Answer

The diagonal set $T$ is a subset of $X$, so it is an element of $2^X$. Surjectivity says that every element of $2^X$ is $f(y)$ for some $y\in X$; without surjectivity, the constructed $T$ could simply be outside the image.

Exercises

Checkpoint

Show why the singleton map $x\mapsto\{x\}$ is injective.

Assume two singleton sets are equal.

Solution · Guided solution

If

$$\{x_1\}=\{x_2\},$$

then the unique element of the left singleton is the unique element of the right singleton. Hence $x_1=x_2$. Therefore $x\mapsto \{x\}$ is injective.

Checkpoint

Explain why a surjective map $f:X\to Y$ gives nonempty fibers $f^{-1}(y)$.

Use the definition of surjective.

Solution · Guided solution

Surjectivity says that for every $y\in Y$, there exists $x\in X$ such that $f(x)=y$. That means exactly that $x\in f^{-1}(y)$, so the fiber is nonempty.

Checkpoint

Give an indexed choice-function statement for a family $(A_i)_{i\in I}$.

State the domain, codomain, and membership condition.

Solution · Guided solution

A choice function is a map

$$c:I\to\bigcup_{i\in I}A_i$$

such that $c(i)\in A_i$ for every $i\in I$, assuming every $A_i$ is nonempty.

Checkpoint

In Zorn's lemma, why is it not enough to talk only about maximum elements?

Recall that the order is partial, not necessarily total.

Solution · Guided solution

In a partial order, some elements may be incomparable. A maximum would need to be above every element, which may not exist. Zorn's lemma guarantees a maximal element under its hypotheses: an element with no strictly larger element above it.

Related notes

Read this after 6.1 Cardinality, countability, and cardinal inequalities and 2.2 Functions and relations. Continue to 6.3 Intervals, Cantor set, density, and well-ordering to compare cardinality with length, density, and order.