Well-ordering theorem

From Wikipedia, the free encyclopedia

In Mathematics, the well-ordering theorem (not to be confused with the well-ordering principle) states that every set can be well-ordered. This is known as the Zermelo's theorem and is equivalent to the Axiom of Choice as a result of a theorem which states that if every set can be well ordered, then for every set there exists a choice function.^[1][2]Ernst Zermelo then introduced the Axiom of Choice as an "unobjectionable logical principle" to prove the well-ordering theorem. This is important because it makes every set susceptible to the powerful technique of transfinite induction. The well-ordering theorem has consequences that may seem paradoxical, such as the Banach–Tarski paradox.

Contents 1 History 2 Zermelo's theorm in game theory 3 See also 4 Further reading 5 References

[edit] History

Georg Cantor considered the well-ordering theorem to be a "fundamental principle of thought." Most mathematicians however find it difficult to visualize a well-ordering of, for example, the set R of real numbers. In 1904, Gyula Kőnig claimed to have proven that such a well-ordering cannot exist. A few weeks later, though, Felix Hausdorff found a mistake in the proof. It turned out though, that the well-ordering theorem is equivalent to the axiom of choice, in the sense that either one together with the Zermelo-Fraenkel axioms is sufficient to prove the other, in first order logic. (The same applies to Zorn's Lemma.) In second order logic, however, the well-ordering theorem is strictly stronger than the axiom of choice: from the well-ordering theorem one may deduce the axiom of choice, but from the axiom of choice one cannot deduce the well-ordering theorem.^[3]

[edit] Zermelo's theorm in game theory

Zermelo’s theorem says that in any finite two-person game of perfect information in which the players move alternatively and in which chance does not affect the decision making process, if the game cannot end in a draw, then one of the two players must have a winning strategy.^[4] Zermelo's theorem has become mathematical folklore. Throughout literature in the last century, variations of the theorem has appeared in several forms. Some claimed that Zermelo proved something that he did not, namely that Chess, or a more general class of game, was determinate. Others claim he used a method of proof, known as 'backwards induction' that was not employed until 1953, by von Neumann and Morgenstern. Ken Binmore (1992) writes, Zermelo used this method way back in 1912 to analyze Chess. It requires starting from the end of the game and then working backwards to its beginning.

Zermelo did no such thing. Worst of all is the claim by M.A. Dimand and R.W. Dimand in 1996 that in a finite game, there exists a strategy whereby a first mover ... cannot lose, but it is not clear whether there is a strategy whereby the first mover can win. Not only is this not what Zermelo stated, but in fact there is no reason to assume that the statement attributed to him is even true.

That Zermelo's paper was originally published only in German may have been a significant factor leading to the confusion regarding what was discussed therein. Regardless, the falsities in modern literature these days are a warning about taking for granted what is written before.

Since Ulrich Schwalbe and Paul Walker faithfully translated Zermelo's paper in 1997 and published the translation in the appendix to Zermelo and the History of Game Theory^[5], it has become easier to determine the truth of what is discussed. Zermelo considers the class of two-person games without chance, where players have strictly opposing interests and where only a finite number of positions are possible. Chess is an obvious example of such a game. ^[6]

[edit] See also

• Well-ordering principle
• Game theory

[edit] Further reading

• Zermelo and the Early History of Game Theory

[edit] References

1. ^ http://books.google.com/books?id=rqqvbKOC4c8C&pg=PA15&lpg=PA15&dq=%22Zermelo+THEOREM%22&source=bl&ots=P9kXF08yZa&sig=jTRhXTVFGbf0jNIyjDCZIdQfH2k&hl=en&ei=ZD9MSsPXM5HSM572heoD&sa=X&oi=book_result&ct=result&resnum=4
2. ^ http://books.google.com/books?id=ewIaZqqm46oC&pg=PA458&lpg=PA458&dq=%22Zermelo+THEOREM%22&source=bl&ots=VTDYEoXyU8&sig=Ty7hPYEKesfaA3Wm0LiKZk7tV3I&hl=en&ei=oEVMSsbTAov8MJKn7PMD&sa=X&oi=book_result&ct=result&resnum=9
3. ^ Stewart Shapiro, 1991, "Foundations Without Foundationalism: A Case for Second-Order Logic". Oxford University Press.
4. ^ http://hkumath.hku.hk/~ntw/EMB(giftedstudents_6-April-2008).pdf
5. ^ http://www.math.harvard.edu/~elkies/FS23j.03/zermelo.pdf
6. ^ http://www.gap-system.org/~history/Projects/MacQuarrie/Chapters/Ch4.html