Discrete Mathematics for Computer Science

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)}