'Partial' AC/Well-Ordering?
Jim Heckman
while now, and the following idle speculation has occurred to me.
Possibly it's answered in texts I haven't gotten to yet, but in the
meantime I'd be interested in any insights anyone would care to offer
:-) First, a lemma leading up to my speculation:
Lemma: My understanding is that the Well-Ordering Principle/Theorem is
*equivalent* to the Axiom of Choice. Is this correct, or is one stronger
than the other?
Speculation: Does it make any sense at all to talk about a 'partial' AC
in the following sense: Can consistent (and interesting) set theories be
constructed, supposedly somehow intermediate between ZF and ZFC, in
which *some*, but not *all*, uncountable sets can be well ordered? (A
stab in the dark is that one natural place to make such a separation is
at the inaccessible cardinals, about which I've learned very little as
yet.) If the answer is yes, what can be said about such set theories and
their equivalents of AC -- maybe something like "Given a family of
non-empty sets indexed by a set of cardinality < X, there exists a set
with non-empty intersection with each set in the family." Would the
cardinals (and ordinals?) of such a theory form only a partially ordered
class, as opposed to being totally ordered in ZFC? If so, would the
ordered chains within the class of cardinals be well ordered?
Thanks in advance for any time you might spend reading, thinking about,
researching, and writing a response to this post!
--
~~ Jim Heckman ~~
-- "As I understand it, your actions have ensured that you will never
see Daniel again." -- Larissa, a witch-woman of the Lowlands.
-- "*Everything* is mutable." -- Destruction of the Endless
Sent via Deja.com http://www.deja.com/
Before you buy.
Martin Vaeth
>Can consistent (and interesting) set theories be
>constructed, supposedly somehow intermediate between ZF and ZFC, in
The simplest one says that you have a choice function for any *countable*
collection of nonempty sets (of course you may replace *countable* also by any
other cardinal set of your choice).
>which *some*, but not *all*, uncountable sets can be well ordered?
In ZF there are always non-countable ordinals (in particular, non-countable
well ordered sets): This is Hartog's theorem which does not require AC.
If you assume only the countable AC mentioned above, these sets are even
uncountable (i.e. there is an injection from N into these sets but not
vice versa).
The problem is that without AC, these uncountable ordinals are hard to grasp.
For example it is not clear whether there exists a subset of the real line R
(or the power set of N if you prefer) which is in bijection with such a set.
In fact, if you can not well-order R, you can not associate a cardinality to R
(in the sense of a cardinal set). The same argument applies for also for the
power set of R, the power set of this power set, etc.
So in some sense the ordinals may form an hierarchy for themselves which is
outside the "hierarchy" formed by the above power sets (unless you assume AC,
of course).
BTW: Recall that the large continuum hypothesis states that the cardinality
of a power set is equal to the next cardinal number. In some sense this means
that the two hierarchies "strictly" coincide.
This observation explains (although it is not a formal proof, of course)
why the large continuum hypothesis actually implies AC.
>Would the cardinals (and ordinals?) of such a theory form only a partially
>ordered class, as opposed to being totally ordered in ZFC?
No, the ordinals (and thus the cardinals as particular ordinals) still form
a well-ordered class: The standard arguments (used usually in ZFC) actually
make no use of any form of AC. However, as explained above, the class of
ordinals may be rather "esoteric" (in contrast to the "intuitive" "class of
subsets of power sets" [I intentionally did not try to define the latter
precisely]).
G. A. Edgar
> In fact, if you can not well-order R, you can not associate a cardinality to R
I prefer to say: The cardinal of R is not an aleph. Alephs are the
cardinals of well-orderable sets, and they may be identified
with certain ordinals. Non-well-orderable sets still have
cardinals (which are, of course, not alephs).
--
Gerald A. Edgar ed...@math.ohio-state.edu
Richard Carr
:Date: 15 Jun 2000 17:39:47 +0100
:From: Martin Vaeth <va...@mathematik.uni-wuerzburg.de>
:Newsgroups: sci.math
:Subject: Re: 'Partial' AC/Well-Ordering?
:In ZF there are always non-countable ordinals (in particular, non-countable
:well ordered sets): This is Hartog's theorem which does not require AC.
:If you assume only the countable AC mentioned above, these sets are even
:uncountable (i.e. there is an injection from N into these sets but not
:vice versa).
They are uncountable without using AC. The fact that omega is a subset of
them but that there is no bijection already shows that they are
uncountable.
Richard Carr
:Date: Thu, 15 Jun 2000 08:05:37 GMT
:From: Jim Heckman <jhec...@my-deja.com>
:Newsgroups: sci.math
:Subject: 'Partial' AC/Well-Ordering?
:
:I've been studying axiomatic set theory, in fits and starts, for a short
:while now, and the following idle speculation has occurred to me.
:Possibly it's answered in texts I haven't gotten to yet, but in the
:meantime I'd be interested in any insights anyone would care to offer
::-) First, a lemma leading up to my speculation:
:
:Lemma: My understanding is that the Well-Ordering Principle/Theorem is
:*equivalent* to the Axiom of Choice. Is this correct, or is one stronger
:than the other?
:
They are equivalent in ZF. If you have the well-ordering principle then
you can define a choice function on a set A as follows:
well order A by some relation <
for a non-empty subset B of A, let f(B) be the <-least element of B.
Then f is a choice function.
Now, suppose AC holds. Let A be any set and let g be a choice
function on A. Extend domain(g) to include the empty set by
defining g(0)=A. (If you don't assume regularity, so that, perhaps A is an
element of A, then let t be any set not in A and define g(0)=t,
instead.) Let gamma be the ordinal obtained by using Hartogs' theorem on
A.
Define a map f:gamma->AU{A}, as follows: f(0)=g(A). Assume,
f(beta) is defined for all beta<alpha. Let A_alpha={f(beta):beta<alpha}
and let f(alpha)=g(A\A_alpha).
Note that A_beta is a subset of A_alpha for beta<=alpha. If beta<alpha and
f(beta)=f(alpha) then f(beta) is in A\A_alpha or else A\A_alpha=0. Since
f(beta) is in A_alpha by definition, it can't be in A\A_alpha, so
A\A_alpha=0. Thus A=A_alpha. If A=A_alpha, then A=A_beta for any
beta>alpha.
If there is no alpha such that A=A_alpha, then f is an injection from
gamma into A, contrary to Hartogs' theorem. Thus, for some alpha in gamma,
A=A_alpha. Choose the minimal such alpha in gamma (possible as gamma is
well-ordered, being an ordinal). Then A_alpha=A and the restriction of f
to A is injective and so it is a bijection between A and alpha.
Thus A can be well-ordered (for a,b in A, let aRb iff f(a)<f(b)).
:Speculation: Does it make any sense at all to talk about a 'partial' AC
:in the following sense: Can consistent (and interesting) set theories be
:constructed, supposedly somehow intermediate between ZF and ZFC, in
:which *some*, but not *all*, uncountable sets can be well ordered? (A
Yes. There are always uncountable ordered sets (omega_1, for instance) so
*some* will occur. It's possible to have some uncountable sets non-well
orderable or even non-linearly orderable.
:stab in the dark is that one natural place to make such a separation is
:at the inaccessible cardinals, about which I've learned very little as
:yet.) If the answer is yes, what can be said about such set theories and
:their equivalents of AC -- maybe something like "Given a family of
:non-empty sets indexed by a set of cardinality < X, there exists a set
:with non-empty intersection with each set in the family." Would the
I think so.
:cardinals (and ordinals?) of such a theory form only a partially ordered
:class, as opposed to being totally ordered in ZFC? If so, would the
Yes. In general, cardinals would be of 2 types: Initial ordinals and ones
obtained by use of Scott's trick (|A|={B:there is a bijection between A
and B and for any C, if there is a bijection between C and A then rank
B<=rank C}) (which needs the axiom of regularity/foundation).
:ordered chains within the class of cardinals be well ordered?
I don't think this is necessarily the case.
:
:Thanks in advance for any time you might spend reading, thinking about,
:
Herman Rubin
In fact, one can prove without any use of choice that the
power set of the reals is the union of aleph_1 sets. This
does not imply that it has a set of aleph_1 elements.
--
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, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
hru...@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558
Herman Rubin
Herman Rubin <hru...@odds.stat.purdue.edu> wrote:
>In article <Pine.LNX.4.21.000615...@cpw.math.columbia.edu>,
>Richard Carr <ca...@cpw.math.columbia.edu> wrote:
>>On 15 Jun 2000, Martin Vaeth wrote:
>>:Date: 15 Jun 2000 17:39:47 +0100
>>:From: Martin Vaeth <va...@mathematik.uni-wuerzburg.de>
>>:Newsgroups: sci.math
>>:Subject: Re: 'Partial' AC/Well-Ordering?
>>:In ZF there are always non-countable ordinals (in particular, non-countable
>>:well ordered sets): This is Hartog's theorem which does not require AC.
>>:If you assume only the countable AC mentioned above, these sets are even
>>:uncountable (i.e. there is an injection from N into these sets but not
>>:vice versa).
>>They are uncountable without using AC. The fact that omega is a subset of
>>them but that there is no bijection already shows that they are
>>uncountable.
>In fact, one can prove without any use of choice that the
>power set of the reals is the union of aleph_1 sets. This
>does not imply that it has a set of aleph_1 elements.
The first sentence in this paragraph is too weak, and
because of this, the second sentence is wrong. Both
of these should refer to the set of reals, rather than
the power set of the reals. The set of reals being the
union of aleph_1 sets automatically guarantees that the
power set of the reals has a set of aleph_1 elements.
Keith Ramsay
Jim Heckman <jhec...@my-deja.com> writes:
|If the answer is yes, what can be said about such set theories and
|their equivalents of AC -- maybe something like "Given a family of
|non-empty sets indexed by a set of cardinality < X, there exists a set
|with non-empty intersection with each set in the family."
I think you want to replace "non-empty" with "exactly one element in".
The union of the family has nonempty intersection with each set, of
course. Restricting the cardinality of the family is one way of
weakening AC, certainly. "Countable AC" is a weakening that holds in
some models where full AC fails. There is also the "axiom of dependent
choice", which says that if we have a sequence S1, S2, S3,... of
nonempty sets, and a relation R_i between S_i and S_{i+1} such that
for each element a of S_i there exists an element b of S_{i+1} such
that a R_i b, then there exists a sequence a_1, a_2, a_3,... where
each a_n is in S_n, and a_n R_n a_{n+1}. You can think of this as
saying you can choose countably many times, where each choice depends
upon the previous choice.
|Would the
|cardinals (and ordinals?) of such a theory form only a partially ordered
|class, as opposed to being totally ordered in ZFC? If so, would the
|ordered chains within the class of cardinals be well ordered?
That the cardinals are ordered is equivalent in ZF to AC. That the
ordinals are ordered is a theorem of ZF not requiring AC. I don't
know offhand whether an infinite descending chain of cardinalities
is possible; I don't see why it wouldn't be.
Keith Ramsay
David Libert
>
> That the cardinals are ordered is equivalent in ZF to AC. That the
> ordinals are ordered is a theorem of ZF not requiring AC. I don't
> know offhand whether an infinite descending chain of cardinalities
> is possible; I don't see why it wouldn't be.
Thomas Jech has a result I am recalling from memory. There is an
inexact statement of the result in Jech's paper _The Axiom of Choice_
(in the section titled "Mathematics without the axiom of choice"), the
paper appearing in _The Handbook of Mathematical Logic_ edited by Jon
Barwise.
As I recall the result is if M is a countable model of ZFC and
<P, <= > is a partial order in M (ie P a set), then there is a
countable ZF model N end extending M (ie members m in M don't get
any new members in the larger universe N), s.t. there is a set A of
cardinals so that A with the injectibility partial ordering between
cardinals is isomorphic to <P, <= > .
So this isomorphism preserves not only positive information on P but
also negative. So for example incomparable P elements correspond to
incomparable cardinals.
So as Keith suggested, infinite descending chains of cardinals are
possible, as well as anything else. A possibility I wondered about
before hearing of this theorem was the rational's ordering.
--
David Libert (ah...@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
Jeremy Boden
<kra...@aol.commangled> writes
...
>That the cardinals are ordered is equivalent in ZF to AC. That the
>ordinals are ordered is a theorem of ZF not requiring AC. I don't
>know offhand whether an infinite descending chain of cardinalities
>is possible; I don't see why it wouldn't be.
>
sense that one associates every cardinal with some ordinal.
Does this mean that without AC there could be sets which have a
cardinality different from that of any ordinal?
--
Jeremy Boden
Dave Seaman
Jeremy Boden <jer...@jboden.demon.co.uk> wrote:
>In article <20000618191630...@nso-df.aol.com>, Keith Ramsay
><kra...@aol.commangled> writes
>...
>>That the cardinals are ordered is equivalent in ZF to AC. That the
>>ordinals are ordered is a theorem of ZF not requiring AC. I don't
>>know offhand whether an infinite descending chain of cardinalities
>>is possible; I don't see why it wouldn't be.
>I thought that cardinals and ordinals are equivalent, at least in the
>sense that one associates every cardinal with some ordinal.
In the presence of AC, every cardinal is an ordinal, but not every
ordinal is a cardinal.
>Does this mean that without AC there could be sets which have a
>cardinality different from that of any ordinal?
Correct. All ordinals are well-ordered, and therefore it follows that
any set having the same cardinality as some ordinal is a set that can be
well-ordered.
--
Dave Seaman dse...@purdue.edu
Amnesty International calls for new trial for Mumia Abu-Jamal
<http://mojo.calyx.net/~refuse/mumia/021700amnesty.html>