From: ah170@FreeNet.Carleton.CA (David Libert) Subject: Re: Axiom of choice question Date: 20 Oct 1999 07:27:29 GMT Newsgroups: sci.math Keywords: Cohen's models showing independence of Axiom of Choice David Libert (ah170@FreeNet.Carleton.CA) writes: > > Paul Cohen in _Set Theory and the Continuum Hypothesis_ gives a > similar model to the above, just adjusted enough to allow ~AC. Assuming > ZF is consistent Cohen constructs a ZF model containing a countable > sequence of two element sets, where each element of the 2 element sets is > a countable set of reals. > > To express this in deceptive notation he gives a sequence > <{Ui, Vi}| i in omega> , a counable sequence of 2 element sets, where > each Ui and Vi are countable sets of reals. This notation is deceptive > though, because it suggests a method to uniformly split the 2 element > sets into the "U" and "V" members. > > In Cohen's model, this countable sequence has no choice function. So > ie, my comments above about U vs V notation deceptive. > > So ie: countably many binary choices can fail. Not quite. Everything above is ok except the original Cohen construction does not have the Ui and Vi countable as I wrote above. Toward discussing the properties of the Ui and Vi 's in Cohen's construction I will review notions of finiteness. The usual definition of finiteness is having cardinality a member of omega, where omega is defined to be the smallest set with the empty set as member and closed under the ordinal successor operation. The axiom of infinity asserts there is a set with member empty set and closed under this operation. From the existence of such a set other axioms of ZF imply there is a smallest one, omega is defined to be this set. This definition of finiteness could be more verbosely described as inductive finiteness, because it is exactly the definition that supports proofs by mathematical (as opposed to transfinite) induction. The schematum of induction for arbitrary formulas of ZF is provable for this definition of finiteness. Also if any other definition F() supports this schematum of induction, this F induction schematum can be used to prove by induction that F is equivalent to the definition above of finiteness. There is another approach to defining finiteness. Dedekind proposed a set be defined to be infinite if it is bijective with a proper subset of itself and defined to be finite otherwise. Now that the main definition of finiteness has settled on inductive finiteness as I described above, we refer to Dedekind's definitions as Dedekind infinite and Dedekind finite. In ZF a proof by induction shows inductive finite -> Dedekind finite. On the other hand ZFC proves Dedekind finite -> inductive finite, so in ZFC the two definitions of finiteness are equivalent. Back in ZF the case still not ruled out is an infinite (ie inductive infinite) but Dedekind finite set. Such sets will be called Dedekind sets. So ZFC proves there are no Dedekind sets, and so far Dedekind sets are not yet ruled out in ZF from what I have written so far. ZF proves some equivalences of Dedekind finite: A is Dedekind finite <-> A has no countably infinite subsets <-> omega cannot inject into A <-> every well-orderable subset of A is finite. So a Dedekind set is an infinite set having all those strange properties. In particular, no Dedekind set can be well-ordered, and so cannot be countable. Cohen's first ~AC model in his book is a ZF model having a Dedekind set of reals. Cohen was the first to construct any ~AC ZF model, and this particular model is the first and simplest in his book. This is also the first proof that the two definitions of finiteness are not equivalent over ZF. Cohen's second ~AC model in the book is the model I was discussing last post with the Ui and Vi 's : ie a failure of countably many binary choices. As I understand Cohen's second construction now, each Ui and Vi is a Dedekind set of reals, contrary my claim last post that these sets are each countable. I think Cohen's second construction can be modified to give the result I first claimed: Ui and Vi each countable. I will outline the modifications to Cohen's construction which I think do this. The general method of construction of all these models (Cohen's two and my modification and many other ~AC constructions) is Cohen's method of symmetric models. To say what this is in broad outline, Cohen defines a method of construction for a ZFC model. He also has a group which acts on this construction method. He can define a subclass of the constructed ZFC model consisting of parts suitably symmetric with respect to the action of the group on the construction process of the enveloping ZFC model. Such subclasses will always still satisfy ZF, but AC is lost in passing to this subclass. For example, choice functions existing in the enveloping ZFC model will not be suitably symmetric and fail to enter the submodel. The trick in constructing these symmetric models is to define the correct construction of the outer ZFC model and to choose a definition of the group and the group action to arrange that the symmetric submodel has the desired properties. In particular arrange that things you wanted in the model will be sufficiently symmetric and those you wanted to exclude won't be symmetric. In Cohen's second construction there are cross effects between the Ui 's and Vi 's, but ignoring that for a moment and just considering what the group action does on Ui 's and Vi 's in isolation, it turns out each is like a copy of the single Dedekind set Cohen created in the first construction. This is why all the Ui and Vi 's end up as Dedekind sets in Cohen's second construction. The construction of the enveloping ZFC model involves making labels that will denote elements of the eventually constructed ZFC model. For example for Cohen's second model, we have a distinct label for each Ui and each Vi. We also make a countable list of labels of the respective elements of each Ui and Vi. So Ui = {a_i,j | j in omega}, Vi = {b_i,j | j in omega}. Each Ui and Vi has countably many labels naming all its elements, and so in the first outer ZFC model constructed these are each countable sets. This was how I mistakenly thought these were countable last article. The point is, Cohen's original 2nd model puts so many symmetries among the a_i,j1 and a_i,j2 's for example that any map from omega onto the Ui members is not symmetric and is left out of the final inner symmetric ZF model. This is how these sets end up as Dedekind in the symmetric model. Specifically considering the subgroup of Cohen's orginal group which is the identity outide of Ui and maps Ui to itself, the group we get is arbitrary permutations on Ui. The Ui members are so symmetric they can't be distinguished by a listing from omega. To fix this problem for a modified version of the construction, we take a different group and group action. If we want something to end up in the symmetric model, like for example a map from omega onto Ui, we arrange that the group action respects this object. So for the modified construction (to make the Ui and Vi 's countable), we make the labels listing Ui and Vi members be indexed by Z the integers instead of omega as in Cohen's. So Ui = {a_i,j | j in Z} and Vi = {b_i,j | j in Z}, for i in omega. In Cohen's version each permutation of labels in the group was required for all but finitely many i to fix all Ui and Vi 's and their members. Each permutation was allowed to be nonidentity on finitely many i, namely for one such i to either fix Ui and Vi and arbitrarily permute Ui members among themselves and Vi members among themselves, or alternatively to interchange Ui and Vi and to send Ui members bijectively to Vi members and Vi members bijectively by a possibly different bijection to Ui members. So on the Ui and Vi labels it either flipped pairs or not, and on the labels representing members it is an arbitrary permutation preserveing membership in Ui or Vi acording to its action on Ui or Vi. The fact that some group elements can flip within pairs makes choice functions on the pairs too assymmetric and gets the basic desired failure of choce of pairs. The fact that within the the Ui and Vi 's on members there are arbitrary permutations corresponds to the earlier Cohen construction of one Dedikind set. So for my modification we have the same conditions as Cohen on Ui and Vi labels. Regarding the a_i,j & b_i,j labels, as before I require membership in Ui or Vi be respected, so assign consistently with whether Ui and Vi were fixed or flipped. If they were fixed though, I require that within Ui the permutation act on the member labels by shifting the Z indexes by a constant, instead of performing an arbitrary permutation. Similarly for Vi. If Ui and Vi flipped, a_i,j 's will go to b_i,k 's, but again by a constant shift of the Z ordered indices: a_i,j |-> b_i,j+c the same integer constant c for all the j's for that fixed i. The linear ordering of Ui elements isomorphically to Z induced by the ordering of indices of labels is preserved by all permutations of this group, and so this linear ordering will survive into the symmetric inner model. Cohen's version allowing wild permutations on these elements would lose these linear orderings at this point. So each Ui and Vi has a linear ordering isomorphic to Z in the symmetric model, and so is countable. On the other hand we still have flip permutations of Ui and Vi, so as from Cohen's original version we end up that there are no choice functions on the sequence of doubletons. Another perspective on this. The Ui and Vi 's each have bijections to omega, but the fact that there are those group elements sliding these bijections back and forth along Z, prevents amalgamating across the Ui and Vi 's to pick one such bijection for each Ui or Vi. If this were possible the usual proof that aleph_0 ^2 = aleph_0 could be completed to get the union of Ui and Vi 's is countable, hence the sequence of pairs has a choice set. -- David Libert ( 1. I used to be conceited but now I am perfect. 2. "So self-quoting doesn't seem so bad." -- David Libert 3. "So don't be a morron." -- Marek Drobnik bd308 rhetorical salvo IRC sig