Thomas Jech: The Axiom of Choice
This chapter discusses a theorem by Jech on a finitary version of the Axiom of Choice. A bootstrapping trick for constructing finite choice functions may have other applications in theory.
- PDF / 241,334 Bytes
- 3 Pages / 441 x 666 pts Page_size
- 39 Downloads / 286 Views
37
Thomas Jech is a set theorist and logician, who among many other things wrote a classic book on the Axiom of Choice (AC). I strongly recommend this book for its wonderfully lucid explanation of many aspects of AC—including the results by Kurt Gödel and Paul Cohen on the independence of AC from ZF set theory. We will discuss an old result about the famous axiom. It concerns a finitary version of AC, and may be related to some of our problems in complexity theory. In any event it is a quite neat result, in my opinion. At the 2010 Association of Symbolic Logic meeting, hosted by George Washington University in Washington, DC, a group of us went to dinner after our session on complexity theory. As usual we discussed many things during dinner: who was hiring, who was moving, P = NP, but somehow the conversation hit upon the AC. I told the group that I recalled vaguely a result on the AC for finite sets. No one seemed to be aware of such a result. I was a bit embarrassed, since I could not recall the exact statement of the theorem, but did recall it concerned choice on finite sets. We then moved onto other topics. This is my attempt to make up for forgetting these pretty theorems about the AC for finite sets.
37.1
Finite Choice
Recall the AC is all about choice functions, since we are computer scientists we will only consider choices among finite objects. Consider a family F of sets each of cardinality exactly n. The statement Cn says every such family has a choice function: More precisely, there is a function s from sets A ∈ F to elements so that s(A) ∈ A for every set A. Jech gives several theorems, but the most interesting ones solve the following problem: when does Cm imply Cn ? Here are two key examples: Theorem 37.1 The statement C2 implies C4 . R.J. Lipton, K.W. Regan, People, Problems, and Proofs, DOI 10.1007/978-3-642-41422-0_37, © Springer-Verlag Berlin Heidelberg 2013
195
196
37
Thomas Jech: The Axiom of Choice
Theorem 37.2 The statement C2 does not imply C3 . What I find interesting is the non-monotone nature: the relationship from Cm to Cn is not simple. Let me prove the first, C2 implies C4 . I will follow Jech’s proof almost exactly. It is important to understand what we are allowed to do with sets: (1) Given a finite set A we can tell the cardinality of the set. (2) Given a set A and B we can form the set difference A − B. (3) Given any set A = {a, b} of two elements, we have a universal function g that is a choice function: g(A) = x, where x = a or x = b. The last property follows from the assumption C2 . We now assume we have a family F of four-element sets, and are looking for a way to select among any four elements. We will construct the choice function using the above properties—the existence of g is critical. Let A be in the family F . There are six two-element subsets of A. For every a ∈ A, let q(a) = Number of pairs {a, b} ⊂ A such that g {a, b} = a. Obviously q(a) cannot be the same for all a ∈ A: if all had q(a) = 1 this would be too few choices, if all had q(a) = 2 this would b
Data Loading...
