Section 4.1 Sets
251
implies the principle of well-ordering. (Hint: Assume that the first principle of mathematical induction
is valid, and use proof by contradiction to show that the principle of well-ordering is valid. Let T be a
nonempty subset of the positive integers that has no smallest member. Let P(n) be the property that every
member of T is greater than n.)
96. Prove that the principle of well-ordering (see Exercise 95) implies the second principle of mathematical
induction. Hint: Assume that the principle of well-ordering is valid, and let P be a property for which
1.′ P(1) is true
2.′ (4k)[P(r) true for all r, 1 ≤ r ≤ k S P(k + 1) true]
Let T be the subset of the positive integers defined by
T = {t 0 P(t) is not true}
Show that T is the empty set.
97. Prove that the set of odd positive integers is denumerable.
98. Prove that the set ℤ of all integers is denumerable.
99. Prove that the set of all finite-length strings of the letter a is denumerable.
100. Prove that the set of all finite-length binary strings is denumerable.
101. Prove that the set ℤ × ℤ is denumerable.
102. In Example 23, the claim was made that 0.249999999 … is the same number as 0.250000000 … . The first
representation is a nonterminating decimal, and a calculus-type argument can be made that “in the limit”
these are the same values. Here is a slightly different argument:
a. Let n = 0.249999 … .
Compute 100n by multiplying both sides of this equation by 100.
Subtract n from 100n to give a value for 99n.
Solve the resulting equation for n.
b. Let m = 0.250000 … .
Compute 100m by multiplying both sides of this equation by 100.
Subtract m from 100m to give a value for 99m.
Solve the resulting equation for m.
c. Compare the values of n and m.
103. Use Cantor’s diagonalization method to show that the set of all infinite sequences of positive integers is
not countable.
104. Use Cantor’s diagonalization method to show that the set of all infinite strings of the letters {a, b} is not
countable.
105. Explain why the union of any two denumerable sets is denumerable.
106. Explain why any subset of a countable set is countable.
107. Sets can have sets as elements (see Exercise 13, for example). Let B be the set defined as follows:
B = {S 0 S is a set and S o S}
Argue that both B [ B and B o B are true. This contradiction is called Russell’s paradox, after the famous
philosopher and mathematician Bertrand Russell, who stated it in 1901. (A carefully constructed axiomatization of set theory puts some restrictions on what can be called a set. All ordinary sets are still sets, but
peculiar sets that get us into trouble, like B in this exercise, seem to be avoided.)
251
implies the principle of well-ordering. (Hint: Assume that the first principle of mathematical induction
is valid, and use proof by contradiction to show that the principle of well-ordering is valid. Let T be a
nonempty subset of the positive integers that has no smallest member. Let P(n) be the property that every
member of T is greater than n.)
96. Prove that the principle of well-ordering (see Exercise 95) implies the second principle of mathematical
induction. Hint: Assume that the principle of well-ordering is valid, and let P be a property for which
1.′ P(1) is true
2.′ (4k)[P(r) true for all r, 1 ≤ r ≤ k S P(k + 1) true]
Let T be the subset of the positive integers defined by
T = {t 0 P(t) is not true}
Show that T is the empty set.
97. Prove that the set of odd positive integers is denumerable.
98. Prove that the set ℤ of all integers is denumerable.
99. Prove that the set of all finite-length strings of the letter a is denumerable.
100. Prove that the set of all finite-length binary strings is denumerable.
101. Prove that the set ℤ × ℤ is denumerable.
102. In Example 23, the claim was made that 0.249999999 … is the same number as 0.250000000 … . The first
representation is a nonterminating decimal, and a calculus-type argument can be made that “in the limit”
these are the same values. Here is a slightly different argument:
a. Let n = 0.249999 … .
Compute 100n by multiplying both sides of this equation by 100.
Subtract n from 100n to give a value for 99n.
Solve the resulting equation for n.
b. Let m = 0.250000 … .
Compute 100m by multiplying both sides of this equation by 100.
Subtract m from 100m to give a value for 99m.
Solve the resulting equation for m.
c. Compare the values of n and m.
103. Use Cantor’s diagonalization method to show that the set of all infinite sequences of positive integers is
not countable.
104. Use Cantor’s diagonalization method to show that the set of all infinite strings of the letters {a, b} is not
countable.
105. Explain why the union of any two denumerable sets is denumerable.
106. Explain why any subset of a countable set is countable.
107. Sets can have sets as elements (see Exercise 13, for example). Let B be the set defined as follows:
B = {S 0 S is a set and S o S}
Argue that both B [ B and B o B are true. This contradiction is called Russell’s paradox, after the famous
philosopher and mathematician Bertrand Russell, who stated it in 1901. (A carefully constructed axiomatization of set theory puts some restrictions on what can be called a set. All ordinary sets are still sets, but
peculiar sets that get us into trouble, like B in this exercise, seem to be avoided.)