7.2 Cardinality and Countability

Cardinality is the part of set theory that compares the sizes of sets. For finite sets this agrees with ordinary counting, but for infinite sets the idea becomes more subtle, because two infinite sets may have the same size even when one appears to sit inside the other as a proper subset.

Size by Correspondence

The basic idea is that two sets have the same size when their elements can be paired without omission or repetition. This avoids relying on ordinary counting, which works only for finite sets.

For example, the sets:

A=\{a,b,c\}

and:

B=\{1,2,3\}

have the same size because we can pair:

a \leftrightarrow 1, \quad b \leftrightarrow 2, \quad c \leftrightarrow 3

In finite cases this means both sets have the same number of elements. In infinite cases this becomes the definition of having the same cardinality.

Definition 7.42 (Equipotence)

Two sets $A$ and $B$ are equipotent if there exists a bijection:

f:A\to B

In this case we say that $A$ and $B$ have the same cardinality, and we write:

|A|=|B|

The notation $|A|$ denotes the cardinality of $A$ , meaning the size of $A$ considered up to bijection.

Example 7.43

The set:

\mathbb{N}=\{0,1,2,3,\dots\}

and the set of even natural numbers:

E=\{0,2,4,6,\dots\}

have the same cardinality.

Define:

f:\mathbb{N}\to E

by:

f(n)=2n

This function is injective because:

2m=2n \to m=n

It is surjective because every even natural number has the form $2n$ for some $n\in\mathbb{N}$ .

Thus $f$ is a bijection, and therefore:

|\mathbb{N}|=|E|

This example shows that an infinite set can have the same cardinality as one of its proper subsets.

Lemma 7.44 (Equipotence Is an Equivalence Relation)

Equipotence is an equivalence relation on sets.

That is, for all sets $A$ , $B$ , and $C$ :

|A|=|A|

if:

|A|=|B|

then:

|B|=|A|

and if:

|A|=|B| \quad \text{and} \quad |B|=|C|

then:

|A|=|C|

Proof

Reflexivity follows from the identity function:

\mathrm{id}_A:A\to A

which is a bijection, so $A$ has the same cardinality as itself.

Symmetry follows because if $f:A\to B$ is a bijection, then by Lemma 7.37 there exists an inverse bijection:

f^{-1}:B\to A

so $B$ has the same cardinality as $A$ .

Transitivity follows because if $f:A\to B$ and $g:B\to C$ are bijections, then the composition:

g\circ f:A\to C

is also a bijection. Hence $A$ and $C$ have the same cardinality.

Finite Sets

A set is finite when its elements can be counted by some natural number. We define this using bijections with initial segments of the natural numbers.

For $n\in\mathbb{N}$ , write:

[n]=\{0,1,\dots,n-1\}

Thus:

[0]=\varnothing

[1]=\{0\}

[2]=\{0,1\}

[3]=\{0,1,2\}

Definition 7.45 (Finite Set)

A set $A$ is finite if there exists some $n\in\mathbb{N}$ and a bijection:

f:[n]\to A

In this case we say that $A$ has $n$ elements and write:

|A|=n

A set is infinite if it is not finite.

Example 7.46

The set:

A=\{a,b,c\}

is finite because there is a bijection:

f:[3]\to A

given by:

f(0)=a,\quad f(1)=b,\quad f(2)=c

Therefore:

|A|=3

The empty set is finite because:

[0]=\varnothing

and the identity map:

\varnothing\to\varnothing

is a bijection.

Lemma 7.47 (Finite Cardinality Is Unique)

If a set $A$ is in bijection with $[m]$ and also in bijection with $[n]$ , then:

m=n

Proof

It is enough to show that there is no bijection between $[m]$ and $[n]$ when $m\ne n$ .

Assume without loss of generality that $m<n$ . Then $[m]$ has fewer positions than $[n]$ . A function from $[m]$ to $[n]$ can assign at most one output to each of the $m$ inputs, so its image contains at most $m$ elements. Since $[n]$ has $n$ elements and $m<n$ , at least one element of $[n]$ cannot be in the image. Therefore no function $[m]\to[n]$ can be surjective.

Hence no bijection exists between $[m]$ and $[n]$ when $m\ne n$ , so the number of elements of a finite set is well defined.

Countable Sets

Countability extends the idea of listing elements. A set is countable if its elements can be arranged in a sequence, possibly with repetitions removed, so that every element eventually appears.

Definition 7.48 (Countable Set)

