Chapter Review
277
4.8 Countable and Uncountable Sets
TERMS
aleph nought (
1 O)
countably infinite
algebraic
finite
Cantor's first diagonal argument
infinite
Cantor's second diagonal argument
lowest terms
cardinality
transcendental
continuum hypothesis
uncountable
countable
THEOREMS
Cantor-Schrbder-Bemstein
R is uncountable
Properties of Cardinalities
Z is countably infinite
Q is countably infinite
4.10.2 Starting to Review
1. Which of the following are functions?
i. X is the set of students at Purdue University. For x E X, define g(x) to be the
oldest brother of x.
ii. X is the set of governors of Oregon. For x E X, define g(x) is the year that x
was first sworn into office as governor.
iii. For x E R, define g(x) = x/I x 1.
(a) i
(b) ii
(c) iii
(d) None of the above
2. Let X = [1, 2, 3, 4) and Y = [a, b, c, d} be sets. Define the following subsets of
X x Y:
F 1 = {(1, b), (4, d), (2, c), (3, a)}
F 2 = [(3, b), (1, d), (4, c), (2, b))
F 3 = {(4, c), (2, a), (3, b), (1, d)}
Which of the sets F 1 , F 2 , and F3 are 1-1 functions?
(a) F 1 , F 2 , F 3
(b) F 1 , F 3
(c) F 2 , F3
(d) F 1 , F 2
3. Let X = {11, 12, 23, 44} and Y = {r, s, t, vI be sets. Define the following subsets of
X x Y:
F 1 = I (11, r), (44, v), (12, s), (23, t)}
F2 = {(23, s), (11, v), (44, t), (12, s)}
F 3 = 1(44, t), (12, r), (23, s), (11, v)}