Transfinite induction

Question

Is it true that while using transfinite induction we dont need to prove the zero case? because, if we want to prove some property $ \psi $ , we assume that for any $ x\in A $ if for any $ y\leq x $ it follows that if $ \psi\left(y\right) $ then also $ \psi\left(x\right) $ holds. the minimum object $a\in A $ also follows that $ a\leq x $. So should we prove for the zero case ?

If not, I'll be glad to see some counterexample where we can prove a wrong argument just because we havent proved the first case. Thanks

Answer 1

You are (almost) correct. Actually:
We want to prove some property $\psi$ ,
We prove that $$ (\forall x \in A)\big[(\forall y \in A)(y<x \rightarrow\psi(y))\;\rightarrow\; \psi(x)\big] \tag1$$ Then we may conclude that $$ (\forall x \in A)(\psi(x)) \tag2$$

And of course if $0$ is the least element of $A$, then $$ (\forall y \in A)(y<0 \rightarrow\psi(y)) \tag3$$ is vacuously true. So if we proved $(1)$, then taking $x=0$ we conclude $\psi(0)$ with no additional effort.

---

Stated the other way: if the "base case" $\psi(0)$ is false, then since (vacuously) $(3)$ is true, we have that (1) is false.

Answer 2

Induction, transfinite or otherwise, is a tool. And the thing about tools is that they need to be useful. Just like a chef's knife can do most things in the kitchen, but it's not going to do everything as well as specialised knives.

The general form formulation of induction is $(\forall x(A_{<x}\to A(x)))\to\forall x A(x)$. It works in every well-founded situation, and in fact exactly in well-founded situations.

But we normally like to think about the linear case (even when it's very much not the right thing to thing about). Because the linear case has a linear structure. It has a first step, then a next one, and so on. So we can conceptualise induction better: $(A(0)\land \forall x(A(x)\to A(x^+)))\to\forall x A(x)$, as the "usual induction" is structured.

What happens in the transfinite case, though? Well, in the transfinite case we need to contend with limit stages, not just base case and successors. And for that we need to formulate a separate hypothesis, and it looks like the "general induction": if $x$ is not a successor, and $A_{<x}$, then $A(x)$.

So we can formulate transfinite induction as follows: let $A$ be a class of ordinals such that:

1. $0\in A$.
2. If $\alpha\in A$, then $\alpha+1\in A$.
3. If $\alpha$ is a limit ordinal and $\alpha\subseteq A$, then $\alpha\in A$.

Then $A=\mathrm{Ord}$. Now it's not too hard to prove that this is equivalent to the general principle of transfinite induction.

---

So why do we care, or bother? Well, remember what I said about knives? Sometimes it's easier to use this tool. Sometimes the proof naturally splits into different parts.

For example, if you want to prove the recursive definition of ordinal addition, $$\alpha+0=\alpha; \alpha+(\beta+1)=(\alpha+\beta)+1; \alpha+\beta=\sup\{\alpha+\gamma\mid\gamma<\beta\}\text{ for limits},$$ is equivalent to the order-sum definition, this lends itself quite well to separating the three cases.

Or, when you construct by transfinite recursion a maximal chain in a partial order (using a choice function, of course), you need to prove by induction that the chain is maximal. And since the construction is a continuous construction (namely, taking union at limit steps), the work splits naturally to limit and non-limit.

So in these cases, it is sometimes worth to split into successor/limit; and you can either lump $0$ into limits, sometimes, but many times the $0$th step is defined as some explicit object, which means it separates naturally as well.