Calculus

Set Theory

Set Theory Logo

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.

A bijective mapping of elements of a Cartesian product to natural numbers.
Figure 1.

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.