From: Fred Galvin Subject: Re: new axiom of choice question Date: Wed, 22 Dec 1999 20:55:19 -0600 Newsgroups: sci.math Keywords: Hartog's theorem (large well-ordered sets) On Wed, 22 Dec 1999, garuda777 wrote: > In your hint the well ordering is equivalent to AC so i must > mis-understand. As set theory is almost antipodal to my specialty, i > fear i need slightly larger hints...just trying to learn without > reading a big thick book...my faculties appear to decrease > exponentially with every post to this group...arghhh What do you mean, "the well ordering is equivalent to AC"? The assertion that EVERY set can be well-ordered is equivalent to AC. Even without AC, SOME sets can be well-ordered. In particular, the following statement can be proved without AC: Given any set X, we can construct a well-ordered set A such that there is no 1-to-1 map of A into X. This is Hartogs' theorem; see, e.g., Prop. 24 on p. 50 of J. E. Littlewood, _The Elements of the Theory of Real Functions_, Third Edition, Dover Publications, New York, 1954. If we assume that any two sets are comparable in the *injective* sense, then we can conclude immediately that there is a 1-to-1 map of X into A, whence X can be well-ordered. If we only assume comparability in the *surjective* sense, we have to work a little bit harder. Use Hartogs' theorem to get a well-ordered set A such that there is no 1-to-1 map of A into P(X), the power set of X. It follows that there is no map of X onto A, and so there must be a map of A onto X; since A is well-ordered, it follows that there is a 1-to-1 map of X into A, and so X can be well-ordered.