# A non-well-ordered set where principle of transfinite induction holds?

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? – Brian M. Scott Dec 19 '12 at 12:26
I'll add exact statement to the post. – ante.ceperic Dec 19 '12 at 12:49

## 2 Answers

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$.

-
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? – ante.ceperic Dec 19 '12 at 12:48

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. – Brian M. Scott Dec 19 '12 at 12:50
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? – ante.ceperic Dec 19 '12 at 12:57
@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. – Brian M. Scott Dec 19 '12 at 13:10
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 29, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9204013347625732, "perplexity_flag": "head"}