Section 4.1 Sets
237
example 22
The set ℚ
+
of positive rational numbers is denumerable.
We assume that each positive rational number is written as a fraction of
positive integers. We can write all such fractions having the numerator 1 in one
row, all those having the numerator 2 in a second row, and so on:
1/1 1/2 1/3 1/4 1/5
2/1 2/2 2/3 2/4 2/5
3/1 3/2 3/3 3/4 3/5
4/1 4/2 4/3 4/4 4/5
To show that the set of all fractions in this array is denumerable, we will thread
an arrow through the entire array, beginning with 1/1; following the arrow gives
an enumeration of the set. Thus the fraction 1/3 is the fourth member in this
enumeration:
1/1 1/2 1/3 1/4 1/5
2/1 2/2 2/3 2/4 2/5
3/1 3/2 3/3 3/4 3/5
4/1 4/2 4/3 4/4 4/5
Therefore the set represented by the array is denumerable. Note that our path
through the array must “spread out” from one corner. If we begin to follow just the
first row or just the first column, for example, we will never finish it to get on to
other rows (or columns).
To obtain an enumeration of ℚ
+
, we use the enumeration of the set shown
but eliminate any fractions not in lowest terms. This avoids the problem of listing
both 1/2 and 2/4, for example, which represent the same positive rational. The
enumeration of ℚ
+
thus begins with
1/1, 2/1, 1/2, 1/3, 3/1, 4/1, …
For example, we have eliminated 2/2, which reduces to 1/1.
■
PraCtiCe 21 What is the 11th fraction in the above enumeration? What is the 1lth positive rational?
Now let’s show that there is an uncountable (not countable) infinite set. The
proof technique that seems appropriate to prove that set A does not have property
B is to assume that A does have property B and look for a contradiction. The
proof in Example 23 is a very famous proof by contradiction known as Cantor’s
diagonalization method, after Georg Cantor, the nineteenth-century German
mathematician known as the “father of set theory.”
237
example 22
The set ℚ
+
of positive rational numbers is denumerable.
We assume that each positive rational number is written as a fraction of
positive integers. We can write all such fractions having the numerator 1 in one
row, all those having the numerator 2 in a second row, and so on:
1/1 1/2 1/3 1/4 1/5
2/1 2/2 2/3 2/4 2/5
3/1 3/2 3/3 3/4 3/5
4/1 4/2 4/3 4/4 4/5
To show that the set of all fractions in this array is denumerable, we will thread
an arrow through the entire array, beginning with 1/1; following the arrow gives
an enumeration of the set. Thus the fraction 1/3 is the fourth member in this
enumeration:
1/1 1/2 1/3 1/4 1/5
2/1 2/2 2/3 2/4 2/5
3/1 3/2 3/3 3/4 3/5
4/1 4/2 4/3 4/4 4/5
Therefore the set represented by the array is denumerable. Note that our path
through the array must “spread out” from one corner. If we begin to follow just the
first row or just the first column, for example, we will never finish it to get on to
other rows (or columns).
To obtain an enumeration of ℚ
+
, we use the enumeration of the set shown
but eliminate any fractions not in lowest terms. This avoids the problem of listing
both 1/2 and 2/4, for example, which represent the same positive rational. The
enumeration of ℚ
+
thus begins with
1/1, 2/1, 1/2, 1/3, 3/1, 4/1, …
For example, we have eliminated 2/2, which reduces to 1/1.
■
PraCtiCe 21 What is the 11th fraction in the above enumeration? What is the 1lth positive rational?
Now let’s show that there is an uncountable (not countable) infinite set. The
proof technique that seems appropriate to prove that set A does not have property
B is to assume that A does have property B and look for a contradiction. The
proof in Example 23 is a very famous proof by contradiction known as Cantor’s
diagonalization method, after Georg Cantor, the nineteenth-century German
mathematician known as the “father of set theory.”