Paul Halmos - Naive Set Theory
Exercises from section 15
Chapter 15 deals with the Axiom of Choice (AoC), as a brief interlude of coming after having explained Order Relations. On the face of it, AoC feels pretty intuitive. An informal rendering would phrase it thus: if you have a (non-empty) collection of (non-empty) sets, you can create a new set by taking one element from each of those and making a new set with them. A way of visualizing the process is through a function, whose input is each of the sets A in the collection and whose output, f(A), is an element a ∈ A.
I say it is pretty intuitive because if you are thinking about finite sets, it is automatically obvious that the process is possible and the function exists. But there’s the catch: will this rule also hold for infinite sets? There’s no reason why it would have to. I mean, it makes superficial sense, but lots of properties of mathematical infinity don’t (like ‘there’s different sizes of infinity’, or ‘some proper subsets of infinite sets have (in a technical sense) as many elements as the mother set itself’). AoC is required for extending the rule to infinite sets. Using it yields interesting mathematics, it seems, and also some paradoxes (I’m talking about you, Banach-Tarski!).
Anyway. The chapter contains a couple of exercises I’ve given a shot at:
If {Xi} is a finite sequence of sets, for i in n, say, then a necessary and sufficient condition that their Cartesian product be empty is that at least one of them be empty. The assertion is easy to prove by induction on n.
The book also says that case n = 0 leads to a slippery argument about the empty function, so I’ll start with n=1 and go back to the zeroth case later.
We start an n=1. In this case, {Xi} only contains one set, X1. Now X1 is either non-empty or empty. If it is non-empty, it contains at least one element, x1. This means its Cartesian Product of X1 is itself, as there are no proper tuples except the elements xi of X1. Now, if X1 is empty, then there is one empty set in the sequence (the only one there is) and indeed, the Cartesian Product is empty, as there's no element in X1 that could be in the Cartesian Product.
Assume true for k, show that follows for k+1. So we have {Xk}, and by the induction hypothesis, if one of its sets is empty, the Cartesian product of them (X1 x X2.... x Xk) also is. If we add another set, Xk+1, to the collection, it doesn't matter if the new set is empty or not: we already have an empty one in the collection, so we still cannot make a Cartesian Product.
What if none of the sets in {Xk} is empty? Then it all falls on the Xk+1 we add to the collection. If the new set is not empty, we can obviously make a Cartesian Product, but if it *is* empty, then the Cartesian product would fail (it cannot select any x in Xk+1 for there are none), so it is still the case that the Cartesian product of Xk+1 sets is empty if at least one of them is empty.
Now let’s go back to the case n=0. In this case, it is deeply anti-intuitive that there could be a Cartesian Product at all. We have a collection with no sets in it (an empty collection), so there are no elements xi that could conform a Cartesian Product; one would imagine it would follow that such a Cartesian Product would be empty, but it seems this is wrong.
I don’t remember if Halmos formulated it as such, but another definition of a Cartesian Product is as the set of all functions f with domain in the index set I and range sets X1, X2, X3 … of the collection. As I = ∅, there is only one function from ∅ to the collection X0}: the empty function. So the Cartesian Product in this case can never be empty, making the statement for n=0 true (i.e., the Cartesian Product is not empty, so the condition cannot apply meaningfully. And besides, the clause "at least one set is empty" is vacuously true, as there are no sets in the collection to contradict this).
As a sample (and an exercise) we mention the assertion that every relation includes a function with the same domain. Another sample: if 𝒞 is a collection of pairwise disjoint non-empty sets, then there exists a set A such that A ∩ C is a singleton for each C in 𝒞. Both these assertions are among the many known to be equivalent to the axiom of choice.
Let’s start with the first case: every relation includes a function with the same domain. A relation R was explained in chapter 7 as a set of ordered pairs (with sets X and Y forming its projections, such that for any element (x,y)∈R, x∈X and y∈Y), and a function F was explained in chapter 8, as a relation between two sets with an extra uniqueness condition, such that if (x,y)∈F, it is not possible for (x,y’)∈F if y≠y’. Also, if we consider the Cartesian Product XxY, then clearly both R and F are subsets of it.
Assume some arbitrary relation R. As such, its elements (ordered pairs) are also elements of the Cartesian Product XxY, and together form a subset R of XxY. Now, for each element of this subset, one can check if the uniqueness condition for functions stated previously holds, and we can generate a subset of R (and also a subset of XxY) whose elements satisfy this condition. Such a subset would be a function F with the same domain as R. The reason why this is equivalent to the AoC is as follows: imagine a partition of R such that elements in the same partition share the same x∈X. This partition has generated a collection of sets. Now we can apply a choice function to the collection, such that for each set in the collection it picks just one of its elements -one pair only out of all the possible ones in the set-. The resulting set that is generated is a function F with the same domain as R.
As for the second case: As 𝒞 is a collection of pairwise disjoint non-empty sets, any sets C1,C2,C3… do not share any elements in common. Now, assume a choice function f, with domain 𝒞. This function can select one element c1∈C1, one element c2∈C2, one element c3∈C3 and so on. Each of these elements forms a set A = {c1, c2, c3…}. Now, if you check what A ∩ C is for each C in 𝒞, it is clear that each of those intersections can, by the construction, only include a singleton element for each: A ∩ C1 = {c1}, A ∩ C2 = {c2}, A ∩ C3 = {c3} and so on. This shows that our statement is indeed equivalent to the AoC.