A set $A$ is countable if there exists a surjection:

f:\mathbb{N}\to A

Equivalently, $A$ is countable if it is finite or there exists a bijection:

g:\mathbb{N}\to A

When there exists a bijection $\mathbb{N}\to A$ , the set $A$ is called countably infinite.

Example 7.49

The set $\mathbb{N}$ is countably infinite, since the identity function:

\mathrm{id}_{\mathbb{N}}:\mathbb{N}\to\mathbb{N}

is a bijection.

The set of even natural numbers is countably infinite by the bijection:

n\mapsto 2n

The set of odd natural numbers is countably infinite by the bijection:

n\mapsto 2n+1

Lemma 7.50 (Every Subset of a Countable Set Is Countable)

If $A$ is countable and $B\subseteq A$ , then $B$ is countable.

Proof

Since $A$ is countable, there exists a surjection:

f:\mathbb{N}\to A

If $B=\varnothing$ , then $B$ is finite and hence countable.

Assume $B$ is nonempty, and choose an element:

b_0\in B

Define a function:

g:\mathbb{N}\to B

as follows. For each $n$ , if $f(n)\in B$ , set:

g(n)=f(n)

If $f(n)\notin B$ , set:

g(n)=b_0

Then $g$ maps $\mathbb{N}$ into $B$ . We claim that $g$ is surjective. Let $b\in B$ . Since $f$ is surjective onto $A$ , there exists $n\in\mathbb{N}$ such that:

f(n)=b

Because $b\in B$ , the definition gives:

g(n)=f(n)=b

Therefore every element of $B$ is hit by $g$ , so $B$ is countable.

Countability of the Integers

The integers extend the natural numbers by adding negative numbers:

\mathbb{Z}=\{\dots,-3,-2,-1,0,1,2,3,\dots\}

Although $\mathbb{Z}$ appears larger than $\mathbb{N}$ , it is still countable because its elements can be listed in a sequence.

Lemma 7.51 (The Integers Are Countable)

The set $\mathbb{Z}$ is countably infinite.

Proof

Define:

f:\mathbb{N}\to\mathbb{Z}

by:

f(0)=0

and for $n\geq 1$ :

f(2n-1)=n

f(2n)=-n

This gives the listing:

0,1,-1,2,-2,3,-3,\dots

Every integer appears exactly once in this list. The number $0$ appears at index $0$ . If $k>0$ , then $k=f(2k-1)$ . If $k<0$ , then $k=f(-2k)$ . Therefore $f$ is surjective.

One may also check that no two indices give the same integer, so $f$ is injective. Hence $f$ is a bijection, and:

|\mathbb{Z}|=|\mathbb{N}|

Countability of Products

A key fact is that the product of two countable sets is countable. The main example is:

\mathbb{N}\times\mathbb{N}

This means that all ordered pairs of natural numbers can be listed in a single sequence.

Lemma 7.52 (The Product of Two Countable Sets Is Countable)

If $A$ and $B$ are countable, then:

A\times B

is countable.

Proof

It is enough to prove that:

\mathbb{N}\times\mathbb{N}

is countable, because if $A$ and $B$ are countable, then their elements can be listed using natural numbers, and pairs of elements can be listed by first listing pairs of indices.

We list the pairs $(m,n)$ by increasing value of:

m+n

The list begins:

(0,0)

(0,1),(1,0)

(0,2),(1,1),(2,0)

(0,3),(1,2),(2,1),(3,0)

Every pair $(m,n)$ appears in the finite block where:

m+n=k

Since every natural number $k$ eventually appears, every pair appears somewhere in the list. Therefore there is a surjection:

\mathbb{N}\to\mathbb{N}\times\mathbb{N}

Hence:

\mathbb{N}\times\mathbb{N}

is countable.

Since any product $A\times B$ of countable sets is the image of a countable set under a suitable map, it is also countable.

Corollary 7.53 (Finite Products of Countable Sets Are Countable)

If:

A_1,A_2,\dots,A_n

are countable sets, then:

A_1\times A_2\times \cdots \times A_n

is countable.

Proof

The proof is by induction on $n$ .

For $n=1$ , the statement is the definition of countability.

Assume the result holds for $n$ . Then:

A_1\times \cdots \times A_n

is countable by the induction hypothesis. Since $A_{n+1}$ is countable, Lemma 7.52 implies:

(A_1\times \cdots \times A_n)\times A_{n+1}

is countable. This set is naturally identified with:

