# Countable and Uncountable Sets

## Definition and Properties of Countable Sets

We know from the previous topic that the sets $$\mathbb{N}$$ and $$\mathbb{Z}$$ have the same cardinality but the cardinalities of the sets $$\mathbb{N}$$ and $$\mathbb{R}$$ are different. Thus, we need to distinguish between two types of infinite sets.

Sets such as $$\mathbb{N}$$ or $$\mathbb{Z}$$ are called countable because we can list their elements:

• $$\mathbb{N} = \left\{ {1,2,3,4,5, \ldots } \right\}$$
• $$\mathbb{Z} = \left\{ {0, - 1,1, - 2,2, - 3,3, \ldots } \right\}$$

To define the concept more formally, consider a set $$A.$$ The set $$A$$ is called countably infinite if $$\left| A \right| = \left| \mathbb{N} \right|,$$ that is, if there is a bijection $$\mathbb{N} \to A.$$

Respectively, the set $$A$$ is called uncountable, if $$A$$ is infinite but $$\left| A \right| \ne \left| \mathbb{N} \right|,$$ that is, there exists no bijection between the set of natural numbers $$\mathbb{N}$$ and the infinite set $$A.$$

A set is called countable, if it is finite or countably infinite.

Thus the sets $$\mathbb{Z},$$ $$\mathbb{O},$$ $$\left\{ {a,b,c,d} \right\}$$ are countable, but the sets $$\mathbb{R},$$ $$\left( {0,1} \right),$$ $$\left( {1,\infty } \right)$$ are uncountable.

The cardinality of the set of natural numbers is denoted $$\aleph_0$$ (pronounced aleph null):

$\left| \mathbb{N} \right| = {\aleph_0}.$

Hence, any countably infinite set has cardinality $$\aleph_0.$$

Any subset of a countable set is countable.

Any infinite subset of a countably infinite set is countably infinite.

Let $$A$$ and $$B$$ be countable sets. Then their union $$A \cup B$$ is also countable.

## Cartesian Product of Countable Sets

If $$A$$ and $$B$$ are countable sets, then the Cartesian product $$A \times B$$ is also countable.

Indeed, if the sets $$A$$ and $$B$$ are countable, they can be represented in list form:

$A = \left\{ {{a_1},{a_2},{a_3}, \ldots ,{a_i}, \ldots } \right\},\;\;B = \left\{ {{b_1},{b_2},{b_3}, \ldots ,{b_j}, \ldots } \right\}.$

To provide unique mapping between the ordered pairs $$\left( {{a_i},{b_j}} \right)$$ and natural numbers $$n,$$ we can traverse all elements $$\left( {{a_i},{b_j}} \right)$$ as shown in Figure $$1,$$ starting at the smallest arrow.

There are many other ways to construct a bijective mapping from $$A \times B$$ and $$\mathbb{N}.$$

It follows from the above that the Cartesian product $$\mathbb{N} \times \mathbb{N}$$ is countably infinite, that is,

$\left| {\mathbb{N} \times \mathbb{N}} \right| = {\aleph_0}.$

This result can be generalized to the product of any finite number of countable sets.

## Rational Numbers

The set of rational numbers $$\mathbb{Q}$$ is countable.

Indeed, any rational number $$r$$ other than zero can be written in canonical form as

$r = \frac{p}{q},$

where $$p \in \mathbb{Z},$$ $$q \in \mathbb{N}$$ and $$p$$ and $$q$$ have no common divisors except $$1.$$

The number $$0$$ can be represented, for example, as $$\frac{0}{1}.$$

We can arrange the rational numbers in ascending order of the sum $$\left|p\right| + q:$$

$\begin{array}{*{20}{l}} {\left| p \right| + q = 1:} &{\frac{0}{1}}\\[1em] {\left| p \right| + q = 2:} &{\frac{-1}{1}, \frac{1}{1}}\\[1em] {\left| p \right| + q = 3:} &{\frac{-2}{1}, \frac{-1}{2}, \frac{1}{2}, \frac{2}{1}}\\[1em] {\left| p \right| + q = 4:} &{\frac{-3}{1}, \frac{-1}{3}, \frac{1}{3}, \frac{3}{1}}\\[1em] {\left| p \right| + q = 5:} &{\frac{-4}{1}, \frac{-3}{2}, \frac{-2}{3}, \frac{-1}{4}, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1},} \end{array}$

and so on.

As a result, we get a list of rational numbers that maps to natural numbers. This mapping is bijective. Thus the set of rational numbers $$\mathbb{Q}$$ is countable, that is,

$\left| \mathbb{Q} \right| = {\aleph_0}.$

## Some Uncountable Sets

### Real Numbers

We already know that the sets $$\mathbb{N}$$ and $$\mathbb{R}$$ have unequal cardinalities. Therefore $$\left| \mathbb{R} \right| \ne {\aleph_0}$$ and the set of real numbers is uncountable.

### Irrational Numbers

The set of irrational numbers $$\mathbb{I}$$ is also uncountable. Indeed, $$\mathbb{R} = \mathbb{Q} \cup \mathbb{I}.$$ The set $$\mathbb{Q}$$ is countable. So if we suppose that $$\mathbb{I}$$ is countable, then the union of two countable sets $$\mathbb{Q} \cup \mathbb{I} = \mathbb{R}$$ would also be countable, which contradicts the above statement.

### Set of Infinite Sequences of $$0\text{s}$$ and $$1\text{s}$$

Let $$S$$ be the set of all infinite sequences consisting of $$0\text{s}$$ and $$1\text{s}.$$ This set is uncountable. The proof is based on Cantor's diagonal argument. By contradiction, suppose that $$S$$ is countable. Then we can arrange all infinite sequences in a list like this

$S = \left\{ {{s_1},{s_2},{s_3}, \ldots } \right\}.$

Each infinite sequence is represented as

${s_1} = {s_{11}}{s_{12}}{s_{13}}{s_{14}}{s_{15}} \cdots\cdot$
${s_2} = {s_{21}}{s_{22}}{s_{23}}{s_{24}}{s_{25}} \cdots\cdot$
${s_3} = {s_{31}}{s_{32}}{s_{33}}{s_{34}}{s_{35}} \cdots \cdot$
$\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdot\cdot$
${s_n} = {s_{n1}}{s_{n2}}{s_{n3}}{s_{n4}}{s_{n5}} \cdots$
$\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdot\cdot$

where the elements of the matrix $$\left[ {{s_{nm}}} \right]$$ take values $$0$$ or $$1.$$

Now, using the diagonal elements $${s_{11}},$$ $${s_{22}},$$ $${s_{33}},\ldots,$$ we construct a new infinite sequence $$t = {t_1}{t_2}{t_3}\cdots,$$ where $$t_n$$ is calculated as the binary difference $${t_n} = {s_{nn}} - 1,$$ that is,

${t_i} = \left\{ {\begin{array}{*{20}{l}} {0} &{\text{if}\;\;{s_{nn}} = 1}\\ {1} &{\text{if}\;\;{s_{nn}} = 0} \end{array}} \right..$

It is clear that $$t \ne s_n$$ for any $$n \in \mathbb{N}.$$ Hence, the set $$S$$ is not countable.