0
$\begingroup$

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} $$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$ – sharkbear May 12 '20 at 13:40
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila May 12 '20 at 13:41
  • $\begingroup$ 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? $\endgroup$ – sharkbear May 12 '20 at 13:46
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila May 12 '20 at 13:47
  • $\begingroup$ 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\}\}\}$? $\endgroup$ – sharkbear May 12 '20 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.