A theorem in my textbook says:

Let $(A, < )$ be a totally ordered set. Set A has a least element and principle of transfinite induction holds in A if and only if A is well ordered.

I understand why you need an assumption that A has a least element to prove left-to-right implication in my textbook proof of this theorem. But I can't find an example of the non-well-ordered set where principle of transfinite induction holds... Obviously, that set doesn't have a least element but that ''hint'' didn't take me far.

So, can someone help me?

EDIT: (Due to Brian M. Scott)

We state principle of transfinite induction as follows:

Let $(A, <)$ be a totally ordered set and $B \subseteq A$ which satisfies:

$$ (\forall x \in A) (p_A(x) \subseteq B \implies x \in B) $$

Then B = A.

( where $p_A(x) = \{ a \in A : a < x \}$ )

  • 1
    $\begingroup$ Exactly how do you state the principle of transfinite induction? $\endgroup$ – Brian M. Scott Dec 19 '12 at 12:26
  • $\begingroup$ I'll add exact statement to the post. $\endgroup$ – ante.ceperic Dec 19 '12 at 12:49
  • $\begingroup$ Also, which definition of well-orderedness are you using? $\endgroup$ – Peter LeFanu Lumsdaine Dec 21 '13 at 18:38

You are stating the principle as essentially $$ (\forall x)[(\forall y < x) P(y) \to P(x)] \to (\forall x) P(x) $$ where the quantifiers range over an ordered set $A$.

I claim that if the set has no least element then the principle does not hold. Take $P(z)$ to be $z \not = z$. Fix any $x \in A$. Because $x$ is not minimal, there is some $y < x$, and $P(y)$ is false, so $(\forall y < x)P(y)$ is false. Also $P(x)$ is false. Thus $(\forall x)[(\forall y < x) P(y) \to P(x)]$ is true. But $P(x)$ is false for all $x$, so the principle gives an incorrect result.

Thus, by contraposition, if the transfinite induction principle holds then $A$ does have a least element. The assumption of a least element in the theorem mentioned in the question is superfluous.

If the set did have a least element $x_0$, then $(\forall y < x_0) Q(y)$ would be true regardless what $Q$ is. That is the way that the transfinite induction principle is able to avoid proving identically false statements such as the $P$ I chose above. The intuition to have is that when we look at non-minimal elements, the "inductive" part of the principle of mathematical induction or the principle of transfinite induction will always go through for false statements.


I’m guessing that your version of the principle of transfinite induction is something like this:

If $(\forall y<x)P(y)$ implies $P(x)$ for each $x\in X$, then $(\forall x\in X)P(x)$.

If so, try taking $X=\Bbb Z$. I’ve also included a spoiler-protected hint for a property $P(x)$ that would work. (There are many.) Mouse-over to see it.

For $P(x)$ you could try $x=x+1$.

  • $\begingroup$ Yes, you provided an example of non-well-ordered set where principle of transfinite induction does not hold. I'm interested in a non-well-ordered set where principle of transfinite induction HOLDS (it's use gives good results). I'm actually wondering why do we NEED that ''A has a least element'' assumption in theorem I cited. Can we leave it out? $\endgroup$ – ante.ceperic Dec 19 '12 at 12:48
  • 1
    $\begingroup$ @ante: It’s the absence of a least element that makes my example work. But we need to know exactly how you’re stating the principle of transfinite induction: in some versions it incorporates the assumption of a least element. $\endgroup$ – Brian M. Scott Dec 19 '12 at 12:50
  • $\begingroup$ You are providing me with an example of non-well-ordered set where transfinite induction principle doesn't hold. You use it to get to the wrong conclusion. I'm interested in the non-well-ordered set where PTI holds (it's use gives us a good conclusion for every P). Are there any? $\endgroup$ – ante.ceperic Dec 19 '12 at 12:57
  • $\begingroup$ @ante: Okay, I see what you’re asking now. I’ll have to give that some thought; I don’t see a proof that doesn’t use the assumption of a least element, but I don’t immediately see a counterexample without it. $\endgroup$ – Brian M. Scott Dec 19 '12 at 13:10

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.