8.4 ARBITRARY COLLECTIONS OF SETS 289- (a) Prove that the set Z of all integers is countably infinite (recall Figure 8.7).
(b) Prove that N x N is a countably infinite set (recall Figure 8.6).
(c) Prove that if S is any countably infinite set, then S x S is countably infinite.
(d) Prove by induction that if {S,, S,,... , S,) (where n E N) is a collection of n
countably infinite sets, then S1 x S2 x - - - x S, is countably infinite. - (a) Prove that if A, and A, are countably infinite sets, then A, u A, is count-
ably infinite. (Hint: Using notation such as A, = {a,,, a,,, a,,,.. .) and A, =
{a,,, a,,,.. .), develop a scheme for listing the elements of A, u A, system-
atically.)
(b) Prove that if {Ail i = 1,2,3,.. .) is a countable collection of sets, each of which
is countably infinite, then Ug, Ai is countably infinite. (This result is usually
paraphrased "a countable union of countable sets is countable.") - (a) Prove that the relation 5 , from Definition 4(a), is a reflexive and transitive
relation on the collection of all subsets of any given universal set U. Is < an anti-
symmetric relation on this collection?
(b) Prove that the relation <, from Definition 4(b), is transitive and not reflexive.
*(c) Prove that if A,, A,, B,, and B, are sets satisfying A, < B,, A, E A,, and
B2 z B1, then A, 5 B,. Explain the significance of this result, relative to the two
paragraphs immediately following Theorem 5. In particular, explain in exactly
what sense 5 can be regarded as an antisymmetric relation, in view of the
Schroeder-Bernstein theorem. - (a) Use the Schroeder-Bernstein theorem to prove that if a, b, c, d E R with a # b
and c # d, then (a, b) z [c, dl.
(b) Verify the following details from the proof of the Schroeder-Bernstein theorem:
(i) The three sets A,, A,, and A, are pairwise disjoint and have union A.
(ii) The mapping f/AA is a one-to-one mapping of AA onto BA.
(iii) The mapping f/A, is a one-to-one mapping of A, onto B,.
(iv) The mapping g/BB is a one-to-one mapping of BB onto A,.
(v) The mapping h, defined in the proof, is a bijection between A and B.
(c) Prove that if a subset S of R contains a nonempty open interval as a subset,
then s r R.
8.4 Arbitrary Collections of Sets
We now return briefly to infinite collections of sets. Recall the treatment,
in Article 4.2, of infinite collections indexed by N, including the union and
intersection of such collections. After studying cardinal numbers, we now
have a different way of characterizing the condition "indexed by N." First,
recall the role of N as an indexing set. It essentially provides a means of
labeling the sets in the collection, of keeping track of and, in a sense,
counting them. Now if each set in an infinite collection can be matched
in a one-to-one fashion with a positive integer, then the collection must