How many ordinals?
William Elliot
1) without axiom of infinite, without axiom of choice
2) without axiom of infinite, with axiom of choice
3) with axiom of infinite, without axiom of choice
4) with axiom of infinite, with axiom of choice?
Answers?
1) All the finite ordinals only.
2) ?
3) ?
4) ?
(As many as you like and more than you can ever use. ;-)
Riddle of the day.
How much faster can cardinals count than ordinals can?
Dave L. Renfro
> Riddle of the day.
> How much faster can cardinals count than ordinals can?
I'd say the ordinals are only faster for (relatively) short
periods and, as you get farther out along the ordinals, these
intervals where the ordinals are ahead of the cardinals become
blips that can be ignored.
The mapping beta |--> aleph_beta that takes the beta'th
ordinal to the beta'th cardinal is a normal function
(on a sufficiently large initial segment of the ordinals),
and hence has fixed points. In fact, it's fixed points
are order-isomorphic to every initial segment of the
ordinals, and so before too long it's fixed points start
to look like the limit ordinals when you're out around
the first epsilon number. Moreover, the fixed points have
fixed points as well, and these 2'nd order fixed points
have the same behavior. Same for the 3'rd order fixed points,
and so on, even for the omega'th order fixed points (use a
countable intersection of clubs to get them) and beyond.
After a while, the epsilon_0'th order fixed points start
to look like the limit ordinals out around epsilon_0. And
this is only the beginning, because we can jump past this
pedestrian pace of iterating the fixed point operation by
taking diagonal intersections (look it up), and on and on
and on ...
See the beginning of Section 4.33 in Azriel Levy's "Basic
Set Theory", Dover Publications, 1979/2002.
Use 'Search in this book' = "omitted by diagonal intersection"
http://books.google.com/books?vid=ISBN0486420795
I also posted this in sci.math once, but it seems to only
be in the Math Forum archive, not the google archive.
(Also, my URL's and some other things seem not to have
been transmitted faithfully.)
Thread: "Different size infinities?"
Date: October 29, 2004
http://mathforum.org/kb/thread.jspa?messageID=3414869
Dave L. Renfro
Jonathan Hoyle
> What and/or how many ordinals are given by ZFC
ZFC doesn't "give" ordinals. There are many, many models of Set Theory
consistent with ZFC. You are confusing the model with the theory.
For example, the existence of inaccessible cardinals is undecidable in
ZFC. So you can have a model in which the V = V_theta, where theta is
the smallest inaccessible cardinal. That is to say, in the universe of
V_theta, the only sets are those which have accessible cardinality.
Anything larger cannot exist as a set.
On the other hand, you can have a model of ZFC which contains
inaccessible cardinals, say V= V_kappa where kappa is the smallest
hyper-inaccessible cardinal. Here you can have sets which are of
inaccessible cardinality. Or you can choose kappa = to a Mahlo
cardinal, or a measurable cardinal, or Shelah, or huge, or all the way
up the line.
All of these models are consistent with ZFC, or at least not proven to
be inconsistent with it. There does not appear to be an upper limit on
large cardinals, although as they get bigger, they border on breaking
out of the ZFC consistency shell. For example, the largest cardinals
known currently are Reinhardt cardinals which are inconsistent with the
Axiom of Choice, and thus cannot be a ZFC model. The largest known
after them are the "rank-into-rank" cardinals, which have not yet been
shown to be inconsistent with ZFC.
Chip Eastham
William Elliot wrote:
> What and/or how many ordinals are given by ZFC
>
> 1) without axiom of infinite, without axiom of choice
>
> 2) without axiom of infinite, with axiom of choice
>
> 3) with axiom of infinite, without axiom of choice
>
> 4) with axiom of infinite, with axiom of choice?
>
> Answers?
> 1) All the finite ordinals only.
> 2) ?
> 3) ?
> 4) ?
> (As many as you like and more than you can ever use. ;-)
I suspect you may be interested in a result provable in
ZFS without axiom of infinity (the C stands for Choice).
Friedrich Hartogs proved a "lemma" on the way to
showing the Axiom of Choice is equivalent to the
trichotomy principle for cardinals. Given any set
X, there is of course the cardinal number of X,
which is naively the equivalence class of sets
equinumerous with X. Ordinal numbers may be
considered either as equivalences on well-orders
or (in the von Neumann approach) hereditarily
transitive sets (the "transitive" meaning here
that every member of a member is a member
of a transitive set).
What Hartogs showed is that, without assuming
the Axiom of Choice (or Axiom of Infinity, for that
matter), there exists a least ordinal which is not
"injective" to X, i.e. not less than or equal to X
in cardinality, for any set X whatever.
Without trichotomy, of course, we cannot claim
that this is the same as having cardinality greater
than or equal to X. But as trichotomy establishes
that, it establishes that any X can be well-ordered.
Hence the Axiom of Choice is equivalent to the
principle of trichotomy for cardinal numbers (the
other direction being trivial).
Regarding the various "subsystems" of ZFC you
propose, I would highlight one implication of
Hartogs lemma concerning the assumption of
the Axiom of Infinity but not Axiom of Choice.
Given X as little-omega, there must be an ordinal
Y which is not injective to X. But since both X
and Y are well-ordered, by transfinite induction
we must have |X| strictly less than |Y|. That is,
there exists a well-orderable cardinal strictly
beyond the countable little-omega. Of course
the argument can be repeated with X replaced
by Y, to get a chain of strictly increasing well-
orderable cardinals.
regards, chip
Stephen J. Herschkorn
>What and/or how many ordinals are given by ZFC
>
>
I assume you mean in ZF - Infinity. My answers are actually for ZF -
Inifinty - Foundation; I strongly suspect that Foundation has no effect
here.
>1) without axiom of infinite, without axiom of choice
>
>2) without axiom of infinite, with axiom of choice
>
>3) with axiom of infinite, without axiom of choice
>
>4) with axiom of infinite, with axiom of choice?
>
>Answers?
>1) All the finite ordinals only.
>2) ?
>3) ?
>4) ?
> (As many as you like and more than you can ever use. ;-)
>
Regarding (3) and (4), with Infinity, you get the same class of
ordinals with or without AC. You and I discussed this here some time
ago, William, though I cannot track down the thread right now. There
are other such threads, however.
Regarding (2), "All sets are finite" is consistent with ZFC -
Infinity. See Kunen, p. 123. In fact, isn't AC a theorem of ZF -
Infinity + "All ordinals are finite" ?
--
Stephen J. Herschkorn sjher...@netscape.net
Math Tutor on the Internet and in Central New Jersey and Manhattan
William Elliot
> William Elliot wrote (in part):
> > Riddle of the day.
> > How much faster can cardinals count than ordinals can?
> I'd say the ordinals are only faster for (relatively) short
> periods and, as you get farther out along the ordinals, these
> intervals where the ordinals are ahead of the cardinals become
> blips that can be ignored.
Nay, the cardinals go 1,2,3,.. aleph_0, aleph_1. While the
ordinals go 1,2,3,.. omega_0, omega_0 + 1, ... omega_0 * 2 ...
So at aleph_0 = omega_0, they're neck and neck but then the cardinals jump
off to aleph_1 while the ordinals take forever and a half to get to
omega_1 = aleph_1. While they're still getting to the edge of the solar
system, the cardinals have raced off aleph_1, aleph_2,... aleph_omega0 to
the nearest stars and beyond to aleph_omega1 at the edge of the galaxy.
> The mapping beta |--> aleph_beta that takes the beta'th ordinal to
> the beta'th cardinal is a normal function (on a sufficiently large
> initial segment of the ordinals), and hence has fixed points. In
> fact, it's fixed points are order-isomorphic to every initial segment
> of the ordinals, and so before too long it's fixed points start to
> look like the limit ordinals when you're out around the first epsilon
Isn't that first fixed point aleph_omega_omega_...?
So while the ordinals are still in a race with Voygers 1 and 2 to get to
the nearby stars, the cardinals have reached the speed of light.
> number. Moreover, the fixed points have fixed points as well, and
> these 2'nd order fixed points have the same behavior. Same for the
> 3'rd order fixed points, and so on, even for the omega'th order fixed
> points (use a countable intersection of clubs to get them) and
> beyond. After a while, the epsilon_0'th order fixed points start to
> look like the limit ordinals out around epsilon_0. And this is only
> the beginning, because we can jump past this pedestrian pace of
> iterating the fixed point operation by taking diagonal intersections
> (look it up), and on and on and on ...
What if I prefer to see nothing beyond the speed of light, to leave the
intangible untouchable inaccessibles in the dungon of their own
remoteness?
> See the beginning of Section 4.33 in Azriel Levy's "Basic
> Set Theory", Dover Publications, 1979/2002.
> Use 'Search in this book' = "omitted by diagonal intersection"
> http://books.google.com/books?vid=ISBN0486420795
> I also posted this in sci.math once, but it seems to only
> be in the Math Forum archive, not the google archive.
> (Also, my URL's and some other things seem not to have
> been transmitted faithfully.)
> Thread: "Different size infinities?"
> Date: October 29, 2004
> http://mathforum.org/kb/thread.jspa?messageID=3414869
----
William Elliot
> For example, the existence of inaccessible cardinals is undecidable
> in ZFC. So you can have a model in which the V = V_theta, where
> theta is the smallest inaccessible cardinal. That is to say, in the
> universe of V_theta, the only sets are those which have accessible
> cardinality. Anything larger cannot exist as a set.
> On the other hand, you can have a model of ZFC which contains
> inaccessible cardinals, say V= V_kappa where kappa is the smallest
> hyper-inaccessible cardinal. Here you can have sets which are of
> inaccessible cardinality. Or you can choose kappa = to a Mahlo
> cardinal, or a measurable cardinal, or Shelah, or huge, or all the
> way up the line.
As I said, as many as you wish and more than you can ever use.
But you are dreaming for by the Loewenheim-Skolem paradox,
it's just a countable model.
> All of these models are consistent with ZFC, or at least not proven
> to be inconsistent with it. There does not appear to be an upper
> limit on large cardinals, although as they get bigger, they border on
> breaking out of the ZFC consistency shell. For example, the largest
> cardinals known currently are Reinhardt cardinals which are
> inconsistent with the Axiom of Choice, and thus cannot be a ZFC
> model. The largest known after them are the "rank-into-rank"
> cardinals, which have not yet been shown to be inconsistent with
> ZFC.
As I recall V = L, assuming the universe of sets is constructable
implies AxC. Does it not deny existence of inaccessibles? What
does it do regarding CH and GCH, the continuum hypothesis?
----
William Elliot
> William Elliot wrote:
> >What and/or how many ordinals are given by ZFC
>
> I assume you mean in ZF - Infinity. My answers are actually for ZF
> - Inifinty - Foundation; I strongly suspect that Foundation has no
> effect here.
> >1) without axiom of infinite, without axiom of choice
>
> >2) without axiom of infinite, with axiom of choice
>
> >3) with axiom of infinite, without axiom of choice
>
> >4) with axiom of infinite, with axiom of choice?
>
> >Answers?
> >1) All the finite ordinals only.
> >2) ?
> >3) ?
> >4) ?
> > (As many as you like and more than you can ever use. ;-)
> Regarding (3) and (4), with Infinity, you get the same class of
> ordinals with or without AC. You and I discussed this here some
> time ago, William, though I cannot track down the thread right now.
> There are other such threads, however.
Not that I recall, nor have I watched closely the construction of the
ordinals to say for sure that AxC wasn't used.
> Regarding (2), "All sets are finite" is consistent with ZFC -
> Infinity. See Kunen, p. 123.
I'm shocked.
> In fact, isn't AC a theorem of ZF -
> Infinity + "All ordinals are finite" ?
I'd think it'd be a theorem of ZF + all sets are finite.
or of ZF + all ordinals are finite
----
Jonathan Hoyle
> it's just a countable model.
I don't understand this sentence (nor is it grammatically correct).
Could you rephrase, please?
> As I recall V = L, assuming the universe of sets is constructable
> implies AxC. Does it not deny existence of inaccessibles? What
> does it do regarding CH and GCH, the continuum hypothesis?
If you add V=L to your set of axioms along with ZF, then AC and GCH are
theorems. Reasonably large cardinals do not exist in the constructible
universe. Measurable cardinals and even 0# do not. The smallest
inaccessible cardinal (I believe) is still consistent with ZF+(V=L).
And of course strongly inaccessible = weakly inaccessible in this
universe.
The main complaint most Set Theorists have with V=L is that it feels
needlessly confining. Denying the existence of sets which cannot be
constructed in its simple steps, although consistent, seems rather
artificial. Why make such a blatantly restrictive assumption? Those
who do tend to do so only because they want an easy way to its
conclusions, not because V=L is itself at all persuasive.
One important result of the Constructible Universe is that it's a
minimal inner model of ZFC, so you can't really get any smaller without
being isomorphic to it. Also, all constructible sets are definable
from the ordinals, which is nice (but again, implying a too simplistic
world).
Richard Tobin
Jonathan Hoyle <jonh...@mac.com> wrote:
>> But you are dreaming for by the Loewenheim-Skolem paradox,
>> it's just a countable model.
>I don't understand this sentence (nor is it grammatically correct).
It's grammatically correct if you interpret "for" as "because".
-- Richard
Jonathan Hoyle
Stephen J. Herschkorn wrote:
> William Elliot wrote:
>
> >What and/or how many ordinals are given by ZFC
> >
> >
> I assume you mean in ZF - Infinity. My answers are actually for ZF -
> Inifinty - Foundation; I strongly suspect that Foundation has no effect
> here.
>
> >1) without axiom of infinite, without axiom of choice
> >
> >2) without axiom of infinite, with axiom of choice
> >
> >3) with axiom of infinite, without axiom of choice
> >
> >4) with axiom of infinite, with axiom of choice?
> >
> ordinals with or without AC. You and I discussed this here some time
> ago, William, though I cannot track down the thread right now. There
> are other such threads, however.
The main difference is that, with AC, you can always compare two
cardinals k1, k2 such that exactly one of these three statements is
true:
1) k1 < k2
2) k1 = k2
3) k1 > k2
Without AC, you can have two cardinals which are incomparable.
Chip Eastham
Jonathan Hoyle wrote:
> > As I recall V = L, assuming the universe of sets is constructable
> > implies AxC. Does it not deny existence of inaccessibles? What
> > does it do regarding CH and GCH, the continuum hypothesis?
>
> If you add V=L to your set of axioms along with ZF, then AC and GCH are
> theorems. Reasonably large cardinals do not exist in the constructible
> universe. Measurable cardinals and even 0# do not. The smallest
> inaccessible cardinal (I believe) is still consistent with ZF+(V=L).
> And of course strongly inaccessible = weakly inaccessible in this
> universe.
Yes, Gödel's 1940 paper was after all titled:
Consistency of the axiom of choice and of the generalized
continuum-hypothesis with the axioms of set theory
This is where he introduces the "V=L" internal model to
prove relative consistency of ZF + AC + GCH with ZF.
It's mentioned in the Wikipedia article on Kurt Gödel:
http://en.wikipedia.org/wiki/Godel
regards, chip
W. Dale Hall
William Elliot wrote:
> From: Dave L. Renfro <renf...@cmich.edu>
>
>>William Elliot wrote (in part):
>
>
>>>Riddle of the day.
>>>How much faster can cardinals count than ordinals can?
>
>
>>I'd say the ordinals are only faster for (relatively) short
>>periods and, as you get farther out along the ordinals, these
>>intervals where the ordinals are ahead of the cardinals become
>>blips that can be ignored.
>
>
> Nay, the cardinals go 1,2,3,.. aleph_0, aleph_1. While the
> ordinals go 1,2,3,.. omega_0, omega_0 + 1, ... omega_0 * 2 ...
>
> So at aleph_0 = omega_0, they're neck and neck but then the cardinals jump
> off to aleph_1 while the ordinals take forever and a half to get to
> omega_1 = aleph_1. While they're still getting to the edge of the solar
> system, the cardinals have raced off aleph_1, aleph_2,... aleph_omega0 to
> the nearest stars and beyond to aleph_omega1 at the edge of the galaxy.
>
I'm reminded of an old Sydney Harris cartoon I saw pasted on
some professor's office door in Madison while I was in graduate
school:
A man is lying in bed, face up, circles under
his open eyes, and a look of resignation.
The thought cloud above him shows sheep jumping over a fence.
The caption, "... Omega + 1, Omega + 2, ..."
... the rest deleted ...
Dale
W. Dale Hall
Jonathan Hoyle wrote:
>>But you are dreaming for by the Loewenheim-Skolem paradox,
>>it's just a countable model.
>
>
> I don't understand this sentence (nor is it grammatically correct).
> Could you rephrase, please?
>
>
I would have placed a comma:
But you are dreaming, for by the Loewenheim-
Skolem paradox, it's just a countable model.
That helps in the interpretation of the usage of "for"
On the other hand, I wouldn't have had the knowledge
to construct the sentence in the first place.
Dale.
Stephen J. Herschkorn
> > Infinity + "All ordinals are finite" ?
>
> I'd think it'd be a theorem of ZF + all sets are finite.
> or of ZF + all ordinals are finite
Anything is a theorem of ZF + all ordinals are finite, since Infinity
is one of the axioms of ZF Or was that your point?
William Elliot
Newsgroups: sci.math
Subject: Re: How many ordinals?
> I'm reminded of an old Sydney Harris cartoon I saw pasted on
> some professor's office door in Madison while I was in graduate
> school:
> A man is lying in bed, face up, circles under
> his open eyes, and a look of resignation.
> The thought cloud above him shows sheep jumping over a fence.
> The caption, "... Omega + 1, Omega + 2, ..."
Riddle of the day.
Why couldn't the mathematician fall asleep counting sheep?
The New Math
Bushwacky signs legislation prohibiting Axiom of Choice. Prochoice
mathematicians accuse 'educational president' of academic abortion.
----
William Elliot
Subject: Re: How many ordinals?
> William Elliot wrote:
> > From: Stephen J. Herschkorn <sjher...@netscape.net>
> >
> > > In fact, isn't AC a theorem of ZF -
> > > Infinity + "All ordinals are finite" ?
>
> > I'd think it'd be a theorem of ZF + all sets are finite.
> > or of ZF + all ordinals are finite
> Anything is a theorem of ZF + all ordinals are finite, since
> Infinity is one of the axioms of ZF Or was that your point?
Whoops, missed the ZF *-*
infinity +
----
William Elliot
Newsgroups: sci.math
Subject: Re: How many ordinals?
> > But you are dreaming for by the Loewenheim-Skolem paradox,
> > it's just a countable model.
> I don't understand this sentence (nor is it grammatically correct).
> Could you rephrase, please?
But you are dreaming, for by the Loewenheim-
Skolem paradox, it's just a countable model.
> > As I recall V = L, assuming the universe of sets is constructible
> > implies AxC. Does it not deny existence of inaccessibles? What
> > does it do regarding CH and GCH, the continuum hypothesis?
> If you add V=L to your set of axioms along with ZF, then AC and GCH
> are theorems. Reasonably large cardinals do not exist in the
> constructible universe. Measurable cardinals and even 0# do not.
0#? What a strange name. Then V = L also rids one of those pesky
Reihardt and rank on rank ordinals that scoff at AxC. They'll find a
comfortable home in NF which is now known to rebuke AxC.
> The smallest inaccessible cardinal (I believe) is still consistent
> with ZF+(V=L). And of course strongly inaccessible = weakly
> inaccessible in this universe.
Just the first one only and no others?
> The main complaint most Set Theorists have with V=L is that it feels
> needlessly confining. Denying the existence of sets which cannot be
> constructed in its simple steps, although consistent, seems rather
> artificial.
Some deny gods, ghosts, fairies, etc., others like them. Even so,
no matter how fantastic the entity, it's but mortal imagination.
No matter how big the number, by the Loewenheim-Skolem paradox
it's a facade of a countable number.
> Why make such a blatantly restrictive assumption? Those
> who do tend to do so only because they want an easy way to its
> conclusions, not because V=L is itself at all persuasive.
Evidence for V = L is provided by Occam's razor.
> One important result of the Constructible Universe is that it's a
> minimal inner model of ZFC, so you can't really get any smaller
> without being isomorphic to it. Also, all constructible sets are
> definable from the ordinals, which is nice (but again, implying a too
> simplistic world).
'Tis a gift to be simple... -- refrain Amish song
KISS -- engineering directive
----
William Elliot
Newsgroups: sci.math
Subject: Re: How many ordinals?
> Friedrich Hartogs proved a "lemma" on the way to showing the Axiom of
> Choice is equivalent to the trichotomy principle for cardinals.
> Given any set X, there is of course the cardinal number of X, which
> is naively the equivalence class of sets equinumerous with X.
> Ordinal numbers may be considered either as equivalences on
> well-orders or (in the von Neumann approach) hereditarily transitive
> sets (the "transitive" meaning here that every member of a member is
> a member of a transitive set).
> What Hartogs showed is that, without assuming
> the Axiom of Choice (or Axiom of Infinity, for that
> matter), there exists a least ordinal which is not
> "injective" to X, i.e. not less than or equal to X
> in cardinality, for any set X whatever.
How does the proof of this compare with the
Cantor-Bernstein theorem?
> Without trichotomy, of course, we cannot claim
> that this is the same as having cardinality greater
> than or equal to X. But as trichotomy establishes
> that, it establishes that any X can be well-ordered.
We have a number system that is partially ordered.
Trichotomy, Hartog ==> for all X, some cardinal > |X| ?
for all X, some cardinal > |X| implies well ordered?
> Hence the Axiom of Choice is equivalent to the
> principle of trichotomy for cardinal numbers (the
> other direction being trivial).
well order ==> AxC ? Yes, immediate.
What about the converse?
Does Bourbaki-Witt theorem
nonnul (partially) ordered S,
f:S -> S,
for all x in S, x <= f(x),
for all chains C subset S, sup C in S
implies
some x with f(x) = x
which is a result of Hartog's theorem, make it easier to show
AxC ==> well ordering.
> Regarding the various "subsystems" of ZFC you propose, I would
> highlight one implication of Hartogs lemma concerning the assumption
> of the Axiom of Infinity but not Axiom of Choice. Given X as
> little-omega, there must be an ordinal Y which is not injective to
> X. But since both X and Y are well ordered, by transfinite induction
> we must have |X| strictly less than |Y|. That is, there exists a well-
> orderable cardinal strictly beyond the countable little-omega. Of
> course the argument can be repeated with X replaced by Y, to get a
> chain of strictly increasing well-orderable cardinals.
So the axiom of infinity allows construction of the ordinals?
----
Stephen J. Herschkorn
>So the axiom of infinity allows construction of the ordinals?
>
Yes, William, using Infinity and Power Set, you can construct all the
ordinals. See the thread, "Countable Ordinals," which you started here
on 21 December 2003. See also the first chapter of Kunen's graduate
text on Set Theory.
Chip Eastham
(following a snippet from me)
> > Friedrich Hartogs proved a "lemma" on the way to showing the Axiom of
> > Choice is equivalent to the trichotomy principle for cardinals.
> > Given any set X, there is of course the cardinal number of X, which
> > is naively the equivalence class of sets equinumerous with X.
> > Ordinal numbers may be considered either as equivalences on
> > well-orders or (in the von Neumann approach) hereditarily transitive
> > sets (the "transitive" meaning here that every member of a member is
> > a member of a transitive set).
>
> > What Hartogs showed is that, without assuming
> > the Axiom of Choice (or Axiom of Infinity, for that
> > matter), there exists a least ordinal which is not
> > "injective" to X, i.e. not less than or equal to X
> > in cardinality, for any set X whatever.
William Elliot asked:
> How does the proof of this compare with the
> Cantor-Bernstein theorem?
The Cantor-Schroder-Bernstein theorem establishes
that injectivity (of representative sets) induces a
partial order among cardinals. While surprisingly
messy, the CSB theorem doesn't require choice
(which would make the proof relatively trivial).
So (a bit uncertain of what exactly you want to
know) the proof of the Hartogs lemma is less
complicated than that of CSB (which I guess is
why the former is merely a lemma and the latter
is a named theorem).
(more of what I wrote)
> > Without trichotomy, of course, we cannot claim
> > that this is the same as having cardinality greater
> > than or equal to X. But as trichotomy establishes
> > that, it establishes that any X can be well-ordered.
elicited this futher discussion from William:
> We have a number system that is partially ordered.
>
> Trichotomy, Hartog ==> for all X, some cardinal > |X| ?
> for all X, some cardinal > |X| implies well ordered?
No, Hartogs proved that for any cardinal |X| there is a
well-orderable cardinal which is not less than or equal
to |X|. If trichotomy is assumed then suddenly |X| is
(strictly) less than a well-orderable cardinal, which
implies |X| is well-orderable. Which is the gist of
this next remark by me:
> > Hence the Axiom of Choice is equivalent to the
> > principle of trichotomy for cardinal numbers (the
> > other direction being trivial).
William then wrote:
> well order ==> AxC ? Yes, immediate.
Yes, get a choice function on a family of non-empty
subsets by applying a well-ordering to their union
and using the "least" element of each subset as
defined by the well-ordering.
> What about the converse?
> Does Bourbaki-Witt theorem
> nonnul (partially) ordered S,
> f:S -> S,
> for all x in S, x <= f(x),
> for all chains C subset S, sup C in S
> implies
> some x with f(x) = x
>
> which is a result of Hartog's theorem, make it easier
> to show AxC ==> well ordering.
I don't know of an approach to showing
AxC ==> well-ordering along these lines.
My mind wants to interpolate Zorn's
lemma in between AxC and well-ordering,
which has the side-benefit of showing the
equivalence of all three formulations.
I kinda hoped Stephen would have answered
this piece! When I said "the other direction
being trivial", all I had in mind was a well-order
is a maximal total ordering on a nonempty
set, and that such a thing is guaranteed by
AxC (via Zorn's lemma), and that trichotomy
(of cardinals) follows from all sets being
well-ordered.
> > Regarding the various "subsystems" of ZFC you propose, I would
> > highlight one implication of Hartogs lemma concerning the assumption
> > of the Axiom of Infinity but not Axiom of Choice. Given X as
> > little-omega, there must be an ordinal Y which is not injective to
> > X. But since both X and Y are well ordered, by transfinite induction
> > we must have |X| strictly less than |Y|. That is, there exists a well-
> > orderable cardinal strictly beyond the countable little-omega. Of
> > course the argument can be repeated with X replaced by Y, to get a
> > chain of strictly increasing well-orderable cardinals.
> So the axiom of infinity allows construction of the ordinals?
Well, it certainly allows construction of some interesting
ordinals, for instance some uncountable ones. E.g. if the
continuum is not well-orderable, then Hartogs lemma gives
an ordinal whose cardinal which is not less than or equal to
the cardinality of the continuum. But such an ordinal must
then be uncountable.
I'm something of a Quine's NF aficianado, where the theory
of ordinals and cardinals is less developed than in ZFS. I
note that Jonathan Hoyle has made some interesting
comments elsewhere in this thread.
regards, chip
William Elliot
> > Friedrich Hartogs proved a "lemma" on the way to showing the Axiom of
> > Choice is equivalent to the trichotomy principle for cardinals.
> > Given any set X, there is of course the cardinal number of X, which
> > is naively the equivalence class of sets equinumerous with X.
> > Ordinal numbers may be considered either as equivalences on
> > well-orders or (in the von Neumann approach) hereditarily transitive
> > sets (the "transitive" meaning here that every member of a member is
> > a member of a transitive set).
>
> > What Hartogs showed is that, without assuming
> > the Axiom of Choice (or Axiom of Infinity, for that
> > matter), there exists a least ordinal which is not
> > "injective" to X, i.e. not less than or equal to X
> > in cardinality, for any set X whatever.
| William Elliot asked:
> How does the proof of this compare with the
> Cantor-Bernstein theorem?
| The Cantor-Schroder-Bernstein theorem establishes
| that injectivity (of representative sets) induces a
| partial order among cardinals. While surprisingly
| messy, the CSB theorem doesn't require choice
| (which would make the proof relatively trivial).
9 lines involking the Tarski fixed point theorem is _too_ messy?
| So (a bit uncertain of what exactly you want to
| know) the proof of the Hartogs lemma is less
| complicated than that of CSB (which I guess is
| why the former is merely a lemma and the latter
| is a named theorem).
Oh good, then it's simple and you could give some easy to follow hints.
> > Without trichotomy, of course, we cannot claim
> > that this is the same as having cardinality greater
> > than or equal to X. But as trichotomy establishes
> > that, it establishes that any X can be well-ordered.
| elicited this futher discussion from William:
> We have a number system that is partially ordered.
>
> Trichotomy, Hartog ==> for all X, some cardinal > |X| ?
> for all X, some cardinal > |X| implies well ordered?
| No, Hartogs proved that for any cardinal |X| there is a
| well-orderable cardinal which is not less than or equal
| to |X|. If trichotomy is assumed then suddenly |X| is
| (strictly) less than a well-orderable cardinal, which
| implies |X| is well-orderable. Which is the gist of
| this next remark by me:
> > Hence the Axiom of Choice is equivalent to the
> > principle of trichotomy for cardinal numbers (the
> > other direction being trivial).
| William then wrote:
> well order ==> AxC ? Yes, immediate.
| Yes, get a choice function on a family of non-empty
| subsets by applying a well-ordering to their union
| and using the "least" element of each subset as
| defined by the well-ordering.
William willfully rejoined, "Yes, immediate."
> What about the converse?
> Does Bourbaki-Witt theorem
> nonnul (partially) ordered S,
> f:S -> S,
> for all x in S, x <= f(x),
> for all chains C subset S, sup C in S
> implies
> some x with f(x) = x
>
> which is a result of Hartog's theorem, make it easier
> to show AxC ==> well ordering.
| I don't know of an approach to showing
| AxC ==> well-ordering along these lines.
| My mind wants to interpolate Zorn's
| lemma in between AxC and well-ordering,
| which has the side-benefit of showing the
| equivalence of all three formulations.
|
| I kinda hoped Stephen would have answered
| this piece! When I said "the other direction
| being trivial", all I had in mind was a well-order
| is a maximal total ordering on a nonempty
| set, and that such a thing is guaranteed by
| AxC (via Zorn's lemma), and that trichotomy
| (of cardinals) follows from all sets being
| well-ordered.
Thanks Chip. This looks like material for another thread which eventually
I may get around to recaping Bourbaki-Witt, Zorn, AxC etc.
> > Regarding the various "subsystems" of ZFC you propose, I would
> > highlight one implication of Hartogs lemma concerning the assumption
> > of the Axiom of Infinity but not Axiom of Choice. Given X as
> > little-omega, there must be an ordinal Y which is not injective to
> > X. But since both X and Y are well ordered, by transfinite induction
> > we must have |X| strictly less than |Y|. That is, there exists a well-
> > orderable cardinal strictly beyond the countable little-omega. Of
> > course the argument can be repeated with X replaced by Y, to get a
> > chain of strictly increasing well-orderable cardinals.
> So the axiom of infinity allows construction of the ordinals?
| Well, it certainly allows construction of some interesting
| ordinals, for instance some uncountable ones. E.g. if the
| continuum is not well-orderable, then Hartogs lemma gives
| an ordinal whose cardinal which is not less than or equal to
| the cardinality of the continuum. But such an ordinal must
| then be uncountable.
| I'm something of a Quine's NF aficianado, where the theory
| of ordinals and cardinals is less developed than in ZFS. I
| note that Jonathan Hoyle has made some interesting
| comments elsewhere in this thread.
ZFS? You don't mean ZFC?
I liked NF until NF -> ~AxC which put a big hole in Rosseur's 'Logic for
Mathematicians'. I'm teaming up with Occam to research a proof of V = L.
With V = L, how many inaccessibles are possible?
One takes into account that assuming no inaccessibles doesn't introduce a
contradiction to set theory while assuming inaccessibles cannot be shown
consistent with set theory, ie there's a proof that shows it's not
possible to show assuming inaccessibles doesn't introduce a contradiction
to set theory.
> regards, chip
----
Aatu Koskensilta
> From: Jonathan Hoyle <jonh...@mac.com>
>> The smallest inaccessible cardinal (I believe) is still consistent
>> with ZF+(V=L). And of course strongly inaccessible = weakly
>> inaccessible in this universe.
>
> Just the first one only and no others?
Nah. You can have many many large cardinal axioms up to something like
"for every countable alpha there exists an alpha-Erdös cardinal" holding
in L.
--
Aatu Koskensilta (aatu.kos...@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
David R Tribble
>> Riddle of the day.
>> How much faster can cardinals count than ordinals can?
>
Dave L. Renfro wrote:
>> I'd say the ordinals are only faster for (relatively) short
>> periods and, as you get farther out along the ordinals, these
>> intervals where the ordinals are ahead of the cardinals become
>> blips that can be ignored.
>
William Elliot wrote:
> Nay, the cardinals go 1,2,3,.. aleph_0, aleph_1. While the
> ordinals go 1,2,3,.. omega_0, omega_0 + 1, ... omega_0 * 2 ...
>
> So at aleph_0 = omega_0, they're neck and neck but then the cardinals jump
> off to aleph_1 while the ordinals take forever and a half to get to
> omega_1 = aleph_1. While they're still getting to the edge of the solar
> system, the cardinals have raced off aleph_1, aleph_2,... aleph_omega0 to
> the nearest stars and beyond to aleph_omega1 at the edge of the galaxy.
So is it fair to say that there are "more" ordinals than cardinals,
in the sense that every cardinal corresponds to some ordinal, but not
necessarily the other way around? (Or am I under the wrong impression?)
Aatu Koskensilta
> So is it fair to say that there are "more" ordinals than cardinals,
> in the sense that every cardinal corresponds to some ordinal, but not
> necessarily the other way around? (Or am I under the wrong impression?)
There are "more" ordinals than cardinals in the sense that some ordinals
are cardinals, but not all. There are exactly the same number of
ordinals as cardinals in the sense that there is a definable one-to-one
mapping between them.
Jonathan Hoyle
> Skolem paradox, it's just a countable model.
I still don't understand your point. Lowenstein-Skolem merely states
that among the many, many models of ZFC, some are countable.
Lowenstein-Skolem does *NOT* say they all are. For example, our usual
model of ZFC is not countable.
> > The smallest inaccessible cardinal (I believe) is still consistent
> > with ZF+(V=L). And of course strongly inaccessible = weakly
> > inaccessible in this universe.
>
> Just the first one only and no others?
No, of course not. It is consistent to have countlessly many
inaccessibles, hyper-inaccessibles, hyper-hyper-inaccessibles, etc. In
the world of large cardinals, however, these are considered rather
small. They are "large" but just so.
> No matter how big the number, by the Loewenheim-Skolem paradox
> it's a facade of a countable number.
You clearly have no idea of what you are talking about. You seem to be
hoping that the Lowenstein-Skolem Theorem (not a "paradox") will say
something more than it is saying. That ZFC can be modelled by a
countable model does not in any way detract it from being modelled by
an uncountable one. You wishing it to be so does not make it so.
I'm going to guess that you have never read the Loewenheim-Skolem
Theorem, or even an outline of its proof. You must have read somewhere
where "there must be a countable model" and somehow concluded that this
means there can be no other models. You lived in a fictional world,
groping for some idealized 19th century world view, lacking the
intestinal fortitude to accept mathematical truth, what it says.
If this is what you want, rather than the truth of mathematics, I
recommend you tour the authors cited on http://www.crank.net/maths.html
. Surely there will be some crackpot there whose ideas approximate
your own.
William Elliot
> > But you are dreaming, for by the Loewenheim-
> > Skolem paradox, it's just a countable model.
> I still don't understand your point. Lowenstein-Skolem merely
> states that among the many, many models of ZFC, some are countable.
> Lowenstein-Skolem does *NOT* say they all are. For example, our
> usual model of ZFC is not countable.
It is an example how no FOL can distinguish one uncountable cardinal
from another. That they are allusions of the language being spoken.
Theorem: any theory (with countable language) categorical in one
uncountable cardinal is categorical in all uncountable cardinals.
I suppose the question to ask is, is FOL + ZFC a categorical theory?
----
Aatu Koskensilta
> I suppose the question to ask is, is FOL + ZFC a categorical theory?
No, "FOL + ZFC" is not categorical in any power.
Jonathan Hoyle
> > > Skolem paradox, it's just a countable model.
>
> > states that among the many, many models of ZFC, some are countable.
> > Lowenstein-Skolem does *NOT* say they all are. For example, our
> > usual model of ZFC is not countable.
>
> It is an example how no FOL can distinguish one uncountable cardinal
> from another. That they are allusions of the language being spoken.
Not true at all. The cardinality of the reals and the cardinality of
the power set of the reals are easily distinguished. The
Loewenheim-Skolem Theorem does not contradict this in the least. Your
understanding of LST is not only incomplete, it appears to be downright
flawed.
Herman Rubin
Jonathan Hoyle <jonh...@mac.com> wrote:
>> But you are dreaming, for by the Loewenheim-
>> Skolem paradox, it's just a countable model.
>I still don't understand your point. Lowenstein-Skolem merely states
>that among the many, many models of ZFC, some are countable.
>Lowenstein-Skolem does *NOT* say they all are. For example, our usual
>model of ZFC is not countable.
There is an extension of the Skolem-Loewenheim Theorem
which states that if there is an infinite model, there
exist models with all larger cardinals. This is
equivalent to the Axiom of Choice.
>> > The smallest inaccessible cardinal (I believe) is still consistent
>> > with ZF+(V=L). And of course strongly inaccessible = weakly
>> > inaccessible in this universe.
We do not know if it is consistent, and it cannot be
proved consistent if present mathematics is consistent.
The reason is that a model with a strongly inaccessible
cardinal enables the proof of consistency, which Godel
has shown cannot be done.
>> Just the first one only and no others?
>No, of course not. It is consistent to have countlessly many
>inaccessibles, hyper-inaccessibles, hyper-hyper-inaccessibles, etc. In
>the world of large cardinals, however, these are considered rather
>small. They are "large" but just so.
The same problems arise.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hru...@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558
William Elliot
Newsgroups: sci.math
Subject: Re: How many ordinals?
Jonathan Hoyle <jonh...@mac.com> wrote:
> >> But you are dreaming, for by the Loewenheim-
> >> Skolem paradox, it's just a countable model.
> >I still don't understand your point. Lowenstein-Skolem merely
> >states that among the many, many models of ZFC, some are countable.
> >Lowenstein-Skolem does *NOT* say they all are. For example, our
> >usual model of ZFC is not countable.
> There is an extension of the Skolem-Loewenheim Theorem
> which states that if there is an infinite model, there
> exist models with all larger cardinals. This is
> equivalent to the Axiom of Choice.
Fantastic, it augments the notion that the infinite is but an allusion of
the language spoken. Thus there is no way that a FOL can capture the
essence of bigger and smaller infinities but only allude to them within
its internal imaginations.
>> > The smallest inaccessible cardinal (I believe) is still consistent
>> > with ZF+(V=L). And of course strongly inaccessible = weakly
>> > inaccessible in this universe.
> We do not know if it is consistent, and it cannot be
> proved consistent if present mathematics is consistent.
> The reason is that a model with a strongly inaccessible
> cardinal enables the proof of consistency, which Godel
> has shown cannot be done.
> >> Just the first one only and no others?
> >No, of course not. It is consistent to have countlessly many
> >inaccessibles, hyper-inaccessibles, hyper-hyper-inaccessibles, etc.
> >In the world of large cardinals, however, these are considered
> >rather small. They are "large" but just so.
> The same problems arise.
Let's see if I got this right.
ZF + V = L + inaccessibles
has the same statues as
ZFC + inaccessibles.
Namely it can't be proven consistent given the consistency of ZFC.
Am I right to surmise,
the consistency of ZF implies the consistency of ZFC?
----
Denis Feldmann
Yes, this resultsz from Gödel and Cohen's works
>
> ----
William Elliot
> William Elliot a écrit :
> >
> > Let's see if I got this right.
> > ZF + V = L + inaccessibles
> > has the same statues as
> > ZFC + inaccessibles.
> > Namely it can't be proven consistent given the consistency of ZFC.
> >
> > Am I right to surmise,
> > the consistency of ZF implies the consistency of ZFC?
>
> Yes, this resultsz from Gödel and Cohen's works
>
Since AxC is independent of ZF and if ZF is consistent, then isn't
already ZF + AxC and ZF + ~AxC consistence? For if they weren't then
ZF + AxC |- contradiction
would prove
ZF |- ~AxC
and similar for ZF + ~AxC?
Aatu Koskensilta
> William Elliot a écrit :
>> the consistency of ZF implies the consistency of ZFC?
>
> Yes, this resultsz from Gödel and Cohen's works
You don't need forcing, just noting that choice holds in L suffices.