From: Fred Galvin <galvin@math.ukans.edu>
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.