Talk:Well-ordering theorem

A brute-force proof

It has always amazed me to see how many well educated and intelligent people objected to the Well-Ordering Theorem, calling it a "paradoxical" consequence of the Axiom of Choice. But as soon as one accepts that every set has its cardinality, the "paradox" vanishes. Let's see.

A cardinality |X| of a set X is defined as the smallest ordinal that has the same number of elements as X has. Being an ordinal, it is well-ordered by the less-than relation <. (Some prefer to name the relation < the "is-an-element-of" relation $\in$ in this context.)

Just take any set X and pick any 1-1 function f from X onto its cardinality |X|. It must exist by the definition of two sets having the same number of elements. Now, define the well-ordering << on X by:

x << y iff f(x) < f(y)).

<< is a well-ordering of X because < is a well-ordering of |X|.

To make the story shorter, the existence of well-ordering of any set X is entailed by the fact that its cardinality |X| is a well-ordered set (by < or by $\in$, as some would prefer to say).

The "brute force" descriptor can be justified as follows. One can think of the above construction of a well-ordering of X this way.

Pick up an ordinal number b of cardinality > |X| (for instance, the cardinality of the set of all subsets of X) and construct a (transfinite) sequence S of distinct elements of X using consecutive elements of b as indices of S. Informally, beginning with X = X', just keep removing the elements of X' and appending them to the end of sequence S' constructed already until X' becomes empty. Formally, if for some ordinal d < b, the sequence S' has already been constructed for all ordinals c < d and X' is still non-empty then remove any element z from X' and extend S' on d by putting S' (d) = z. (In addition to transfinite induction, the Axiom of Choice comes into play here, although not in a way that might be bona fide characterized as "counterintuitive".)

Here is a transfinite program that does just that:

X' = X;

for (d in b)

