Countable and Uncountable Sets

Definition and Properties of Countable Sets

We know from the previous topic that the sets ℕ and ℤ have the same cardinality but the cardinalities of the sets ℕ and ℝ are different. Thus, we need to distinguish between two types of infinite sets.

Sets such as ℕ or ℤ 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 |A| = |ℕ|, that is, if there is a bijection ℕ → A.

Respectively, the set A is called uncountable, if A is infinite but |A| ≠ |ℕ|, that is, there exists no bijection between the set of natural numbers ℕ 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.

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 \(\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.

See solved problems on Page 2.

Calculus

Set Theory