5
$\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 \}$ )

  • 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
    @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