Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In textbook it says that every well-orderable set is equipotent to an initial ordinal number. However, of course unwell-orderable cannot equipotent to any ordinal number, but is there any set is unwell-orderable? By axiom of regularity we know that every set is well-founded, so can we conclude that every set is well-orderable? If not, which set is unwell-orderable?

share|improve this question

3 Answers 3

up vote 5 down vote accepted

You cannot really point out at an arbitrary set and say "Aha! I found something which cannot be well-ordered!" because if you only assume ZF it is possible that the universe also satisfies the axiom of choice.

To actually point out a set which cannot be well-ordered you need to assume that one exists, but the problem is that you are only assuming it exists and you don't really know where. In some cases that is enough to produce a counterexample for some things (e.g. Zorn's lemma) but it is not enough in order to identify where this set lies.

It is consistent that the real numbers cannot be well-ordered, and it is consistent that every set that "usual" mathematician would care about is well-ordered but the axiom of choice fails in a very acute way.

This is why often "anti-choice" axioms point out where the axiom of choice fails in a rather explicit way. For example the axiom of determinacy tells us that the axiom of choice fails for the real numbers. It tells us that because we know that if the real numbers can be well-ordered then there is a set which cannot be determined.

Perhaps a simpler case would be "all sets of real numbers are measurable", but the idea is the same.

The requirement that $\in$ is well-founded is not enough to ensure well-orderability, because well-foundedness tells you that you are never "too far" from the bottom, but you can be very wide nonetheless.


I want to add some personal experience of mine on the topic, that usually when doing work without the axiom of choice you want to first figure out what exactly you are trying to prove, after you figured that out you can pinpoint your assumptions better. Do you want a particular set to be non-well ordered, or just a non-well ordered set which has a certain property, and so on.

But ultimately this really depends on what you are trying to prove.

share|improve this answer
    
Okay, my original purpose is to find out a particular set which is non-well ordered. But I was surprised that whether a set is well-orderable or not is depend on the axiom system. Furthermore, I don't quite understand why it is consistent that the real numbers cannot be well-ordered. Though the real field itself is not well-ordered, $\mathbb{R}$ is equipotent to $2^{\aleph_0}$, which is an ordinal number, thus $\mathbb{R}$ must be well-orderable $\ldots$ –  Popopo Sep 19 '12 at 13:19
    
@Popopo: No... $2^{\aleph_0}$ does not have to be an ordinal. –  Asaf Karagila Sep 19 '12 at 13:41
    
But $2^{\aleph_0}$ is a cardinal number, and in some books the cardinal number of a set is the least ordinal number which equipotent to it(seems called Von Neumann cardinal assignment). So every cardinal number is an ordinal number. –  Popopo Sep 19 '12 at 13:50
    
@Popopo: No. Under this definition of cardinals the exponentiation is not well-defined. Cardinality can be defined without the axiom of choice as equivalence classes under bijections. –  Asaf Karagila Sep 19 '12 at 15:12
    
Ok, I see. So if we add 'the real numbers cannot be well-ordered' into ZF as an axiom, both AC and CH will not hold? –  Popopo Sep 19 '12 at 15:29

The statement that all sets are well-orderable is a well-known equivalent of the Axiom of Choice (perhaps even the first, as Zermelo devised the Axiom of Choice precisely to prove this consequence). Because the Axiom of Choice is relatively consistent with ZF -- as proved by Kurt Gödel -- one will not be able to construct a non-well-orderable set using standard set-theoretic operations.

However Paul Cohen proved that the negation of Axiom of Choice is also relatively consistent with ZF, and so one can devise "set theoretic models" in which not all sets are well-orderable.

share|improve this answer

The axiom of choice is equivalent to there being some well-order on every set. The axiom of choice is independent of the other axioms of set theory, so it is consistent that a set exists that cannot be well-ordered. But it is not provable that such a set exists, for this would violate the consistency of the axiom of choice.

So you cannot construct such a set in any meaningful way. But it is consistent (in the absense of the axiom of choice) for example that there is no well-ordering on $\mathbb{R}$. So $\mathbb{R}$ could be an example.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.