2
$\begingroup$

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$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 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
    You are using recursion to define $H$. I guess that in your definition of $H$ you mean $\{x\}\cup\bigcup_{y.2012-02-28
  • 0
    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? :-)2012-02-28

1 Answers 1

3

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.

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$$\{x\in S: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$x\in S$, then $H(x)=\{x\}$, and if $x\notin S$, then $H(x)=\varnothing$, so $$\bigcup_{x Moreover, Since $y$ is the $\le$-least element of $S'\setminus S$, $$\{x\in S:x

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

  • 0
    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$?2012-02-28
  • 0
    @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, without which the proof doesn’t work.2012-02-28