Why transfinite induction only works on well-ordered set?

Question

Could you please help me to know why transfinite induction only works on well-ordered set and not arbitrary set ? Why the fact that every susbset has a least element is necessary for transfinite induction principle ?

Thank you very much!

Answer 1

I will expand here on my comment. Let $(X,\le)$ be a totally ordered set. We will prove that it is necessary for the order relation $\le$ to be a well ordering, if we want the transfinite induction to work.

Suppose, otherwise, that $S$ is a nonempty subset of $X$ which does not have a minimum. The predicate $P(x):=x\not\in S$ is therefore not true on the entire $X$ (as $S$ is nonempty), in other words $(\forall x)P(x)$ is false. Yet, $P$ satisfies the condition for transfinite induction:

$$(\forall y<x)P(y)\implies P(x)$$

This is true if $x\not\in S$ (as the consequent is true), but is also true if $x\in S$ !!! Namely, as $x$ is not the minimum of $S$ and the ordering is total, there is a smaller $y\in S, y<x$, and then $P(y)$ is false, and the entire implication is vacuously true.

In other words, transfinite induction didn't work - it proved a false statement $(\forall x)P(x)$.

Answer 2

Let's keep things simple. As any induction, transfinite induction requires two ingredients : 1) order, because the main point of induction is "statement $n$ $\Rightarrow$ statement $n+1$", and 2) a base case (e.g. $n = 0$).

Indeed, without an initial statement, the chain of induction can't be true, because each step depends on the previous one, but a starting point is needed.

In consequence, in a more general context, the set indexing the statements requires a total order to ensure the first ingredient and a minimal element to represent the starting point of the chain of induction, hence well-order. Moreover, in the case of transfinite induction, each limit ordinal corresponds to a new starting point.