110 VI : Infinite constructions in set theory In elementary accounts of set theory, examples of finite collections of objects receive a great deal of attention for several reasons. For example, they provide relatively simple illustrations of the abstract formal concepts in the subject. However, Cantor’s original motivation for studying set theory involved infinite collections of objects, and the real breakthrough of set theory was its ability to provide a framework for studying infinite collections and limits that were previously difficult or out of reach. We shall begin with a variation on the material in Section I I I.3, describing unions and intersections of indexed families of sets; a typical example of this sort is a sequence of sets An, where n runs through all positive integers. In the second section we define a notion of (possibly infinite) Cartesian product for such indexed families. This definition has some aspects that may seem unmotivated, and therefore we shall also describe an axiomatic approach to products such that (i) there is essentially only one set – theoretic construction satisfying the axioms (i i) the construction in these notes satisfies the axioms. In the next two sections we shall present Canto’s landmark results on comparing infinite sets, including proofs of the following: 1. There is a 1 – 1 correspondence between the nonnegative integers N and the integers Z. 2. There is a 1 – 1 correspondence between the nonnegative integers N and the rational numbers Q. 3. There is NO 1 – 1 correspondence between the nonnegative integers N and the real numbers R. We should note that a few aspects of Cantor’s discoveries (in particular, the first of the displayed statements) had been anticipated by Galileo. Section 5 is a commentary on the impact of set theory, and Section 6 looks at generalizations of finite induction and recursion for sets that are larger than the natural numbers N. The latter is included mainly as background for the sake of completeness. VI .1 : Indexed families and set – theoretic operations (Halmos, §§ 4, 8 – 9; Lipschutz, §§ 5.3 – 5.4) One can summarize this section very quickly as follows: In Unit I I I we introduced several ways of constructing a third set out of two given ones, and in this section we111shall describe similar ways of constructing a new set out of a more or less arbitrary list of other ones. We have frequently considered finite and infinite sequences of sets having the form A n where the indexing subscript n runs through some finite or infinite set S of nonnegative integers. Formally such a sequence of sets corresponds to a function for which the value at a given integer n in S is equal to A n . We can generalize this as follows: Definition. Let I be a set. An indexed family of sets with indexing set I is a function from I to some other set X; very often X is the set P(Y) of subsets of some other set Y. Such an indexed family is usually described by notation such as { A i } i ∈∈∈∈ I . In such cases I is generally called the index set, while I(i) = A i is the mapping or (Halmos’ terminology) family, and A i is the element belonging to the index value i, which is sometimes also called the i th element or term of the indexed family. Given any sort of mathematical objects (e.g., partially ordered sets), one can define an indexed family of such objects similarly. As indicated on page 34 of Halmos, in mathematical writings the notation for an indexed family is often abbreviated to { A i }, and this is described by the phrase, “unacceptable but generally accepted way of communicating the notation and indicating the emphasis.” A more concise description would be a “slight abuse of language.” Such an abbreviation should only be used if the indexing set it obvious from the context (for example, a subscript of n almost always denotes an integer) or its precise nature is relatively unimportant and there is no significant danger that the notation will be misinterpreted. Subfamilies. An indexed family { B i } i ∈∈∈∈ J is a subfamily of a family of { A i } i ∈∈∈∈ I , if and only if J is a subset of I and for all i in J we have B i = A i. Indexed unions and intersections Given a set C, in Unit I I I we considered the union $(C), which is the collection of all x such that x ∈∈∈∈ A for some A ∈∈∈∈ C, and we introduced the usual ways of writing these sets as ∪∪∪∪ {A | A ∈∈∈∈ C } or ∪∪∪∪ A ∈∈∈∈ C A. If we have an indexed family of sets { A i } i ∈∈∈∈ I , then the indexed union will refer to the union of the collection { B | B = A i for some i ∈∈∈∈ I }. Recall that here I is a set, and A i is a set for every i ∈∈∈∈ I. In the case that the index set I is the set of natural numbers, one also uses notation is analogous to that of infinite series:112Similarly, given a nonempty set C (recall the extra condition is important!), in Unit I I I we considered the intersection of the sets in C, which is the set of all x such that x ∈∈∈∈ A for every A ∈∈∈∈ C, and we similarly introduced the analogous ways of writing these sets as ∩∩∩∩ {A | A ∈∈∈∈ C } or ∩∩∩∩ A ∈∈∈∈ C A. If we have an indexed family of sets { A i } i ∈∈∈∈ I , then we also have the corresponding indexed intersection As one might expect, this will be the intersection of the collection { B | B = A i for some i ∈∈∈∈ I }. As before, in the case that the index set I is the set of natural numbers, one also uses notation is analogous to that infinite series: These indexed unions and intersections satisfy analogs of the basic formal properties of ordinary unions and intersections which are stated formally on pages 35 – 36 of Halmos. Numerous properties of unions and intersections of indexed families are developed in the exercises VI .2 : Infinite Cartesian products (Halmos, § 9; Lipschutz, §§ 5.4, 9.2) We have already considered n – fold Cartesian products of n sets X1, ... , Xn : X1 × ... × Xn = { (x1, ...,xn) | x1 ∈∈∈∈ X1 & ... & xn ∈∈∈∈ Xn } At least intuitively, this construction can be identified with (X1 × ... × Xn–1) × Xn. We shall not attempt to make this precise here because one can easily do so using the discussion below for general Cartesian products.