A_1\times \cdots \times A_n\times A_{n+1}

Thus the result holds for $n+1$ .

Countability of the Rational Numbers

The rational numbers are fractions:

\mathbb{Q}=\left\{\frac{a}{b}:a\in\mathbb{Z},\ b\in\mathbb{Z},\ b\ne 0\right\}

There are infinitely many rational numbers between any two distinct rational numbers, but the whole set is still countable.

Lemma 7.54 (The Rational Numbers Are Countable)

The set $\mathbb{Q}$ is countable.

Proof

Every rational number can be represented by a pair:

(a,b)\in\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})

where:

\frac{a}{b}

is the corresponding rational number.

The set $\mathbb{Z}$ is countable by Lemma 7.51, and the subset:

\mathbb{Z}\setminus\{0\}

is countable by Lemma 7.50.

Therefore:

\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})

is countable by Lemma 7.52.

The map:

(a,b)\mapsto \frac{a}{b}

is a surjection from this countable product onto $\mathbb{Q}$ . Hence $\mathbb{Q}$ is countable.

This proof does not require each rational number to have a unique representation, because countability only requires that every rational number appears at least once in some list.

Countable Unions

A countable union of countable sets is countable. This result is one of the main tools for proving that large looking sets are still countable.

Lemma 7.55 (Countable Union of Countable Sets)

Let:

A_0,A_1,A_2,\dots

be countable sets. Then:

\bigcup_{n\in\mathbb{N}} A_n

is countable.

Proof

Since each $A_n$ is countable, for each $n$ there exists a surjection:

f_n:\mathbb{N}\to A_n

Define:

F:\mathbb{N}\times\mathbb{N}\to \bigcup_{n\in\mathbb{N}} A_n

by:

F(n,m)=f_n(m)

This function is surjective. Indeed, if:

a\in \bigcup_{n\in\mathbb{N}} A_n

then there exists $n$ such that:

a\in A_n

Since $f_n$ is surjective, there exists $m$ such that:

f_n(m)=a

Therefore:

F(n,m)=a

By Lemma 7.52, the set $\mathbb{N}\times\mathbb{N}$ is countable. Since the union is the image of a countable set under $F$ , it is countable.

Uncountable Sets

A set is uncountable if it is not countable. The first and most important example is the power set of the natural numbers.

Definition 7.56 (Uncountable Set)

A set $A$ is uncountable if there is no surjection:

f:\mathbb{N}\to A

Equivalently, $A$ is uncountable if its elements cannot be listed in a sequence indexed by the natural numbers.

Theorem 7.57 (Cantor Diagonal Theorem)

The power set:

\mathcal{P}(\mathbb{N})

is uncountable.

Proof

Suppose, for contradiction, that:

\mathcal{P}(\mathbb{N})

is countable.

Then there exists a surjection:

f:\mathbb{N}\to \mathcal{P}(\mathbb{N})

Thus every subset of $\mathbb{N}$ appears somewhere in the list:

f(0), f(1), f(2), f(3), \dots

Define a subset $D\subseteq\mathbb{N}$ by:

D=\{n\in\mathbb{N}: n\notin f(n)\}

Since $D$ is a subset of $\mathbb{N}$ , it is an element of:

\mathcal{P}(\mathbb{N})

Since $f$ is assumed to be surjective, there exists some $k\in\mathbb{N}$ such that:

f(k)=D

Now ask whether:

k\in D

By definition of $D$ :

k\in D \quad \text{if and only if} \quad k\notin f(k)

But:

f(k)=D

so:

k\in D \quad \text{if and only if} \quad k\notin D

This is impossible. Therefore the assumption that such a surjection exists must be false. Hence:

\mathcal{P}(\mathbb{N})

is uncountable.

Corollary 7.58

There are different sizes of infinity.

Proof

The set $\mathbb{N}$ is infinite and countable. The set:

\mathcal{P}(\mathbb{N})

is infinite and uncountable by Theorem 7.57. Therefore:

|\mathbb{N}| \ne |\mathcal{P}(\mathbb{N})|

Thus not all infinite sets have the same cardinality.

Cantor Theorem

The diagonal argument works for every set, not only for $\mathbb{N}$ .

Theorem 7.59 (Cantor Theorem)

For every set $A$ , there is no surjection:

f:A\to\mathcal{P}(A)

In particular:

|A|<|\mathcal{P}(A)|

in the sense that the power set has strictly larger cardinality than $A$ .

Proof

Suppose, for contradiction, that:

