Prev: Solution needed
Next: Quaternions as a representation of four-vectors
From: David Libert on 4 Sep 2007 02:31
On Sep 2, 4:35 am, Butch Malahide <fred.gal...(a)gmail.com> wrote:
> On Aug 29, 7:40 pm, "Jim Heckman" <rot13(reply-to)@none.invalid>
> wrote:
>
> > Can ZF alone prove that every totally ordered set has a cofinal
> > well-ordered subset, or does that require AC? (Typically done by
> > applying Zorn's Lemma to the set of well-ordered subsets, ordered
> > by continuation.)
>
> I'm no expert, but I'd bet that without AC you'd have a hard time
> proving even that every set of real numbers (usual ordering) has a
> cofinal well-ordered subset.

Yes, apparently as you suspected this is an independence result.

On page 138 of my edition of Paul Cohen's _Set Theory and the
Continuum Hypothesis_ he has:

THEOREM 1. N is a model for ZF, in which the the set T is a subset
of P(omega) = C, such that T is infinite and yet contains no
countable subset.

A set is defined to be Dedekind infinite if it bijective with some
proper subset of itself. ZF proves a set is Dedekind infinite iff
it contains an infinite countable subset.

A set is defined to be a Dedekind set iff it is infiinite but
Dedekind finite (which means not Dedekind infinite).

So apparently Cohen is getting a ZF model with a Dedekind subset of
P(omega).

Being Dedekind is invariant under set isomorphism, so this also gets
a Dedekind subset of the usual mathematicians reals (as opposed to
logicians calling P(omega) "the reals") .

So a Dedekind set of reals would certainly have no cofinal well-
ordered subset.

This is surprising to me, to get Dedkind for a set of reals, on the
surface a tronger property than having no well-ordered cofinal subset.

This was Cohen's first ~AC model in the book. After that he gave
another model, with countable choice among pair sets failing.

--
David Libert

From: David Libert on 4 Sep 2007 02:53
On Sep 2, 4:50 am, Butch Malahide <fred.gal...(a)gmail.com> wrote:
> On Sep 2, 2:27 am, "Jim Heckman" <rot13(reply-to)@none.invalid> wrote:
>
>
>
> > On 29-Aug-2007, hru...(a)odds.stat.purdue.edu (Herman Rubin)
> > wrote in message <fb573c$4...(a)odds.stat.purdue.edu>:
>
> > > In article <13dc4f7iafuj...(a)corp.supernews.com>,
> > > Jim Heckman <weu_rznvy-hfr...(a)lnubb.pbz.invalid> wrote:
>
> > > >Can ZF alone prove that every totally ordered set has a cofinal
> > > >well-ordered subset, or does that require AC? (Typically done by
> > > >applying Zorn's Lemma to the set of well-ordered subsets, ordered
> > > >by continuation.)
>
> > > It is at least false in the Mostowski model in which the
> > > universe is linearly ordered, but all well-ordered subsets
> > > of the set of individuals aren finite. In the metamathematical
> > > way of looking at the model, the individuals look like the
> > > rationals.
>
> > > The rational ordering does hold in the model, but for example
> > > the subset which is the integers does not exist in the model.
>
> > Thanks. I was hoping for something more elementary, though, since I
> > know next to nothing about model theory. My naive-set-theory
> > intuition is having trouble seeing how any model of ZF can fail to
> > have infinite (within the model) well-ordered sets -- starting with
> > omega.

You are right, ZF alone gets the familiar facts about the existence
of von Neumann ordinals. And also getting well-orderings of high
order type but low set theortic rank (below the rank of the
corresponding von Neumann ordinal) by equivalence classes (by order
type) or well orderings of an earlier set, is available in ZF, the
usual ZFC proofs are not using any AC even in their simplesty
presentation so it requires no work to get back to ZF.

So all the usual well-orderings are around in the ZF model.

Instead what this model is doing is providing another set, which is
lionearly ordered but has no inifinite well-ordered subsets. Off to
the side the usual well-ordered sets are around with their familiar
properties.


> I believe the models Professor Rubin is referring to are not models of
> ZF. They are models of a set theory which, unlike ZF, allows the
> existence of so-called individuals (aka atoms or urelements), objects
> which are not sets. Omega is an infinite well-ordered set, but it's
> not a set of individuals, it's a set of sets.

Yes, Professor Rubin is writing about a Fraenkel Mostowski model, so
a model if ZFU instead of ZF, allowing atoms. And as noted, it is the
set off atoms that has the strange properties, and omega is its usual
self.

On the other, this proof can be combined with forcing, to get an
actual similar ZF model, in which there is a pure set acting like the
set of atoms just mentioned in the Fraenkel Mostowski model. In fact
this is just an application of the Jech Sochar transfer theorem. The
reason this goes through, is the property in question, having only
finite well-orderable subsets, is expressible relatavised to a
bounded set theoretic rank.

