# Well ordering and maximal principle

I have to prove that given any poset $(P,\preceq)$ there exists a chain $S$ such that it is maximal (meaning that if $S\subseteq S'$ then $S=S'$). The book contains a proof using the axiom of choice. The homework assignment is asking me to give an alternate proof using the well-ordering theorem (which is actually equivalent to choice) and transfinite recursion theorem. I managed to prove it in a way that I will show below, however I do not know how to use the transfinite recursion theorem (I might be using it without even knowing it), so if someone can help me point out with I need the transfinite recursion theorem I will be very grateful.

Proof: Assume that $(P,\preceq)$ is a poset. By the Well-ordering theorem, we know that we can impose a well ordering in any set, let this order by given $\leq$ (i.e., $(P,\leq)$ is well ordered). Consider the definite unary condition $H$: $$H(x) = \left\{ \begin{array}{ll} \{x\} & \mbox{if }x\in P \mbox{ and }x\cup\bigcup_{y<x} H(y) \mbox{ is totally ordered with respect to} \preceq \\ \emptyset & \mbox{otherwise} \end{array} \right.$$ Then we can consider the set $S=\bigcup_{x\in P} H(x)$. We claim that this yields a maximal chain in $(P,\preceq)$. We want to show that if $S'$ is a chain such that $S\subseteq S'$ then $S=S'$. Let $y\in S'$. Then, we consider $\{y\}\cup X$ where $X$ is a subset of $S$ and $x<y$ for all $x\in X$. Since this is a subset of $S'$ it is well-ordered, and in particular it is totally ordered. Thus, $H(y)=\{y\}$ and we must have that $y\in S$.

-
You are using recursion to define $H$. I guess that in your definition of $H$ you mean $\{x\}\cup\bigcup_{y<x}H(y)$. –  azarel Feb 28 '12 at 5:30
I have to say that you did not convince me with the proof as presented here. If I were to grade such a solution, either the course is small and I can take my time thinking about your solution; or the course is big and I would probably deduct some points but will give you the opportunity to explain this solution to me in person. Good thing I have to grade a whole other course, eh? :-) –  Asaf Karagila Feb 28 '12 at 8:38

You need the transfinite recursion theorem in order to justify the recursive definition of the function $H$: it’s the theorem that justifies defining $H(x)$ in terms of the values of $H$ at points $y<x$.

Your proof that $S$ is a maximal chain needs just a little work. First, you really should say explicitly why $S$ is a chain: if $x,y\in S$, then without loss of generality $x\le y$, in which case by construction $x\preceq y$ or $y\preceq x$.

When you pick $y\in S'$ and consider $\{y\}\cup X$, you need to be more specific: you want $X$ to be the set of all $x\in S$ such that $x<y$. But there’s still a problem: how do you know that $$\{x\in S:x<y\}=\bigcup_{x<y}H(x)\;?$$ Without that, you can’t be sure that $H(y)\ne\varnothing$.

Here’s the other place (besides the recursion theorem) where you want to use the fact that $\le$ is a well-ordering. Suppose that $S'$ is a chain properly containing $S$. Then $S'\setminus S$ has a $\le$-least element $y$. Now consider $H(y)$. Suppose that $x<y$; if $x\in S$, then $H(x)=\{x\}$, and if $x\notin S$, then $H(x)=\varnothing$, so $$\bigcup_{x<y}H(x)=\{x\in S:x<y\}\;.$$ Moreover, Since $y$ is the $\le$-least element of $S'\setminus S$, $$\{x\in S:x<y\}=\{x\in S':x<y\}\;.$$ Finally, $\{y\}\cup\{x\in S':x<y\}\subseteq S'$, so $$\{y\}\cup\bigcup_{x<y}H(x)=\{y\}\cup\{x\in S':x<y\}$$ is linearly ordered, and hence by definition $H(y)=\{y\}$, and $y\in S$ after all.

Thus, $S'\setminus S$ can have no $\le$-least element and must therefore be empty.

-
I have a question: Since the chains are subsets of $(P,\preceq)$ why do you pick the least element in $S'\backslash S$ with respect to $\leq$ and not with respect to $\preceq$? –  Daniel Montealegre Feb 28 '12 at 9:32
@Daniel: Two reasons. First, $\preceq$ need not be a well-ordering, so there may not be a least element of $S'\setminus S$ with respect to $\preceq$. Secondly, I need the fact that $y$ is the $\le$-least element of $S'\setminus S$ to say that $\{x\in S:x<y\}=\{x\in S':x<y\}$, without which the proof doesn’t work. –  Brian M. Scott Feb 28 '12 at 9:38