So far we have proved that the set of all even numbers P, the set of integers Z, the set of rational numbers Q are enumerable sets. Are there any infinite sets that are not enumerable?

Proof.

If the set of real numbers from the open interval (0,1) was enumerable, then its elements could be line up in a sequence, say d = (d_i)_i=1,2,..., 0 < d_i < 1. Denote the number's d_i digits after decimal point by  d_i1, d_i2, d_i3, ... . Now, we construct a number c = 0,c₁c₂c₃... in which i-th digit after decimal point, marked with c_i, is  characterized by the following conditions:

Of course,  c is a number different from number d₁ (because they differ on the first digit after decimal point). Similarly, for all terms in the sequence d₁, d₂, d₃,... : the number  d_i is different from  c on the i-th position after the decimal point. Although c belongs to the interval (0,1), it never appears in the sequence d. This contradiction proves that the set of all real numbers from the open interval (0,1) is not enumerable. ♦

Question 9.3.1 Is the set of all real numbers countable?

Proof.

Instead of talking about functions we may think of them as about infinite 0-1 sequences. If the set 2^N was countable than we could order all its elements (0-1 sequences) in a sequence. Denote it by (c_i)_{i ∈N} and the terms of i-th sequence by c_i0, c_i1 c_i2 , ... . Now, we build a sequence d = (d₀, d₁ d₂ ,...) in such a way that its i-th term differs from the i-th term of the sequence c_i, e.g.

The sequence d obvoiusly belongs to 2^N  and is different from all sequences c_i (it stores 0 on i-th position if and only if in the sequence c_i the i-th position of c_i  is occupied by the symbol 1, as well as, it stores 1 on the i-th position if and only if  the i-th position of c_i is occupied by the symbol 0). Contradiction, hence it is impossible to build the sequence  (c_i)_{i ∈N}. Therefore, 2^N is a non-enumerable set.  J

Remark Proofs of both lemmas 9.3.1 and 9.3.2 are based on the same method of reasoning which is often called the diagonal method.

Question 9.3.2 Is the set of all subsets of the set N  enumerable?

The following lemma is a simple  conclusion  from  lemma 9.2.1.

Example 9.3.1

The set of all real numbers of closed interval [0,1]  is a non-enumerable set. This fact is the immediate consequence of the above-mentioned lemmas and lemmas 9.3.1 and 9.3.3. But, in our opinion, the following proof is so interesting that it is worth of studying.

Proof. If set [0,1] was countable, then its elements may be lined up in a sequence e.g. (c_i) _{i ∈N} . After that step we split  [0, 1] onto three equal intervals and we chose this one which does not include  c₀. Denote boundaries of this iterval respectively by a₀ and b₀. Now, we split the interval [a₀, b₀] into three equal fragments and we chose this one which does not include  c₁, etc. Denote boundaries of this iterval respectively by a₁ and b₁.This process leads to creation of the following sequence of intervals [a₀,b₀], [a₁,b₁], [a₂,b₂], [a₃,b₃],... with the properties:

1. The sequence (a_i) _{i ∈N} is not decreasing,
2. The sequence (b_i) _{i ∈N} is not increasing,
3. Both sequences are limited.

It follows that the sequences (a_i)_{i ∈N} as well as (b_i)_{i ∈N} are convergent. Because the size of the intervals decreases (three times each time) then lim _{i → ∞} |a_i - b_i| = 0. It implies that there exists a number c = lim_{i → ∞} a_i = lim_{i → ∞} b_i. Of course, for all i, c ∈ [a_i ,b_i ] and c ∈ [0,1]. But the number c is constructed in such a manner that c is different from every number which appears in the sequence (c_i)_{i ∈ N} (c ≠ c₀ because c ∈ [ a₀ ,b₀] and c₀ ∉ [ a₀ ,b₀]; c ≠ c₁ because c ∈ [ a₁ ,b₁] and c₁ ∉ [ a₁ ,b₁]; etc. ). Contradiction. ♦

Question 9.3.3 Is the set of all functions f: N → N countable or not? 

« previous section

next section »