6.2 Cantor's theorem, continuum, and choice

The integers and rationals can both be listed by the natural numbers. Those constructions leave a question open: can every infinite set be listed in this way? A power set supplies an obstruction. From any proposed list of subsets, membership decisions can be used to construct a subset that the list misses.

Power sets and Cantor's theorem

Definition 6.2.1

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

A subset missing from a proposed list

Suppose a function $f:X\to2^X$ assigns one subset to each element of $X$. To find a subset omitted by $f$, it is enough to make it differ from $f(x)$ at one element for each $x$. The index $x$ itself supplies that element: include $x$ precisely when $f(x)$ excludes it. Each row of the proposed list then has a specific reason to disagree with the constructed subset.

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)$. It makes one membership decision for each element of $X$, without requiring a numerical ordering of $X$ or an infinite scanning procedure.

Cantor's theorem

Theorem 6.2.2

(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|$. For example, when $X=\{a,b\}$, this map selects two of the four subsets $\varnothing,\{a\},\{b\},\{a,b\}$; it need not hit every subset.

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

When $X=\varnothing$, the power set has one element and no function from $X$ can hit it. Thus the same conclusion includes the empty-set case.

Proof X-ray

Where surjectivity enters

The equation $f(y)=T$ is the decisive use of surjectivity. The diagonal argument does not use injectivity: it rules out every surjection from $X$ onto $2^X$. The singleton injection supplies the other part of the strict cardinal inequality.

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.

The real numbers are uncountable

Theorem 6.2.3

(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 6.2.4

(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 partial sums are nondecreasing and bounded above by $1/2$, so completeness gives a real limit. This is the same passage from finite approximations to a real number used in 4.6 Decimal expansions and irrational numbers; no conversion to decimal notation is needed.

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 6.2.5

(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

A surjection $f:X\to Y$ reaches every element of $Y$, but it does not specify which preimage to use when several are available. To construct an injection in the reverse direction, we would like to assign each $y$ one element of its fiber $f^{-1}(y)$. Each fiber is nonempty. The additional issue is whether these individual existence statements supply a single function making all the selections at once.

For a family $S$ of sets, all possible selected elements lie in its union:

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

Definition 6.2.6

(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 6.2.7

(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 6.2.8

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

The original surjection may be many-to-one; choice supplies one selected preimage per target. The fibers are pairwise disjoint: an element belonging to both $f^{-1}(y)$ and $f^{-1}(y')$ would give $y=y'$ on applying $f$. Thus the selected representatives for distinct targets cannot coincide.

The identity $f\circ g=id_Y$ makes $g$ a right inverse of $f$. It need not be a two-sided inverse, because $g\circ f=id_X$ is not guaranteed. If $f$ is bijective, each fiber has exactly one element and $g$ is its ordinary inverse.

Countable unions of countable sets

Theorem 6.2.9

(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 index set is nonempty because $x$ belongs to the union, and the well-ordering of $N$ gives its least element. This consequence of induction is proved in 6.3 Intervals, Cantor set, density, and well-ordering. 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 6.2.10

(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 6.2.11

(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 6.2.12

(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 6.2.13

(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

Quick check

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

Quick check

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

Quick check

(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

Quick check

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

Quick check

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

Quick check

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

Quick check

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