6.7 Finite, countable and uncountable sets

Recall the definition of cardinality that we saw in Block 2:

This definition tells us that sets $A$ and $B$ have the same cardinality if there exists a bijection between $A$ and $B$ . So functions can help us compare the size of sets!

Theorem 6.50.

Let $X$ and $Y$ be finite sets and let $f:X\rightarrow Y$ be a function.

1.

If $f$ is injective, then $|X|\leq|Y|$ .
2.

If $f$ is surjective, then $|X|\geq|Y|$ .
3.

If $f$ is bijective, then $|X|=|Y|$ .

Proof.

1.

Since $X$ is finite, we can list its elements as $x_{1},\ldots,x_{n}$ where $n=|X|$ . If $f$ is injective, then the elements $f(x_{1}),\ldots,f(x_{n})$ are distinct, so there are exactly $n$ elements in the set $B=\{f(x_{1}),\ldots,f(x_{n}))\}$ . Since this is a subset of $Y$ , the set $Y$ must have at least as many elements as $B$ , so $|Y|\geq n=|X|$ .
2.

Since $Y$ is finite, we can list its elements as $y_{1},\ldots,y_{m}$ where $m=|Y|$ . If $f$ is surjective, then for each $i=1,\ldots,m$ , we can choose some $x_{i}\in X$ such that $f(x_{i})=y_{i}$ . The elements $x_{1},\ldots,x_{m}$ of $X$ are distinct, since if $x_{i}=x_{j}$ then $f(x_{i})=f(x_{j})$ by the definition of a function i.e. $y_{i}=y_{j}$ , hence $i=j$ . Thus, $X$ has at least $m$ distinct elements, giving $|X|\geq m=|Y|$ .
3.

This follows by combining (1) and (2).

As we can also define functions on infinite sets, we can generalise these ideas to infinite sets too.

Definition 6.51 (Countable and uncountable sets).

A set $S$ is said to be countable if it is finite or if there is a bijection from $\mathbb{N}$ to $S$ .

An infinite countable set is said to be countably infinite.

A set that is not countable is said to be uncountable.

It follows almost immediately from the definition that the set $\mathbb{N}$ itself is countably infinite. Indeed, the identity function $id_{\mathbb{N}}$ is a bijection from $\mathbb{N}$ to itself.

Proposition 6.52.

Every subset of $\mathbb{N}$ is countable.

Proof.

Suppose $S$ is a subset of $\mathbb{N}$ . If $S$ is finite then, by definition, it is countable and the proof is complete. If $S$ is an infinite proper subset of $\mathbb{N}$ then the elements of $S$ can be listed in order starting with the smallest; write $S=\{s_{1},s_{2},s_{3},\ldots\}$ where $s_{1}<s_{2}<s_{3}<\cdots$ . Then define $f:\mathbb{N}\to S$ by $f(n)=s_{n}$ . The function $f$ is bijective.

Exercise 6.53.

Explain why $f$ as defined in the proof of Proposition 6.52 is bijective.

Solution (please try for yourself before looking)

The function $f:\mathbb{N}\to S$ defined by $f(n)=s_{n}$ is injective because $s_{1}<s_{2}<s_{3}<\cdots$ and so $f(1)<f(2)<f(3)<\cdots$ . That is, if $f(m)=f(n)$ then $m=n$ . We can see $f$ is surjective because $S=\{s_{1},s_{2},s_{3},\ldots\}$ and thus for every $s_{m}\in S$ , $f(m)=s_{m}$

It may seem intuitive to you that every subset of $\mathbb{N}$ is countable. But less intuitively, it is also possible for sets that contain $\mathbb{N}$ as a proper subset to be countable too!

Example 6.54.

We will show that $\mathbb{Z}$ is countable by defining a bijection between $\mathbb{Z}$ and $\mathbb{N}$ .

Consider the function $f:\mathbb{N}\to\mathbb{Z}$ which is defined by:

f(n)=\begin{cases}-\frac{n}{2}&\text{if $n$ is even,}\\ \frac{n-1}{2}&\text{if $n$ is odd.}\end{cases}

Notice that $f(1)=0$ , $f(1)=-1$ , $f(3)=1$ and so on.

To prove that $f$ is bijective, we need to show that it is both injective and surjective.

To show that $f$ is injective, we need to show that if $f(n)=f(n^{\prime})$ for $n,n^{\prime}\in\mathbb{N}$ , then $n=n^{\prime}$ .

So, suppose $n,n^{\prime}\in\mathbb{N}$ such that $f(n)=f(n^{\prime})$ . Then, $n$ is either even or odd. If $n$ is even, then $f(n)=-\frac{n}{2}=-\frac{n^{\prime}}{2}=f(n^{\prime})$ . Rearranging, we get $n=n^{\prime}$ as desired.

