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

  • 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. But there’s still a problem: how do you know that $\{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; if $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 Finally, \{y\}\cup\{x\in S':x, so \{y\}\cup\bigcup_{x 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.

  • 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