PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (198)
Orphanage
Unclass'd
Unproven (490)
Corrections (7)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Medium Entry average rating: No information on entry rating
[parent] proof of Zermelo's well-ordering theorem (Proof)

Let $ X$ be any set and let $ f$ be a choice function on $ \mathcal{P}(X)\setminus\{\emptyset \} $. Then define a function $ i$ by transfinite recursion on the class of ordinals as follows:

$\displaystyle i(\beta)=f(X-\bigcup_{\gamma<\beta} \{i(\gamma)\})$ unless $\displaystyle X-\bigcup_{\gamma<\beta} \{i(\gamma)\}=\emptyset$ or $\displaystyle i(\gamma)$ is undefined for some $\displaystyle \gamma<\beta$

(the function is undefined if either of the unless clauses holds).

Thus $ i(0)$ is just $ f(X)$ (the least element of $ X$), and $ i(1)=f(X-\{i(0)\})$ (the least element of $ X$ other than $ i(0)$).

Define by the axiom of replacement $ \beta=i^{-1}[X]=\{\gamma\mid i(\gamma)=x$    for some $ x\in X\}$. Since $ \beta$ is a set of ordinals, it cannot contain all the ordinals (by the Burali-Forti paradox).

Since the ordinals are well ordered, there is a least ordinal $ \alpha$ not in $ \beta$, and therefore $ i(\alpha)$ is undefined. It cannot be that the second unless clause holds (since $ \alpha$ is the least such ordinal) so it must be that $ X-\bigcup_{\gamma<\alpha} \{i(\gamma)\}=\emptyset$, and therefore for every $ x\in X$ there is some $ \gamma<\alpha$ such that $ i(\gamma)=x$. Since we already know that $ i$ is injective, it is a bijection between $ \alpha$ and $ X$, and therefore establishes a well-ordering of $ X$ by $ x<_Xy\leftrightarrow i^{-1}(x)<i^{-1}(y)$.

The reverse is simple. If $ C$ is a set of nonempty sets, select any well ordering of $ \bigcup C$. Then a choice function is just $ f(a)=$ the least member of $ a$ under that well ordering.



"proof of Zermelo's well-ordering theorem" is owned by Henry.
(view preamble)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: ordering, simple, well-ordering, bijection, injective, Burali-Forti paradox, contain, ordinals, axiom, least element, clauses, class of ordinals, transfinite recursion, function, choice function
There are 2 references to this entry.

This is version 6 of proof of Zermelo's well-ordering theorem, born on 2002-08-25, modified 2007-03-12.
Object id is 3359, canonical name is ProofOfZermelosWellOrderingTheorem.
Accessed 5701 times total.

Classification:
AMS MSC: 03E25 (Mathematical logic and foundations :: Set theory :: Axiom of choice and related propositions)
Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)