Alternatively, if $n$ is odd, then $f(n)=\frac{n-1}{2}=\frac{n^{\prime}-1}{2}=f(n^{\prime})$ . Again, rearranging gives $n=n^{\prime}$ .

This completes the proof that $f$ is injective.

To show that $f$ is surjective, we need to show that for all $m\in\mathbb{Z}$ , there is some $n\in\mathbb{N}$ such that $m=f(n)$ .

Let $m\in\mathbb{Z}$ . If $m$ is non-negative, then we can take $n=2m+1$ . Note that $n$ is an odd natural number so $f(n)=\frac{2m+1-1}{2}=m$ as desired.

On the other hand, if $m$ is negative, then we can set $n=-2m$ . Then $n$ is an even positive number and hence a natural number. We have $f(n)=-\frac{-2m}{2}=m$ .

Therefore $f$ is surjective.

As $f$ is both surjective and injective, it is bijective.

Since such a bijection exists, this means that $\mathbb{Z}$ is countable.

In fact, as the next theorem states, if we want to show that an infinite set $S$ is countable, it turns out that proving there exists a surjection from $\mathbb{N}$ to $S$ is enough because Proposition 6.52 does the rest of the work for us. We don’t have to go the extra mile to prove the existence of a bijection in this case.

Theorem 6.55.

Let $S$ be any infinite set. The following are equivalent:

(i)

$S$ is countably infinite;
(ii)

there is a surjection from $\mathbb{N}$ to $S$ ;
(iii)

there is an injection from $S$ to $\mathbb{N}$ .

Proof.

•

(i) $\Rightarrow$ (ii): If $S$ is countably infinite then, by definition, there is a bijection from $\mathbb{N}$ to $S$ . This function is surjective.
•

(ii) $\Rightarrow$ (iii): Suppose $f:\mathbb{N}\to S$ is surjective. Then, for any $x\in S$ , the set $f^{-1}(\{x\})\subseteq\mathbb{N}$ is nonempty and so has a unique smallest element, call it $n_{x}$ . Then $g:S\to\mathbb{N}$ defined by $g(x)=n_{x}$ is injective. [Check that you understand why!]
•

(iii) $\Rightarrow$ (i): Suppose $h:S\to\mathbb{N}$ is injective. Then, since $S$ is an infinite set and no pair of elements in $S$ are mapped (under $h$ ) to the same natural number, $h(S)$ is an infinite subset of $\mathbb{N}$ and is therefore countable by Proposition 6.52.

Exercise 6.56.

Prove that any subset of a countable set is countable.

Solution (please try for yourself before looking)

Let $C$ be a countable set and suppose $S\subseteq C$ is subset.

If $C$ is finite then so is $S$ , and so $S$ is also countable.

If $C$ is countably infinite then, by Theorem 6.55, there exists an injection $f:C\to\mathbb{N}$ . We claim that the function $g:S\to\mathbb{N}$ such that $g(x)=f(x)$ for all $x\in S$ is also an injection. Indeed, suppose $x,y\in S\subseteq C$ such that $g(x)=g(y)$ . Then, $f(x)=f(y)$ and, since $f$ is an injection, this means that $x=y$ . Thus $g$ is an injection and, by Theorem 6.55 again, this means that $S$ is countable.

Exercise 6.57.

Let $S$ be any set and suppose $C$ is a countably set. Prove that if there is a bijection $f:C\to S$ then $S$ is also countable.

Solution (please try for yourself before looking)

Suppose $S$ and $C$ are sets where $C$ is a countable set and suppose there exists a bijection $f:C\to S$ . Since $C$ is countable. There exists a bijection $g:\mathbb{N}\to C$ . By Proposition 6.47, this means $f\circ g:\mathbb{N}\to S$ is a bijection and hence, $S$ is countable.

Countability is also preserved when we take the Cartesian product of two countable sets.

Proposition 6.58.

The set $\mathbb{N}\times\mathbb{N}$ is countable.

Proof.

Let $f:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$ be defined by the following rule. Given $n\in\mathbb{N}$ , by the Fundamental Theorem of Arithmetic we can write $n=2^{p}q$ where $p$ is as large as possible. (In other words, factorise $n$ as a power of $2$ multiplied by an odd integer.) Let $f$ be the function that maps $n$ to $(p+1,(q+1)/2)$ . Then $f$ is a bijection [As an exercise, you should prove this], and thus $\mathbb{N}\times\mathbb{N}$ is countable.

Exercise 6.59.

Prove that the Cartesian product of two countable sets is countable.

Solution (please try for yourself before looking)

Suppose $C_{1}$ and $C_{2}$ are countable sets, with bijections $f_{1}:\mathbb{N}\to C_{1}$ and $f_{2}:\mathbb{N}\to C_{2}$ .

