Answers & Hints for Selected Exercises 64 7EXERCISE SET 2.8- Let A = { ai, a2, · · · , an · · · } and B = {bi, b2, · · · , bn · · · }. Define the func-
tion (sequence) f : N---+ AU B by
f(x) = ak if n = 2k - 1, f(x) =bk if n = 2k (k EN).
If An B = 0, f is a 1-1 correspondence. If An Bf. 0, then deleting those bk
which E A will result in a subsequence that is a 1-1 correspondence N f-t AU B. - Let Ai = {au ai2 ai3
A2 = { a2i a22 a23
A3 = { a3i a 32 a33
ain · · · }
a2n }
a3n · · · }If Ai, A2, ···An,··· are pairwise disjoint, then the function f : LJ:=i An given
by the diagonal counting procedure used in Thm. 2.8.5 is a 1-1 correspon-
dence. If they are not pairwise disjoint, then by omitting from the listing those
members of LJ:=i An previously "counted" by the function f, the resulting
subsequence off is a 1-1 correspondence N f-t LJ:=i An.- (a) The function f: A-- A given by f(x) =xis a 1-1 correspondence.
(b) If f: A---+ Bis a 1-1 correspondence, then 1-i : B-- A is a 1-1 corresp.
(c) If f: A-- B, g: B-- Care 1-1 correspondences, then so is go f: A---+ C.
(For background on this exercise, see Appendix B, Thm. B.3.7.) - Suppose A is an infinite set and B = {xi,x2,-· · ,xn} ~A. Then A - B
has a denumerable subset A' = { Xn+i, Xn+ 2 , · · · }. The function f : A --t A - B
given. b y f ( ) x = { x if x. tt A' U B } 1s. a 1 1 - correspon d ence.
Xn+k if x = Xn, n EN
- Suppose A is an infinite set and B = {bi, b2, b3, · · ·} is a denumerable subset
of A. (The case of finite B is covered by Ex. 7.) Then A - B is infinite, so it
has a denumerable subset B' = {Vi, b2, b~, · · · }. Then f : A ---+ A - B given by
{x if x tt B U B' }
f(x) = b2k if x =bk, k EN is a 1-1 correspondence.
b2k-i if x = b~, k EN- f(x) = a~b~:) shows (a, b) ~(a, +oo). [Draw graph.]
- f(x) = tanx shows (-~, ~) ~JR. [Draw graph.] Since (0, 1) ~ (-~, ~)
and (-~, ~) ~JR, transitivity implies (0, 1) ~JR. - If f : A -- B and g : B -- C are 1-1 correspondences, then (!, g) : A x B ---+
C x D given by (f,g)(x,y) = (f(x),g(y)) is a 1-1 correspondence.