f:A\to\mathcal{P}(A)

is surjective.

Define:

D=\{a\in A:a\notin f(a)\}

Then:

D\subseteq A

so:

D\in\mathcal{P}(A)

Since $f$ is surjective, there exists $d\in A$ such that:

f(d)=D

Now:

d\in D

if and only if:

d\notin f(d)

Since:

f(d)=D

this becomes:

d\in D

if and only if:

d\notin D

This contradiction shows that no such surjection exists.

Real Numbers and Uncountability

The real numbers are uncountable. One way to prove this is to show that the interval:

(0,1)

is uncountable.

The proof uses a diagonal construction similar to Cantor theorem.

Theorem 7.60 (Uncountability of the Unit Interval)

The interval:

(0,1)

is uncountable.

Proof

Suppose, for contradiction, that:

(0,1)

is countable.

Then the real numbers in $(0,1)$ can be listed as:

x_0,x_1,x_2,\dots

Write each $x_n$ in decimal form:

x_n=0.d_{n0}d_{n1}d_{n2}\dots

To avoid ambiguity from decimal expansions ending in repeated $9$ digits, choose decimal expansions that do not eventually become all $9$ .

Now define a new real number:

y=0.e_0e_1e_2\dots

where each digit $e_n$ is chosen so that:

e_n\ne d_{nn}

and also:

e_n\ne 9

For instance, one may choose:

e_n= \begin{cases} 1 & \text{if } d_{nn}\ne 1 \\ 2 & \text{if } d_{nn}=1 \end{cases}

Then $y$ is a real number in $(0,1)$ . Moreover, for each $n$ , the number $y$ differs from $x_n$ in the $n$ th decimal digit. Therefore:

y\ne x_n

for every $n$ .

This contradicts the assumption that the list contains every real number in $(0,1)$ . Hence:

(0,1)

is uncountable.

Corollary 7.61

The set of real numbers $\mathbb{R}$ is uncountable.

Proof

The interval:

(0,1)

is a subset of:

\mathbb{R}

If $\mathbb{R}$ were countable, then every subset of $\mathbb{R}$ would be countable by Lemma 7.50. But Theorem 7.60 shows that $(0,1)$ is uncountable. Therefore $\mathbb{R}$ is uncountable.

Comparing Cardinalities

Cardinality can be compared using injections and surjections.

Definition 7.62 (Cardinality Comparison)

We write:

|A|\leq |B|

if there exists an injection:

f:A\to B

We write:

|A|<|B|

if:

|A|\leq |B|

and:

|A|\ne |B|

This definition says that $A$ has size at most $B$ if $A$ can be embedded into $B$ without identifying distinct elements.

Example 7.63

There is an injection:

\mathbb{N}\to\mathbb{Z}

given by:

n\mapsto n

Thus:

|\mathbb{N}|\leq|\mathbb{Z}|

There is also an injection:

\mathbb{Z}\to\mathbb{N}

because $\mathbb{Z}$ is countable.

Therefore:

|\mathbb{N}|=|\mathbb{Z}|

Theorem 7.64 (Cantor Schroeder Bernstein)

If there is an injection:

f:A\to B

and an injection:

g:B\to A

then there exists a bijection:

h:A\to B

Consequently:

|A|=|B|

Proof

We give the standard construction.

Since $f:A\to B$ and $g:B\to A$ are injections, think of $A$ as sitting inside $B$ through $f$ , and $B$ as sitting inside $A$ through $g$ .

Define:

A_0=A\setminus g[B]

These are the elements of $A$ that are not hit by $g$ .

For each $n\in\mathbb{N}$ , define:

A_{n+1}=g[f[A_n]]

Let:

A^*=\bigcup_{n\in\mathbb{N}} A_n

Now define:

h:A\to B

by:

h(a)=f(a)

if:

a\in A^*

and:

h(a)=g^{-1}(a)

if:

a\notin A^*

This is well defined in the second case because if $a\notin A^*$ , then in particular $a\notin A_0$ , so $a\in g[B]$ , and since $g$ is injective there is a unique $b\in B$ such that:

g(b)=a

One checks that $h$ is injective and surjective.

On the part $A^*$ , the map $h$ uses $f$ to move elements from $A$ to $B$ . Outside $A^*$ , the map uses the inverse of $g$ on its image. The construction separates the elements that must move forward by $f$ from the elements that can move backward by $g^{-1}$ .

Thus $h$ is a bijection from $A$ to $B$ .