Consider the following exercise:

Let $r$ be a binary relation on a set $a$. Show that $r$ is well-founded iff there exists a function $h:a\to \alpha$ for some ordinal $\alpha$, suc hthat $(x,y)\in r$ implies $h(x)<h(y)$. Deduce that if every set can be well-ordered, then any well-founded binary relation on a set can be extended to a well-ordering.

"$\implies$". Suppose $r$ well-founded. Let $a_0 = a$. Choose $r$-minimal element $x_0\in a_0$, and let $h(x_0) = \emptyset$. Now for each $i=1, 2, \ldots$ let $a_i =a_{i-1}\backslash\{x_{i-1}\}$, choose $r$-minimal element $x_i\in a_i$, and let $h(x_i) = h(x_{i-1}) \cup \{h(x_{i-1})\}$. Then $h$ satisfies the desired property.

"$\impliedby$". Given $h:a\to\alpha$ with the desired property. For a given $\emptyset\neq s\subseteq a$, choose $x\in s$ s.t. $h(x)$ is $<$-minimal. Then $x$ is $r$-minimal.

Now let $r$ be well-founded on $a$. Note that the transitive closure of $r$ must be antisymmetric. Thus the transitive reflexive closure of $r$ is a partial ordering, which extends to a total ordering $r'$ by Zorn's lemma.

I'm not sure if my proofs for above implications are rigorous enough. I also struggle to make explicit why the strict version of $r'$ must still be well-founded.


1 Answer 1


I don't really understand your definition of $h$ in the $\implies$ part, it seems that it might depend very much on the choices of $x_i$ at each step. You should just define $h$ directly, and there's really just one natural way of doing that: $$h(x)=\sup\{h(y)+1\mid y\mathrel{r}x\}$$ The definition is a recursive definition, of course. If you defined $h$ for all the elements below $x$, then we define it for $x$. We call this $h$ the rank function.

The other direction is fine.

Now, for the extension part, how do you extend a partial order to a linear order? You essentially show that you can always extend by adding one pair and then appeal to Zorn's lemma. Now two points need to be addressed here:

  1. Every set can be endowed with a well-founded relation (the trivial relation, for example), so you're asking to prove that every set can be well-ordered. This means that you really need to use the axiom of choice in its full power here.

  2. The statement that every partial order can be extended to a linear order is much weaker than the axiom of choice, as far as things go. So you will to slightly modify the idea behind the usual proof.

The idea is that if you had $h$ as above, but instead of being as minimal as possible, it would be injective (so different minimal elements are mapped to different ordinals), then you could add the requirement that you extend the partial order according to which element got a higher ordinal assigned to it.

Now we define $h$ as above, this is your rank function, now by induction on the rank define $H$ such that if $h(x)<h(y)$ then $H(x)<H(y)$. You can do this, for example, by first choosing a well-ordering of the $r$-minimal elements (those of rank $0$), then stacking on that the elements of rank $1$, and so on.

Finally, show that $H$ induces a well-ordering which extends $r$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .