4
$\begingroup$

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
    Exactly how do you state the principle of transfinite induction?2012-12-19
  • 0
    I'll add exact statement to the post.2012-12-19
  • 0
    Also, which definition of well-orderedness are you using?2013-12-21

2 Answers 2

4

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.

2

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

If $(\forall 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$.

  • 0
    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?2012-12-19
  • 1
    @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.2012-12-19
  • 0
    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?2012-12-19
  • 0
    @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.2012-12-19