This chapter collects the set theory that the rest of the book takes for granted: ordered pairs, relations, functions, families of sets, inverse images and composites, equivalence relations and the quotient sets they produce, and cardinality. Much of it follows Halmos’s Naive Set Theory. Throughout, denotes the power set of a set , the set of all subsets of ; denotes the set of elements of that do not lie in ; and .
We begin with a discussion of ordered pairs. A set carries no order: , and so on. Say we want to list the elements of in the order , for some arbitrary reason; we may then consider the collection The order is recorded by the number of sets of the collection in which each element appears: lies in all four, in three of them, in two, and in one.
Applying the same idea to a collection of two sets built from elements and gives the definition of a 2-tuple, or ordered pair:
Note. This way of encoding ordered pairs as sets is called the Kuratowski definition of the ordered pair.
The one property of ordered pairs that the rest of the book uses is that a pair determines its coordinates.
Proposition 1.1.1 (Equality of ordered pairs). For all , we have if and only if and .
Proof. If and , the two sets are equal. Conversely, suppose . If , the left side is , which has one element, so the right side has one element too; hence , which forces , and then gives . Thus . If , the left side has two elements, the one-element set and the two-element set . So the right side also has two elements, which forces , and matching the one-element members gives , so . Matching the two-element members gives ; since and , we get . ∎
Ordered triples and, more generally, -tuples can be built the same way; Section 1.4 gives a uniform description of them as families.
Definition 1.1.2 (Cartesian product). The Cartesian product of sets and is the set of ordered pairs We write for .
Since and are subsets of , every pair with and is a set of subsets of , that is, . So is a subset of ; in particular, it is a set.