{

if (X' == empty) break;

z = choose_one_of ( X' )

X' = X' \ {z};

S' [d] = z;

}

S = S' ;

At some point, one must run out of elements of X' (and, therefore, the break instruction must be executed, eventually) because b has the cardinality > |X| $\geq$ |S' |, and S' , being duplicate-free as it is, establishes a 1-1 function from the set of indices of S' onto (the set of elements of) S' . So, there are not enough elements in X to assign them, via S' , to all indices in b without duplication, and the for-loop in the above program will break. At that point, X' is empty and S' has all the elements of X, thus it becomes the S that we have been constructing.

So, the sequence S is well defined, has no duplicates (so that it well-orders its elements), and the set of its elements is equal to X. Thus S well-orders X. Q.E.D.

The above is by no means "simple" or "complete" proof, whatever these two adjectives mean. (Actually, it would become fairly complicated if one bothered to provide all the details of it.) It's just that it leaves little or no room for bona fide intuitive objections, unless one objects to the existence of the cardinality of an uncountable set.

For instance, in light of the above argument the existence of a well-ordering of all reals is equally "paradoxical" as the existence of ordinal numbers of cardinality equal to (or larger than) the continuum.

Marek Suchenek (July 2, 2013)

Is this technically speaking a theorem (in that it follows from the axiom of choice); or is it a principle (it is equivalent to the axiom of choice)? Chas zzz brown 03:02 Jan 14, 2003 (UTC)

It is a theorem of ZFC, in that it is logically entailed by the axioms of ZFC. One could take it to be an axiom, in which case the proposition conventionally called the "axiom of choice" would be a theorem. But that is not conventionally done. Lots of mathematicians know and use the axiom of choice every day without ever in their lives thinking about well-orderings, so I think that way of doing things is appropriate. Michael Hardy 03:06 Jan 14, 2003 (UTC)

Placing it as part of the default ZFC makes sense to me (I'm pro-Choice :)). I suppose the same goes for Zorn's lemma. BTW, it is helpful when adding new mathematical articles if you could place a link on the List of mathematical topics, so that these articles can be easily tracked when changes are made. Cheers Chas zzz brown 03:15 Jan 14, 2003 (UTC)

Principle/Axiom/Theorem confusion

---

I have always learned that the Well-Ordering Principle is simply that the Naturals are well-ordered, and that the Well-Ordering Principle is equivalent to the Principle of Mathematical Induction. The Well-Ordering Axiom, on the other hand, states that any set can be well-ordered, and that is what this article is about. The Well-Ordering Principle certainly doesn't deserve to be called an axiom, and although the Well-Ordering Theorem can be proved from AC, it can also receive axiom status indifferently - it is independent of ZF.

My point is, it doesn't make sense to say that the Well-Ordering Theorem is "not to be confused with" the Well-Ordering Axiom, when as far as I know, everyone who says "Well-Ordering Axiom" is referring to the Well-Ordering Theorem, not to the Well-Ordering Principle, which is not equivalent to AC. I move that the Well-Ordering Axiom redirect be pointed here, and the phrasing in the parentheses be changed. GTBacchus 07:11, 21 Jun 2004 (UTC)

When I hear "Well ordering axiom/principle/theorem", I always think of the more general one first, and the case restricted to the natural numbers is just a special case. These could actually fit on the same page, with a section about the specialisation to the naturals. (Which obviously has special importance.)

-- Cale Gibbard 18:48, 05 Oct 2007 (UTC)

well-ordering and uncountable

This theorem seems to imply that there is a well-ordering on the reals, albeit not yet conceived-of. Why doesn't this imply that the reals (or any set subject to this theorem for that matter) could be put into 1-1 correspondence with $\mathbb {N}$ in accordance with that particular well-ordering, contradicting the fact that many sets such as the reals are uncountable? Btyner 04:22, 16 February 2006 (UTC)

Because, well, it doesn't. There's no way to construct such a 1-1 correspondence. You are probably thinking of a particular way to construct one, but without knowing which, we can't tell you why it doesn't work. --Mellum 07:35, 16 February 2006 (UTC)

The Well-order article gives the impression that a well-order is just a list such that a given element of the set will be found on the list eventually (?). The well-ordering theorem says such a list of the reals exists. It seems like the uncountability of the reals hinges on the fact that no one has yet conceived of such a list. Btyner 15:13, 16 February 2006 (UTC)

I don't see where it gives this impression. It says that you can make a list and will always know what to take next, but it doesn't say nor imply that this will eventually get every element, except in the finite case. That clearly doesn't even hold for countable sets: If I take 2, 4, 6, ... I always know what to take next and never run out of elements, but I won't hit all elements. --Mellum 20:14, 16 February 2006 (UTC)

Thank you; I think I understand now. By the theorem, there is an ordering on $\mathbb {R}$ such that all subsets thereof have a least element under that ordering. Therefore, $\mathbb {R}$ has a least element, call it $x_{1}$. Now, $\mathbb {R} -\{x_{1}\}$ is a subset of $\mathbb {R}$, so it too has a least element; call it $x_{2}$, and so on. You are saying that the set $\{x_{1},x_{2},\ldots \}$, being countable, leaves out most of $\mathbb {R}$. Btyner 03:31, 17 February 2006 (UTC)

this article is worthless without proof

also, cocks (but seriously guys. i came here looking for a proof. can't you at least give me a linque?) oh yeah re: unsourced: if it had a proof, that would be, well, proof, and the article wouldn't be 'unsourced' because anyone (with the proper background/sufficient time) could understand the proof and know whether the article was correct or not. —Preceding unsigned comment added by 216.15.119.166 (talk) 06:54, 31 January 2008 (UTC)

How do like my sketch of proof? —Preceding unsigned comment added by Adrionwells (talk • contribs) 08:11, 7 November 2009 (UTC)

why is there so much about game theory in this article??

There should be more about set theory. Adrionwells (talk) 15:55, 11 November 2009 (UTC)adrionwells

Split into a separate article Zermelo's theorem (game theory), although I doubt there's enough there to survive. It does not belong in this article. — Arthur Rubin (talk) 17:10, 11 November 2009 (UTC)

"Axiom of choice & its Equivalents"

That looks so ugly in this article. Can someone edit it for the better? — Preceding unsigned comment added by 108.41.98.105 (talk) 21:46, 8 January 2023 (UTC)

The proof of Zorn lemma => well ordering principle is incorrect

Let me reproduce the proof first:

The well-ordering theorem follows from Zorn's lemma. Take the set $\mathbf {A}$ of all well-orderings of subsets of X: an element of $\mathbf {A}$ is an ordered pair (a,b) where a is a subset of X and b is a well-ordering of a. $\mathbf {A}$ can be partially ordered by continuation. That means, define E ≤ F if E is an initial segment of F and the ordering of the members of E is the same as their ordering in F. If ${\mathcal {E}}$ is a chain in $\mathbf {A}$, then the union of the sets in ${\mathcal {E}}$ can be ordered in a way that makes it a continuation of any set in ${\mathcal {E}}$; this ordering is a well-ordering, and therefore, an upper bound of ${\mathcal {E}}$ in $\mathbf {A}$ . We may therefore apply Zorn's Lemma to conclude that $\mathbf {A}$ has a maximal element, say (M,R). The set M must be equal to X, for if X has an element x not in M, then the set M∪{x} has a well-ordering that restricts to R on M, and for which x is larger than all elements of M. This well ordered set is a continuation of (M,R), contradicting its maximality, therefore M = X. Now R is a well-ordering of X.

I take issue with this part:

If ${\mathcal {E}}$ is a chain in $\mathbf {A}$, then the union of the sets in ${\mathcal {E}}$ can be ordered in a way that makes it a continuation of any set in ${\mathcal {E}}$; this ordering is a well-ordering, and therefore, an upper bound of ${\mathcal {E}}$ in $\mathbf {A}$

Contrary to the above, the union of ${\mathcal {E}}$ need not be well-ordered. Let $X=\mathbb {Z}$. Let $A_{n}=\{-n,-(n-1),\ldots ,1,0\}$, and let $E_{n}=(A_{n},\leq |_{A_{n}})$, where $\leq |_{A_{n}}$ is a standard ordering on integers restricted to $A_{n}$. Finally let ${\mathcal {E}}=\{E_{n}:n\in \mathbb {N} \}$. Then the union of chain ${\mathcal {E}}$ is clearly not well ordered. Therefore, I'm removing the erroneous proof. Dodek (talk) 22:45, 24 January 2020 (UTC)

$A_{n}$ is not an initial segment of $A_{n+1}$, since $-(n+1)\in A_{n+1}$ but $-(n+1)\notin A_{n}$. Therefore, your ${\mathcal {E}}$ is not a chain. 65.92.110.77 (talk) 22:21, 4 December 2021 (UTC)

References

"Axiom of choice & its Equivalents"

That looks so ugly in this article. Can someone edit it for the better? — Preceding unsigned comment added by 108.41.98.105 (talk) 21:48, 8 January 2023 (UTC)