Prove Hausdorff's Maximality Principle by the W.O.P.

  • #1
317
26

Homework Statement


Show Hausdorff's Maximality Principle is true by the Well-Ordering Principle.

2. Relevant propositions/axioms
WOP HMP AOC.png


The Attempt at a Solution


Case 1: ##\forall x,y\in X## neither ##x\prec y## or ##y\prec x## is true. Hence any singleton subset of ##X## is a maximal linear order.

Case 2: ##\prec## is a linear order on ##X##, then ##X## is itself the maximal linearly ordered subset of ##X##.

Case 3: ##\prec## is undefined on some pairs ##a,b\in X##. Then ##\prec## is not the relation that well-orders ##X## since there exist subsets of ##X## that does not have a least element.
Question: How can I use the Well-Ordering Principle here? I was thinking of defining a new relation ##\prec_w## that well-orders a finite ##W\subseteq X##, but I'm thinking that that cannot be right since ##\prec_w## is not an arbitrary partial-order relation in ##X##. Which part of this problem should I think more about in order to help me proceed? Or May I simply say that we remove all elements in ##X## that has an undefined relation with all other elements in ##X##?

EDIT: (Alternative case 3: W.O.P.##\rightarrow## A.C. ##\rightarrow## H.M.P.)
Suppose ##\{X_{\lambda}\}_{\lambda\in\Lambda}\neq\emptyset## and ##\forall\lambda\in\Lambda, X_{\lambda}\neq\emptyset##. We want to show ##\prod_{\lambda\in\Lambda}X_{\lambda}\neq\emptyset##. By the well-ordering principle, ##\exists\prec_{x}\forall\lambda\in\Lambda##, ##X_\lambda## is well-ordered; that is with respect to ##\prec_x##, ##\forall\lambda\in\Lambda\forall W\subseteq X_{\lambda}##, ##W## has a least element. Hence, we can simply define a choice-function ##f: \{X_\lambda\}_{\lambda\in\Lambda}\rightarrow\bigcup_{\lambda\in\Lambda}X_\lambda## such that ##f(X_{\lambda})=x_{0}^{\lambda}## denote the least element in ##X_{\lambda}##. Therefore, ##\prod_{\lambda\in\Lambda}X_{\lambda}\neq\emptyset##.

Finally, we want to show A.C. ##\rightarrow## H.M.P. Suppose ##\prec## does not well-order ##X##, then ##\exists a,b\in X## where neither ##a\prec b## or ##b\prec a## are true. Consider some partition of ##X## denoted ##P[X]##. Define ##\hat{X}:=\{\hat{x}\in X:\forall\overline{X}\in P[X]\forall x\in\overline{X},\neg (\hat{x}\prec x\quad\lor\quad x\prec\hat{x})\}##. By the axiom of choice, ##\hat{X}\neq\emptyset##. Thus, ##X^*=X\setminus\hat{X}## is linearly ordered such that ##\forall x\in\hat{X}, X^*\cup\{x\}## is no longer linearly ordered. Therefore, ##X^*\subseteq X## is a maximal linearly ordered subset of ##X##.

So I think I have two questions. First, is how to proceed directly from W.O.P. to H.M.P. and second, is I would like a verification on my alternative case 3 (i.e. did I use W.O.P. and A.C. correctly?)
 

Attachments

Last edited:

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,886
1,454
I can't follow your reasoning in the last paragraph. It does not seem to me that AC implies that ##\hat X\neq \emptyset##. Consider the case X={a,b,c,d} with the only order relations being a>b and c>d. Then X is not well-ordered because the subset {b,c} has no first element. Also, neither b<c nor c<b is true. But every element of X is in one order relation, so no element can be in ##\hat X##, hence ##\hat X=\emptyset##.

Also, is the principle of transfinite induction or the principle of transfinite recursive definition in your toolkit? They can sometimes be useful in making proofs of things like this.
 
  • Like
Likes Terrell
  • #3
317
26
the principle of transfinite recursive definition in your toolkit?
I'll consider using this when I get my mind back to this problem. Thanks for the hint! :)
 

Related Threads on Prove Hausdorff's Maximality Principle by the W.O.P.

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
472
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
8
Views
6K
Replies
3
Views
5K
Replies
0
Views
2K
  • Last Post
Replies
3
Views
2K
Replies
1
Views
3K
Top