Page 197 - Discrete Mathematics and Its Applications

176 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

The continuum hypothesis was stated by Cantor in 1877. He labored unsuccessfully to prove
it, becoming extremely dismayed that he could not. By 1900, settling the continuum hypothesis
was considered to be among the most important unsolved problems in mathematics. It was the
first problem posed by David Hilbert in his famous 1900 list of open problems in mathematics.
The continuum hypothesis is still an open question and remains an area for active research.
However, it has been shown that it can be neither proved nor disproved under the standard set
theory axioms in modern mathematics, the Zermelo-Fraenkel axioms. The Zermelo-Fraenkel
axioms were formulated to avoid the paradoxes of naive set theory, such as Russell’s paradox,
but there is much controversy whether they should be replaced by some other set of axioms for
set theory.

Exercises

1. Determine whether each of these sets is finite, countably 5. Show that a finite group of guests arriving at Hilbert’s
infinite, or uncountable. For those that are countably in- fully occupied Grand Hotel can be given rooms without
finite, exhibit a one-to-one correspondence between the evicting any current guest.
set of positive integers and that set. 6. Suppose that Hilbert’s Grand Hotel is fully occupied, but
a) the negative integers the hotel closes all the even numbered rooms for mainte-
b) the even integers nance. Show that all guests can remain in the hotel.
c) the integers less than 100 7. Suppose that Hilbert’s Grand Hotel is fully occupied on
d) the real numbers between 0 and 1
2 the day the hotel expands to a second building which also
e) the positive integers less than 1,000,000,000 contains a countably infinite number of rooms. Show that
f) the integers that are multiples of 7 the current guests can be spread out to fill every room of
2. Determine whether each of these sets is finite, countably the two buildings of the hotel.
infinite, or uncountable. For those that are countably in- 8. Show that a countably infinite number of guests arriv-
finite, exhibit a one-to-one correspondence between the ing at Hilbert’s fully occupied Grand Hotel can be given
set of positive integers and that set. rooms without evicting any current guest.
a) the integers greater than 10 ∗ 9. Suppose that a countably infinite number of buses, each
b) the odd negative integers containing a countably infinite number of guests, arrive
c) the integers with absolute value less than 1,000,000 at Hilbert’s fully occupied Grand Hotel. Show that all the
d) the real numbers between 0 and 2 arriving guests can be accommodated without evicting
+
e) the set A × Z where A ={2, 3} any current guest.
f) the integers that are multiples of 10
10. Give an example of two uncountable sets A and B such
3. Determine whether each of these sets is countable or un- that A − B is
countable. For those that are countably infinite, exhibit
a) finite.
a one-to-one correspondence between the set of positive
b) countably infinite.
integers and that set.
c) uncountable.
a) all bit strings not containing the bit 0
11. Give an example of two uncountable sets A and B such
b) all positive rational numbers that cannot be written
with denominators less than 4 that A ∩ B is
c) the real numbers not containing 0 in their decimal a) finite.
representation b) countably infinite.
d) the real numbers containing only a finite number of c) uncountable.
1s in their decimal representation 12. Show that if A and B are sets and A ⊂ B then |A|≤|B|.
4. Determine whether each of these sets is countable or un- 13. Explain why the set A is countable if and only if |A|≤
countable. For those that are countably infinite, exhibit |Z |.
+
a one-to-one correspondence between the set of positive
14. Show that if A and B are sets with the same cardinality,
integers and that set.
then |A|≤|B| and |B|≤|A|.
a) integers not divisible by 3
15. Show that if A and B are sets, A is uncountable, and
b) integers divisible by 5 but not by 7
A ⊆ B, then B is uncountable.
c) the real numbers with decimal representations con-
sisting of all 1s 16. Show that a subset of a countable set is also countable.
d) the real numbers with decimal representations of all 17. If A is an uncountable set and B is a countable set, must
1s or 9s A − B be uncountable?