13.1: Basics and Examples

If \(A\) is a set that has the same size as \(\mathbb{N}\text{,}\) then we can think of a bijection \(\mathbb{N} \to A\) as “counting” the elements of \(A\) (even though there are an infinite number of elements to count), in exactly the same way that we use our counting sets \(\mathbb{N}_{<m}\) to count finite sets.

Definition: Countable

a set that is finite or has the same size as \(\mathbb{N}\)

Definition: Countably Infinite

a countable set which has the same size as \(\mathbb{N}\)

Definition: Uncountable

a set that is not countable

Note \(\PageIndex{1}\)

1. An uncountable set is necessarily infinite.
2. Two sets which have the same size (i.e. there exists a bijection between them) are either both countable or both uncountable.

Fact \(\PageIndex{1}\): Characterization of countable sets using sequences.

A nonempty set \(A\) is countable if and only if there exists a sequence of elements from \(A\) in which each element of \(A\) appears exactly once.

Proof Idea.

In case \(A\) is finite, the statement is precisely that of Fact 12.2.1. So assume \(A\) is infinite, in which case a sequence of the type described in the statement must also be infinite. Technically, an infinite sequence from \(A\) is a function \(\mathbb{N} \to A\text{.}\) The “each element of \(A\)” property is the same as saying the function is surjective, and the “exactly once” property is the same as saying the function is injective. So a sequence of the described kind is exactly the same as bijection \(\mathbb{N} \to A\text{,}\) which is what is required for \(A\) to be the same size as \(\mathbb{N}\) (i.e. countably infinite)

Remark \(\PageIndex{1}\)

Compare this fact with Fact 12.2.1.

Theorem \(\PageIndex{1}\): Countability of Integers and Rationals

Sets \(\mathbb{Z}\) and \(\mathbb{Q}\) are both countable.

Proof

We have already constructed a bijection \(\mathbb{N} \to \mathbb{Z}\) in Example 12.3.1, which shows that \(\mathbb{Z}\) is countable.

To show that \(\mathbb{Q}\) is countable, we will use Fact \(\PageIndex{1}\) and construct an infinite sequence which contains each element of \(\mathbb{Q}\) exactly once. First, construct an infinite grid which contains all positive rational numbers. By zig-zagging through the grid, we obtain an infinite sequence which contains each positive element of \(\mathbb{Q}\) at least once, though there are duplicates because an element of \(\mathbb{Q}\) can have many different representations as a fraction.

Figure \(\PageIndex{1}\): A grid containing all positive rational numbers.

Figure \(\PageIndex{2}\): A path through the positive rational numbers.

The path through the grid creates the following sequence of positive rational numbers. By crossing out duplicates, we obtain an infinite sequence which contains each positive rational number exactly once.

\begin{gather*} 1, \;\;\; \dfrac{1}{2}, \;\;\; 2, \;\;\; 3, \;\;\; \xcancel{1,} \;\;\; \dfrac{1}{3}, \;\;\; \dfrac{1}{4}, \;\;\; \dfrac{2}{3}, \;\;\; \dfrac{3}{2}, \;\;\; 4, \;\;\; 5,\\ \xcancel{2,} \;\;\; \xcancel{1,} \;\;\; \xcancel{\dfrac{1}{2},} \;\;\; \dfrac{1}{5}, \;\;\; \dfrac{1}{6}, \;\;\; \dfrac{2}{5}, \;\;\; \dfrac{3}{4}, \;\;\; \dfrac{4}{3}, \;\;\; \dfrac{5}{2}, \;\;\; \dotsc \end{gather*}

Finally, interleave the negative rational numbers into the above sequence, and insert \(0\) at the beginning.

\begin{gather*} 0, \;\;\; 1, \;\;\; -1, \;\;\; \dfrac{1}{2}, \;\;\; -\dfrac{1}{2}, \;\;\; 2, \;\;\; -2, \;\;\; 3, \;\;\; -3, \;\;\; \dfrac{1}{3}, \;\;\; -\dfrac{1}{3}, \;\;\;\\ \dfrac{1}{4}, \;\;\; -\dfrac{1}{4}, \;\;\; \dfrac{2}{3}, \;\;\; -\dfrac{2}{3}, \;\;\; \dfrac{3}{2}, \;\;\; -\dfrac{3}{2}, \;\;\; 4, \;\;\; -4, \;\;\; 5, \;\;\; -5, \;\;\; \dotsc \end{gather*}

Here is an example of an uncountable set. The argument to prove the set is uncountable is a famous one, so we encapsulate it as the proof of a Lemma, rather than just a plain Example.

Lemma \(\PageIndex{1}\): An uncountable set of real numbers

Let \(\scr{C}\) represent the set of all real numbers between \(0\) and \(0.2\) (including \(0\)) whose decimal expansions involve only the digits \(0\) and \(1\text{.}\)

Set \(\scr{C}\) is uncountable.

Proof

The argument in this proof is called Cantor's diagonal argument.

We will show that no sequence of numbers from \(\scr{C}\) can contain every element of \(\scr{C}\text{.}\)

Suppose \(\{a_k\}\) is an infinite sequence of elements of \(\scr{C}\text{.}\) We can create an element \(r \in \scr{C}\) which is not in the sequence as follows. Set

\begin{equation*} r = 0.r_1 r_2 r_3 r_4 \cdots \text{,} \end{equation*}
where \(r_k\) is the digit in the \(k^{th}\) decimal place of \(r\text{,}\) according to the following rules.

If the \(k^{th}\) decimal place of \(a_{k-1}\) is \(0\text{,}\) set \(r_k = 1\text{.}\)

If the \(k^{th}\) decimal place of \(a_{k-1}\) is \(1\text{,}\) set \(r_k = 0\text{.}\)

Clearly every digit of \(r\) will be either a \(0\) or \(1\text{,}\) and \(0 \le r \lt 0.2\text{,}\) so \(r \in \scr{C}\text{.}\) (The reason we use \(a_{k-1}\) instead of \(a_k\) in the rules to create \(r\) is to make sure we consider sequence element \(a_0\) somewhere in there.)

Now we have \(a_k \ne r\) for every \(k \in \mathbb{N}\text{,}\) since \(r\) and \(a_k\) differ in the \((k+1)^{th}\) decimal place. Furthermore, \(r \in \scr{C}\) because it is between \(0\) and \(0.2\) and its decimal expansion involves only digits \(0\) and \(1\text{.}\) Therefore, sequence \(\{a_k\}\) does not contain every element of \(\scr{C}\) because it does not contain \(r\text{.}\)

Remark \(\PageIndex{2}\)

1. The “diagonal” part of the name Cantor's diagonal argument refers to the following. If the decimal expansions of the real numbers in the sequence \(\{a_k\}\) are written out in a grid so that each row is one of the numbers \(a_k\) and each column represents a specific decimal place in the sequence numbers, then the rules to create \(r\) can be thought of as “flipping” the digits that occur in the diagonal positions of this grid. (Draw the grid for yourself to see the pattern!)
2. Later in this chapter we will use Lemma \(\PageIndex{1}\) to prove that \(\mathbb{R}\) itself is uncountable. (See Theorem 13.2.1.)

​​​​