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

  • 1
    $\begingroup$ You are using recursion to define $H$. I guess that in your definition of $H$ you mean $\{x\}\cup\bigcup_{y<x}H(y)$. $\endgroup$ – azarel Feb 28 '12 at 5:30
  • $\begingroup$ 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? :-) $\endgroup$ – 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.

  • $\begingroup$ 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$? $\endgroup$ – Daniel Montealegre Feb 28 '12 at 9:32
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Feb 28 '12 at 9:38

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.