# Calculus

## Set Theory # 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\},\;\;}\kern0pt{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 $$\large{\frac{0}{1}}\normalsize.$$

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

$\left| p \right| + q = 1:\; \frac{0}{1}$

$\left| p \right| + q = 2:\; \frac{-1}{1}, \frac{1}{1}$

$\left| p \right| + q = 3:\; \frac{-2}{1}, \frac{-1}{2}, \frac{1}{2}, \frac{2}{1}$

$\left| p \right| + q = 4:\; \frac{-3}{1}, \frac{-1}{3}, \frac{1}{3}, \frac{3}{1}$

${\left| p \right| + q = 5:\; \frac{-4}{1}, \frac{-3}{2}, \frac{-2}{3}, \frac{-1}{4},\;}\kern0pt{\frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1},}$

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.

## Solved Problems

Click or tap a problem to see the solution.

### Example 1

Is the set $$\left\{ {\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R},\mathbb{C}} \right\}$$ countable or uncountable?

### Example 2

Prove that the set $${\mathbb{N}^3}$$ is countably infinite.

### Example 3

Prove or disprove: If $$A$$ is an uncountable set and $$B \subset A$$ is a countably infinite set, then the set difference $$A \backslash B$$ is uncountable.

### Example 4

Show that the set $$\mathbb{Q}^n$$ is countable for any $$n \in \mathbb{N}.$$

### Example 5

Prove that the set $$\left\{ {0,1} \right\} \times \mathbb{N}$$ is countably infinite.

### Example 6

Determine whether the set of all finite strings over Latin alphabet is countable or uncountable?

### Example 1.

Is the set $$\left\{ {\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R},\mathbb{C}} \right\}$$ countable or uncountable?

Solution.

Here we have a finite set consisting of $$5$$ elements. Therefore, it is countable despite the fact that some of its elements are uncountable sets.

### Example 2.

Prove that the set $${\mathbb{N}^3}$$ is countably infinite.

Solution.

We know that the Cartesian product $$\mathbb{N}^2 = \mathbb{N} \times \mathbb{N}$$ is countably infinite. The Cartesian product of three sets $$\mathbb{N}^3 = \mathbb{N} \times \mathbb{N} \times \mathbb{N}$$ can be represented as

${\mathbb{N}^3} = {\mathbb{N}^2} \times \mathbb{N}.$

We obtain the product of two countably infinite sets, which is also countably infinite.

In list form, the set $${\mathbb{N}^3}$$ is given by

${{\mathbb{N}^3} }={ \left\{ {\left( {1,1,1} \right),\left( {1,1,2} \right),}\right.}\kern0pt{\left.{\left( {1,2,1} \right),\left( {2,1,1} \right),}\right.}\kern0pt{\left.{\left( {1,2,2} \right),\left( {2,1,2} \right),}\right.}\kern0pt{\left.{\left( {2,2,1} \right),\left( {2,2,2} \right), \ldots } \right\}.}$

### Example 3.

Prove or disprove: If $$A$$ is an uncountable set and $$B \subset A$$ is a countably infinite set, then the set difference $$A \backslash B$$ is uncountable.

Solution.

This is a true statement. It can be proved by contradiction. Suppose that $$A \backslash B$$ is countably infinite. Then the union of two countably infinite sets must also be countable:

$\left( {A\backslash B} \right) \cup B = A.$

This contradicts the fact that the set $$A$$ is uncountable.

### Example 4.

Show that the set $$\mathbb{Q}^n$$ is countable for any $$n \in \mathbb{N}.$$

Solution.

When $$n = 1,$$ we have the set of rational numbers $$\mathbb{Q}$$ which is countable. Suppose, by induction, that $$\mathbb{Q}^n$$ is countable for $$n \in \mathbb{N}.$$ Note that

${\mathbb{Q}^{n + 1}} = {\mathbb{Q}^n} \times \mathbb{Q}.$

It is known that the Cartesian product of two countable sets is countable. Therefore $${\mathbb{Q}^{n + 1}}$$ is a countable set.

It follows that the set $${\mathbb{Q}^{n}}$$ is countable for any $$n \in \mathbb{N}.$$

### Example 5.

Prove that the set $$\left\{ {0,1} \right\} \times \mathbb{N}$$ is countably infinite.

Solution.

The set $$\left\{ {0,1} \right\}$$ is finite and hence countable. The set of natural numbers $$\mathbb{N}$$ is also countable. As it is known, the Cartesian product of two countable sets is countable. Therefore, the set $$\left\{ {0,1} \right\} \times \mathbb{N}$$ is countable.

We can arrange the elements of the set in list form as follows:

${\left\{ {0,1} \right\} \times \mathbb{N} }={ \left\{ {0,1} \right\} \times \left\{ {1,2,3,4, \ldots } \right\} }={ \left\{ \left( {0,1} \right),\left( {1,1} \right),\left( {0,2} \right),\left( {1,2} \right),\right.}\kern0pt{\left.\left( {0,3} \right),\left( {1,3} \right),\left( {0,4} \right),\left( {1,4} \right), \ldots \right\}.}$

This shows that the set $$\left\{ {0,1} \right\} \times \mathbb{N}$$ is countably infinite.

### Example 6.

Determine whether the set of all finite strings over Latin alphabet is countable or uncountable?

Solution.

We assume that the Latin alphabet includes $$52$$ letters (both upper and lower case). Then there are $$52$$ one letter strings, $$52^2$$ two letter strings, etc. Let $$M$$ be the maximum string size. Then the total number of possible strings is $$52^M.$$ We can arrange all these strings as follows:

• We sort the strings by size starting from $$1$$ to $$M.$$
• To arrange the elements within each size, we use the lexicographic order.

The resulting list can be numbered with natural numbers, so this set is countable.