# Well-Ordering Theorem implies Hausdorff Maximal Principle

I have a quick question regarding to the proof that well-ordering theorem implies Maximal Principle. In the proof described here https://proofwiki.org/wiki/Well-Ordering_Theorem_implies_Hausdorff_Maximal_Principle The function is defined as

$$\rho(f:S_x \rightarrow \mathcal{P}(X))\begin{cases} f(S_x)\cup\ \{x\} &\mathrm{if}\ P(S_x,x) \\ f(S_x) & \mathrm{otherwise} \end{cases}$$

however, it doesn't seem to make sense to have $$f(S_x)\cup\{x\}$$ as for example if one has $$X$$ as $$\{1, 2, 3, 4, 5, 6\}$$ then $$f(1)=\{1\}$$ $$f(2)=\{\{1\},\{2\}\}$$ and so on. Thus $$f(S_3)=\{\{1\},\{\{1\},\{2\}\}\}$$ But I think the proof is intended to mean $$f(S_3)=\{1,2\}$$ So shouldn't the function be defined as the following?

$$\rho(f:S_x \rightarrow \mathcal{P}(X))\begin{cases} \cup_{z \in S_x}f(z)\cup\ \{x\} &\mathrm{if}\ P(S_x,x) \\ \cup_{z \in S_x}f(z) & \mathrm{otherwise} \end{cases}$$

## 1 Answer

No, $$2\neq\{2\}$$, so $$X\cup\{2\}\neq X\cup\{\{2\}\}$$. In other words, $$\{1\}\cup\{2\}\neq\{\{1\},\{2\}\}$$.

The proof is quite unclear, but here's the idea. Well-order your partial order. This well-order is not necessarily compatible with your partial order, of course. Now recursively go through the well-order, and start collecting elements into a chain: if you reached a certain point, and you've collected a chain so far, add an element if it is comparable to all the things you've collected so far.

At the end of the recursion process we have a chain, and we can prove it is maximal: if we could have added another element to it, why didn't we do it when we got to it on the well-ordering? Well, the only reason is that we couldn't really add it.

• Thank you for the answer. I'm still confused. I understand if the function $f(1)=1$ and $f(2)=2$ then $f(S_3)=\{1\}\cup\{1,2\}=\{1,2\}$, however the function defined in the proof is assigning the element to some set, not an element. That is, $f(S_3)=\{\{1\}\}\cup\{\{1,2\}\}=\{\{1\},\{1,2\}\}$. In other words, it's a set of sets. This kind of set would not satisfy the ideas you mentioned. – sharkbear May 12 '20 at 13:40
• No, $f(S_x)$ is a chain. It's a subset of $X$. And if we can adjoin $x$ to it, then we do. Otherwise, we do not. – Asaf Karagila May 12 '20 at 13:41
• Thanks for the comments again. I understand it should be a chain for the proof to be consistent. But is the function defined above really forming a chain? – sharkbear May 12 '20 at 13:46
• Yes. As I said, this proof is not very well-written. I'd suggest that you find a different proof that is easier to understand. – Asaf Karagila May 12 '20 at 13:47
• Thank you. I guess what I don't understand is the set operation $f(S_x)\cup\{x\}$. If $f(1)={1}$ and I don't even know how to define $f(2)=f(1)\cup\{2\}$. Is it $\{\{1\},2\}$ or $\{1,2\}$ or $\{\{1\},\{2\}\}$? Is the image of $f(\{1,2\})$ equals to $\{\{1\},\{\{1\},2\}\}$ or $\{1,2\}$ or $\{1,\{1,\{2\}\}\}$? – sharkbear May 12 '20 at 15:48