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     (ah170@freenet.carleton.ca)
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