A question occurred to me as I was considering an earlier question of mine, and wasn't closely enough related for me to feel I could to include it.

Let's say that a partial order $\langle S,\preceq\rangle$ is

  • well-chained if each chain of $\langle S,\preceq\rangle$ is well-ordered by $\prec,$ and
  • well-founded if every non-empty subset of $S$ has a $\preceq$-minimal element (though not necessarily a $\preceq$-least element, of course).

Clearly, well-founded partial orders are well-chained. Also, well-chained sets are certainly well-founded in $\mathsf{ZFC},$ but it isn't clear to me that this must be the case in the absence of Choice. Is it known whether/how much Choice is needed to prove that well-chained partial orders are well-founded?


This is exactly Dependent Choice.

First note that $\sf DC$ is equivalent to well-foundedness being equivalent with no decreasing sequences. Then note that no decreasing sequences is almost the same as well-chained.

Why just almost? Because it is slightly weaker without assuming $\sf DC$. But here it doesn't matter, exactly because assuming $\sf DC$ fails gives us a tree without maximal elements and without infinite branches. Reversing the tree order gives the counterexample needed (since every chain is finite).

  • $\begingroup$ Excellent! I knew $\mathsf{DC}$ was sufficient for the equivalence of well-foundedness with no decreasing sequences, and I wondered a while ago if it was necessary. Two questions with one answer! $\endgroup$ – Cameron Buie Sep 13 '15 at 16:51

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.