Can a Set be Well-Ordered Without the Axiom of Choice?

[Dragonfall]

Homework Statement

Show that if every total order of a set x is a well-order, then there is no bijection between x and $$x\cup\{ x\}$$ = Sx.

The Attempt at a Solution

Suppose there was, then you can have a total order on x and an induced total order on Sx. But this induced order on Sx is a total order on x. Something bad's supposed to happen here.

 

[Dragonfall]

Anyone?

 

[Hurkyl]

Do you know of any examples of total orders that are not well-orders?

 

[Dragonfall]

Yes, the usual order on the real numbers.

 

[Hurkyl]

Okay, so you've proven that if every total order of a set x is a well-order, then x does not have the same cardinality as R. (right?)

 

[Dragonfall]

We can't assume the axiom of infinity on this question (nor do we need to, apparently), so we can't assume that R exists, or even N, for that matter.

Basically the two conditions are equivalent to the fact that the set x is "finite". This question is actually part of a bigger question asking me to prove the equivalence of 6 statements, and this is the link in the chain that I can't prove.

I am certain I'm on the right track with the two total orders there, but I can't see a contradiction.

 

[Dragonfall]

Here's the whole question. Prove the following are equivalent:

(a) Every injective function from x to x is surjective.
(b) There is no proper subset y of x in bijection with x.
(c) Every surjective function from x to x is injective.
(d) There is no proper superset y containing x in bijection with x.
(e) Every total order of x is a well order.
(f) There is no bjection between x and Sx = xU{x}.

 

[Hurkyl]

Basically the two conditions are equivalent to the fact that the set x is "finite".

This was my idea. Certainly, the thing you're trying to prove is an immediate consequence of this assertion.

The word "finite" and the phrase "well-order" suggest that induction might be useful.



By the way, is it obvious that every set has a total ordering?

 

[Dragonfall]

Every set is in bijection with some cardinal. Every cardinal is an ordinal (under some models). Every ordinal is totally ordered by $$\in$$, so every set has a total ordering.

 

[Hurkyl]

Whoops, I forgot to say 'without the axiom of choice'.


I was pondering the idea of trying to construct a counterexample; because condition (e) says "Every total order...", and you were assuming one existed, that prompted me to think about the case of a set x without any total orderings. Then, one of two things happen:
(1) The statement you are trying to prove is false.
(2) The set x is not bijective with Sx.

And so, I was mulling the possibility of having an infinite set x that is not bijective with Sx. Clearly this cannot happen if we assume axiom of choice, but I am not so familiar with the case where we reject the AoC, and I'm wondering if this is possible!

 

[Dragonfall]

I don't think cardinality can be used as an argument, since Q is the same cardinality as N, but is not well-ordered.

I'm not familiar with set theory enough to say what you can't do without the axiom of choice. AC seems pretty intuitive to me.

I do have a side question: if the class of all things is in bijection with the class of all ordinals, then you can order the class of all things. What's wrong here?