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 (204)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] Zorn's lemma and the well-ordering theorem equivalence of Hausdorff's maximum principle (Proof)

Hausdorff's maximum principle implies Zorn's lemma.

Consider a partially ordered set $ X$, where every chain has an upper bound. According to the maximum principle there exists a maximal totally ordered subset $ Y\subseteq X$. This then has an upper bound, $ x$. If $ x$ is not the largest element in $ Y$ then $ \{x\}\cup Y$ would be a totally ordered set in which $ Y$ would be properly contained, contradicting the definition. Thus $ x$ is a maximal element in $ X$.

Zorn's lemma implies the well-ordering theorem.

Let $ X$ be any non-empty set, and let $ \mathcal{A}$ be the collection of pairs $ (A,\leq)$, where $ A\subseteq X$ and $ \leq$ is a well-ordering on $ A$. Define a relation $ \preceq$, on $ \mathcal{A}$ so that for all $ x,y\in\mathcal{A}: x\preceq y$ iff $ x$ equals an initial of $ y$. It is easy to see that this defines a partial order relation on $ \mathcal{A}$ (it inherits reflexibility, anti symmetry and transitivity from one set being an initial and thus a subset of the other).

For each chain $ C\subseteq\mathcal{A}$, define $ C'=(R,\leq')$ where R is the union of all the sets $ A$ for all $ (A,\leq)\in C$, and $ \leq'$ is the union of all the relations $ \leq$ for all $ (A,\leq)\in C$. It follows that $ C'$ is an upper bound for $ C$ in $ \mathcal{A}$.

According to Zorn's lemma, $ \mathcal{A}$ now has a maximal element, $ (M,\leq_M)$. We postulate that $ M$ contains all members of $ X$, for if this were not true we could for any $ a\in X-M$ construct $ (M_*,\leq_*)$ where $ M_*=M\cup\{a\}$ and $ \leq_*$ is extended so $ S_a(M_*)=M$. Clearly $ \leq_*$ then defines a well-order on $ M_*$, and $ (M_*,\leq_*)$ would be larger than $ (M,\leq_M)$ contrary to the definition.

Since $ M$ contains all the members of $ X$ and $ \leq_M$ is a well-ordering of $ M$, it is also a well-ordering on $ X$ as required.

The well-ordering theorem implies Hausdorff's maximum principle.

Let $ (X,\preceq)$ be a partially ordered set, and let $ \leq$ be a well-ordering on $ X$. We define the function $ \phi$ by transfinite recursion over $ (X,\leq)$ so that
$\displaystyle \phi(a) = \begin{cases} \{a\} &\text{if }\{a\}\cup\bigcup_{b<a}\p... ...is totally ordered under }\preceq.\ \emptyset &\text{otherwise}. \end{cases}.$
It follows that $ \bigcup_{x\in X}\phi(x)$ is a maximal totally ordered subset of $ X$ as required.



"Zorn's lemma and the well-ordering theorem equivalence of Hausdorff's maximum principle" is owned by mathcam. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

See Also: Zorn's lemma, axiom of choice, Zermelo's well-ordering theorem, Hausdorff's maximum principle

Other names:  proof ofZorn's lemma, proof of Hausdorff's maximum principle, proof of the maximum principle

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

Cross-references: transfinite recursion, function, contains, postulate, Zorn's lemma, union, transitivity, symmetry, partial order, easy to see, iff, relation, well-ordering, collection, maximal element, contained, totally ordered set, subset, totally ordered, maximum principle, upper bound, chain, partially ordered set
There is 1 reference to this entry.

This is version 6 of Zorn's lemma and the well-ordering theorem equivalence of Hausdorff's maximum principle, born on 2002-09-29, modified 2007-06-24.
Object id is 3493, canonical name is ZornsLemmaAndTheWellOrderingTheoremEquivalenceOfHaudorffsMaximumPrinciple.
Accessed 10338 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)