See discussion about these general points in

[1] David Libert July 6 , 2000 "Cohen symmetric
choiceless ZF models"
http://groups.google.com/group/sci.logic/msg/b4271c2585d2f1e5

--
David Libert


From: Butch Malahide on 4 Sep 2007 16:48
On Sep 4, 1:31 am, David Libert <libert.da...(a)gmail.com> wrote:
> On Sep 2, 4:35 am, Butch Malahide <fred.gal...(a)gmail.com> wrote:
>
> > On Aug 29, 7:40 pm, "Jim Heckman" <rot13(reply-to)@none.invalid>
> > wrote:
>
> > > Can ZF alone prove that every totally ordered set has a cofinal
> > > well-ordered subset, or does that require AC? (Typically done by
> > > applying Zorn's Lemma to the set of well-ordered subsets, ordered
> > > by continuation.)
>
> > I'm no expert, but I'd bet that without AC you'd have a hard time
> > proving even that every set of real numbers (usual ordering) has a
> > cofinal well-ordered subset.
>
> Yes, apparently as you suspected this is an independence result.
>
> On page 138 of my edition of Paul Cohen's _Set Theory and the
> Continuum Hypothesis_ he has:
>
> THEOREM 1. N is a model for ZF, in which the the set T is a subset
> of P(omega) = C, such that T is infinite and yet contains no
> countable subset.
>
> A set is defined to be Dedekind infinite if it bijective with some
> proper subset of itself. ZF proves a set is Dedekind infinite iff
> it contains an infinite countable subset.
>
> A set is defined to be a Dedekind set iff it is infiinite but
> Dedekind finite (which means not Dedekind infinite).
>
> So apparently Cohen is getting a ZF model with a Dedekind subset of
> P(omega).
>
> Being Dedekind is invariant under set isomorphism, so this also gets
> a Dedekind subset of the usual mathematicians reals (as opposed to
> logicians calling P(omega) "the reals") .
>
> So a Dedekind set of reals would certainly have no cofinal well-
> ordered subset.

Except that a Dedekind set of reals could have a greatest element. Of
course, by removing a finite number of elements from the top, you
arrive at a Dedekind set with no greatest element, hence no cofinal
well-ordered subset.

From: David Libert on 4 Sep 2007 17:40
On Sep 4, 4:48 pm, Butch Malahide <fred.gal...(a)gmail.com> wrote:
> On Sep 4, 1:31 am, David Libert <libert.da...(a)gmail.com> wrote:
>
>
>
> > On Sep 2, 4:35 am, Butch Malahide <fred.gal...(a)gmail.com> wrote:
>
> > > On Aug 29, 7:40 pm, "Jim Heckman" <rot13(reply-to)@none.invalid>
> > > wrote:
>
> > > > Can ZF alone prove that every totally ordered set has a cofinal
> > > > well-ordered subset, or does that require AC? (Typically done by
> > > > applying Zorn's Lemma to the set of well-ordered subsets, ordered
> > > > by continuation.)
>
> > > I'm no expert, but I'd bet that without AC you'd have a hard time
> > > proving even that every set of real numbers (usual ordering) has a
> > > cofinal well-ordered subset.
>
> > Yes, apparently as you suspected this is an independence result.
>
> > On page 138 of my edition of Paul Cohen's _Set Theory and the
> > Continuum Hypothesis_ he has:
>
> > THEOREM 1. N is a model for ZF, in which the the set T is a subset
> > of P(omega) = C, such that T is infinite and yet contains no
> > countable subset.
>
> > A set is defined to be Dedekind infinite if it bijective with some
> > proper subset of itself. ZF proves a set is Dedekind infinite iff
> > it contains an infinite countable subset.
>
> > A set is defined to be a Dedekind set iff it is infiinite but
> > Dedekind finite (which means not Dedekind infinite).
>
> > So apparently Cohen is getting a ZF model with a Dedekind subset of
> > P(omega).
>
> > Being Dedekind is invariant under set isomorphism, so this also gets
> > a Dedekind subset of the usual mathematicians reals (as opposed to
> > logicians calling P(omega) "the reals") .
>
> > So a Dedekind set of reals would certainly have no cofinal well-
> > ordered subset.
>
> Except that a Dedekind set of reals could have a greatest element. Of
> course, by removing a finite number of elements from the top, you
> arrive at a Dedekind set with no greatest element, hence no cofinal
> well-ordered subset.

Ok.

And from the abstract statement, namely a Dedekind set of reals,
that is a possibility.

I hadn't mentioned it, but Cohen's construction produces a set of
reals (even when slide back to the real reals by ground model
isopmorphims P(omega) <-> R ) with no greatest elelment in the
usual R ordering.

--
David Libert

First  |  Prev  | 
Pages: 1 2
Prev: Solution needed
Next: Quaternions as a representation of four-vectors