Zorn's lemma and maximal linearly ordered subsets

Question

Let $T$ be a partially ordered set. We say $T$ is a tree if $\forall t\in T$ $\{r\in T\mid r < t\}$ is linearly ordered (such orders can be considered on connected graphs without cycles, i.e. on trees). By a branch we mean a maximal linearly ordered subset in $T$.

It is easy to prove that each tree has a branch using Zorn's lemma. However, the converse is also true (I read it recently in an article). Can anybody give a sketchy proof?

Answer 1

Assume that we have a poset $(X,\leq)$ such that each linearly ordered subset of it has an upper bound. Define the following tree:

$s\in T$ if $s\subseteq X$ and $(s,\leq)$ is a linear order and let the order relation of the tree be $s<t$ if and only if $s$ is an initial segment of $t$. It's easy to see that this is a tree. Now take a branch of the tree, $B$. If you take $(\bigcup B,\leq)$ you have a linearly ordered set. By the assumption it has an upper bound, $x$. This upper bound is a maximal element of $X$. Indeed if $x<y$ then $\bigcup B\cup\{y\}$ is above (w.r.t. the tree order) every element of $B$, contradicting the maximality of $B$.

Answer 2

Here is a nice way of proving the well-ordering principle from "Every tree has a branch":

Let $A$ be an infinite set, and let $\lambda$ be the least ordinal such that there is no injection from $\lambda$ into $A$. Consider the set $A^{<\lambda}$, that is all the functions from ordinals smaller than $\lambda$ into $A$, and order those by end-extension (which is exactly $\subseteq$ if you think about it for a moment).

It is not hard to verify that $(A^{<\lambda},\subseteq)$ is a tree. Therefore it has a branch. Take the union of that branch, and we have a "maximal" function $f$ whose domain is an ordinal $\alpha<\lambda$. Note that it has to be a maximal element, otherwise we can extend it and the branch was no branch.

If the range of $f$ is not all $A$ then there is some $a\in A$ which witnesses that, and we can extend $f\cup\{\langle\alpha,a\rangle\}$ to a strictly larger function. Since $f$ is maximal, it follows it has to be a surjection, and therefore $A$ can be well-ordered.

(Note: If we restrict to the sub-tree of the injective functions we can pull the same trick and end up with a bijection, but a surjection from an ordinal is just as good).

From this we have that every set can be well-ordered, and therefore the axiom of choice holds.