Definition

A set is countable if one can enumerate its elements. More precisely, a set S is countable if one can define a function from {1, 2, …} onto S. The interpretation of this function is that it numbers the elements of S. Thus, the function maps the number n into some element s_n of S. This function enumerates S as {s₁, s₂, s₃, s₄, s₅, …}.

Examples

Any subset of a countable set is countable. Indeed, say that S = {s₁, s₂, s₃, s₄, s₅, …} is a countable set and that V is a subset of S. We can then enumerate the elements of V in the order that they appear in S = {s₁, s₂, s₃, s₄, s₅, …}.
Any countable union A = È_nA_n of countable sets is countable. To see this, assume that A_n = {a_n1, a_n2, …}. We can assume that the sets A_n are disjoint by replacing A₂by A₂ \ A₁, and so on. We can then look at A = {a_nm, n, m = 1, 2, …}. Consider the mapping (n, m) ® f(m, n) = 2^m3ⁿ. Let V = {f(m, n) | m, n = 1, 2, …}. Then V is countable (by Example 1). We can write V = {v₁, v₂, v₃, v₄, v₅, …}. Each element a_nm in A is mapped to some element f(m, n) of V. We can then enumerate the elements in A by the corresponding enumeration of V.
The set Q of rational numbers is countable. Recall that Q = {m/n | m Î {…, - 2, -1 , 0, 1, 2, …} and n Î {1, 2, 3, …}}. We let you explain that this is a particular case of Example 2.
The real numbers are not countable. To prove this, assume that one can enumerate the real numbers in [0, 1] as {s₁, s₂, s₃, s₄, s₅, …}. Observe that one can always write a number x in [0, 1] as a binary expansion x = 0.x₁x₂x₃… with the meaning that x = x₁2^-1 + x₂2^-2 + x₃2^-3 + …. For instance, the decimal number 0.324 can be written as ¼ + 0.074 = ¼ + 1/16 + 0.0115 = ¼ + 1/16 + 1/128 + 0.0036875 = ¼ + 1/16 + 1/128 + 1/512 + 0.001953125 = ¼ + 1/16 + 1/128 + 1/152 + 1/1024 + …,. Consequently, we can write 0.324 = 0.0101001011 …. We can make sure that this representation is unique by avoiding an infinite string of consecutive 1s. Let’s write the elements of {s₁, s₂, s₃, s₄, s₅, …} in their binary expansion as s₁ = 0.s₁₁s₁₂s₁₃ …, s₂ = 0.s₂₁s₂₂s₂₃…, s₃ = 0.s₃₁s₃₂s₃₃…,and so on. To show that such an enumeration cannot be exhaustive, not that the element s = 0.s₁s₂s₃… with s₁¹ s₁₁, s₂¹ s₂₂, s₃¹ s₃₃, and so on cannot be in our list. Thus, there is no possible exhaustive enumeration of [0, 1] and this shows that [0, 1] is not countable.

[This argument is called Cantor’s diagonalization argument. It is very similar to the argument that Godel used to prove his celebrated and disturbing theorem on the incompleteness or inconsistency of Arithmetic.]

Importance

Say that S is a set of positive numbers. Assume that the sum a of all the numbers in S is finite. The claim is that S must be countable. To see this, note that the subset S_n of S of elements that are larger than a/n cannot have more than n elements. Also, it is clear that S = È_nS_n. Consequently, from Example 2, S is countable.

Jean Walrand – January 2000 --- INDEX