Let’s define the function $g:\mathbb{N}\times\mathbb{N}\to C_{1}\times C_{2}$ where $g:(a,b)\mapsto(f_{1}(a),f_{2}(b))$ for every $(a,b)\in\mathbb{N}\times\mathbb{N}$ . We claim that $g$ is a bijection. Indeed, for every $a,b,c,d\in\mathbb{N}$ where $g((a,b))=g((c,d))$ , we have

(f_{1}(a),f_{2}(b))=(f_{1}(c),f_{2}(d))\iff f_{1}(a)=f_{1}(c)\text{ and }f_{2}% (b)=f_{2}(d)

which means that $a=c$ and $b=d$ , since $f_{1}$ and $f_{2}$ are injections. Hence, $(a,b)=(c,d)$ and thus, $g$ is an injection. Also, for every $(x,y)\in C_{1}\times C_{2}$ , the surjectivity of $f_{1}$ and $f_{2}$ means there exists some $t,r\in\mathbb{N}$ such that $f_{1}(t)=x$ and $f_{2}(r)=y$ . Thus, $g((t,r))=(f_{1}(t),f_{2}(r))=(x,y)$ . Hence, $g$ is surjective.

Thus, $g$ is bijective and so, since $\mathbb{N}\times\mathbb{N}$ is countable, 6.57 tells us that $C_{1}\times C_{2}$ is also countable.

Exercise 6.60.

Prove that a set with an uncountable subset is uncountable.

Solution (please try for yourself before looking)

This is the contrapositive of 6.56.

6.7.1 The set of real numbers is uncountable

Theorem 6.61.

The set $(0,1)\subseteq\mathbb{R}$ is uncountable.

Proof.

Suppose $f:\mathbb{N}\to(0,1)$ is a function. We know from Block 1 that every real number in $(0,1)$ has a non-terminating decimal representation. So we may write:

\begin{array}[]{cccccccccc}f(1)&=&0&.&x_{11}&x_{12}&x_{13}&x_{14}&x_{15}&% \ldots\\ f(2)&=&0&.&x_{21}&x_{22}&x_{23}&x_{24}&x_{25}&\ldots\\ f(3)&=&0&.&x_{31}&x_{32}&x_{33}&x_{34}&x_{35}&\ldots\\ \vdots&&&&&&&&&\\ f(k)&=&0&.&x_{k1}&x_{k2}&x_{k3}&x_{k4}&x_{k5}&\ldots\\ \vdots&&&&&&&&&\\ \end{array}

where $x_{ij}\in\{0,1,\ldots,9\}$ for all $i,j\in\mathbb{N}$ .

We shall construct a real number in the interval $(0,1)$ that is not on this list, proving that $f$ is not surjective, and so cannot be a bijection.

Let $y$ be the real number with decimal representation ‘ $0.y_{1}y_{2}\ldots$ ’ where

y_{k}=\begin{cases}1&\text{if $x_{kk}\neq 1$}\\ 2&\text{if $x_{kk}=1$},\end{cases}

for every $k\in\mathbb{N}$ .

Then certainly $y\in(0,1)$ because $0.\overline{1}\leq y\leq 0.\overline{2}$ . Moreover, for every $k\in\mathbb{N}$ , $y\neq f(k)$ because $y_{k}$ differs from $x_{kk}$ .

Thus $f$ is not surjective and so cannot be a bijection.

The above proof uses a technique known as Cantor’s diagonal argument.

Corollary 6.62.

The set of real numbers is uncountable.

Proof.

For a contradiction, assume there is a bijection $f:\mathbb{N}\to\mathbb{R}$ . We claim that the function $g:\mathbb{R}\to(0,1)$ defined by $g(x)=\frac{1}{\pi}\arctan(x)+\frac{1}{2}$ is a bijection.

Indeed, if $x,y\in\mathbb{R}$ such that $g(x)=g(y)$ , then we have

\frac{1}{\pi}\arctan(x)+\frac{1}{2}=\frac{1}{\pi}\arctan(y)+\frac{1}{2}\iff% \arctan(x)=\arctan(y),

which means that $x=y$ since $\arctan:\mathbb{R}\to(-\pi/2,\pi/2)$ is injective. So $g$ is injective.

Also, if $z\in(0,1)$ , then

-\frac{\pi}{2}<\pi\left(z-\frac{1}{2}\right)<\frac{\pi}{2}

and thus there exists some $x\in\mathbb{R}$ such that $\arctan(x)=\pi\left(z-\frac{1}{2}\right)$ since $\arctan$ is surjective. Thus,

g(x)=\frac{1}{\pi}\arctan(x)+\frac{1}{2}=z,

and hence $g$ is surjective.

Therefore $g\circ f:\mathbb{N}\to(0,1)$ is a bijection by Proposition 6.47, and so $(0,1)$ is countable. This contradicts Theorem 6.61, and so no such function $f$ can exist.