From: Robin Chapman Subject: Re: uncountable ordinals without AC Date: Fri, 10 Mar 2000 22:36:51 GMT Newsgroups: sci.math Summary: [missing] In article <8abn7k$gn8$2@news.acns.nwu.edu>, lerma@math.nwu.edu (Miguel A. Lerma) wrote: > How do you prove that there are uncountable ordinals without > using the Axiom of Choice? The usual argument proves that there are uncountable well-ordered sets. Let X be a fixed countable infinite sets, and let W be the set of well-orderings of subsets of X. A bit more formally, W is the set of pairs (A,R) where A is a subset of X and R is a well-ordering on A (so as a relation a subset of A x A). We put an equivalence relation on W by setting two ordering equivalent if order-isomorphic, then ordering W' the set of equivalence classes by setting one order to be less than another if it's order-isomorphic to a proper initial segment of the second. Then W is an uncountable well-ordered set. > More generally, I would like to see a proof of the following > statement in ZF without AC: > > (1) "For every set M there is a set Z of ordinals such that > alpha is in Z iff |alpha| =< |M|." > > In other words, the collection of all ordinals equipotent to > subsets of M form a set (if M = omega, then Z would be omega_1 > = the first uncountable ordinal). > > Sierpinski' 1947 paper proving GCH => AC uses (1), but it does > not justify it. Would replacing X with M give a proof that works here? -- Robin Chapman, http://www.maths.ex.ac.uk/~rjc/rjc.html "`The twenty-first century didn't begin until a minute past midnight January first 2001.'" John Brunner, _Stand on Zanzibar_ (1968) Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: lerma@math.nwu.edu (Miguel A. Lerma) Subject: Re: uncountable ordinals without AC Date: 11 Mar 2000 05:38:47 GMT Newsgroups: sci.math Robin Chapman (rjc@maths.ex.ac.uk) wrote: : : Would replacing X with M give a proof that works here? After I posted my question I realized that (1) can be proved with the replacement axiom schema. For each element w of W = well-orderings of subsets of M, let a(w) = the ordinal isomorphic to w. W is a set - in fact a subset of P(M) x P(M x M), where P represents power set. Hence by replacement Z = { a(w) | w in W } is a set. Miguel A. Lerma ============================================================================== From: Fred Galvin Subject: Re: uncountable ordinals without AC Date: Fri, 10 Mar 2000 16:54:14 -0600 Newsgroups: sci.math On 10 Mar 2000, Miguel A. Lerma wrote: > How do you prove that there are uncountable ordinals without > using the Axiom of Choice? > > More generally, I would like to see a proof of the following > statement in ZF without AC: > > (1) "For every set M there is a set Z of ordinals such that > alpha is in Z iff |alpha| =< |M|." > > In other words, the collection of all ordinals equipotent to > subsets of M form a set (if M = omega, then Z would be omega_1 > = the first uncountable ordinal). You are asking about Hartogs' Theorem, which you can find in many books. To pick one at random, it's on p. 50 of J. E. Littlewood, _The Elements of the Theory of Real Functions_, 3rd edition, Dover Publications, 1954, $1.35. Here is a sketch of the proof (for the M = omega case) which I posted a couple of months ago in this newsgroup: Subject: Re: Stupid set theory questions From: Fred Galvin Date: 1999/12/08 Newsgroups: sci.math On 8 Dec 1999, Seraph-sama wrote: > The "first uncountable ordinal" is the set aleph_1 = {1, 2, ..., w, w > + 1, ..., 2w, 2w + 1, ..., w^2, w^2 + 1..., w^2 + w, w^2 + w + 1, ..., > w^n, ...} = w^w. Correct? Is this really the first cardinality after Incorrect, as other posters have already told you. Also, it's customary to include 0 as the first ordinal; and the preferred convention for ordinal multiplication (which is noncommutative) is to write w+w = w2 and 2w = w. By the way, since 0 is the first ordinal, it follows that 1 is the 2nd, 2 is the 3rd, and so on; then omega is the (omega+1)th (there is no "omegath"), and so on; any ordinal alpha is the (alpha+1)th ordinal. Most books (maybe all of them) get this wrong. > aleph_0? If not, could somebody provide a proof (preferably > constructive, if possible) of the existence of aleph_1? And, after > that, the continuum hypothesis states that c = aleph_1 = w^w, right? To construct the cardinal aleph_1 and the ordinal omega_1, it's enough to construct any uncountable well-ordered set. (Let W be any uncountable well-ordered set. If every element of W has only countably many predecessors in the well-ordering of W, then W has order type omega_1 and cardinality aleph_1, and the Von Neumann ordinals up to omega_1 can be defined by transfinite induction on W. If some elements of W have uncountably many predecessors, let a be the least such element, and replace W by the set of predecessors of a.) You can construct an uncountable well-ordered set without the axiom of choice. (I believe this construction is due to the mathematician F. Hartogs.) The idea is simple and natural, but there are many details to check. I'll just give you the outline, and you can fill in the details yourself, or look them up in a good book on set theory. Let N be the set of all natural numbers. Consider the collection of all ordered pairs (X,R) where X is a subset of N and R is a well-ordering of X. (In a manner of speaking, this is the collection of all countable well-ordered sets.) Partition this collection into isomorphism classes; i.e., two pairs (X,R) and (Y,S) are in the same cell of the partition if and only if they are isomorphic as ordered sets. Let W be the set of all these isomorphism classes. (In effect, the set of all countable ordinals.) Define an ordering of W as follows: for any elements x, y in W, let x < y if and only if some element (X,R) of x is a proper initial segment of some element (Y,S) of y. Now you can prove that W is well-ordered by <, and then you can prove that W is uncountable, and that every element of W has only countably many predecessors, whence (W,<) has order type omega_1