What is the meaning of "induction up to a given ordinal"?

Question

Given an ordinal $\alpha$, what does it mean: "induction up to $\alpha$"? When $\alpha=\omega$, is this is ordinary mathematical induction? Also, Goodstein's Theorem is equivalent to "induction up to $\varepsilon_{0}$". But I am not sure what this means.

What is an example of "induction up to 10"? (or any other number). What is an example of "induction up to $\omega^{2}$"? What about "induction up to $\omega^{\omega}$"?

Answer 1

There is an Induction scheme, up to (on) some Ordinal $\alpha$, for some formula $\phi$

$$\forall\delta\in \alpha\,[\forall\beta\in\delta\,(\phi(\beta)\rightarrow\phi(\delta))]\rightarrow\forall\delta\in\alpha\,\phi(\delta)$$

It can be shown, that the above scheme is true for any ordinal $\alpha$ and any $\phi$ in the language of set theory.

Note: Induction on Ordinals larger than $\omega$ is called Transfinite Induction.

Induction up to $\omega$, is just replacing $\alpha$ with $\omega$ in the above statement.

And it is equivalent with Induction on the natural numbers.

We use this schema when trying to show $\phi$ is true for every ordinal up to some ordinal $\alpha$.

It looks like this:

Fix $\delta\in\alpha$

Assume $\forall\beta\in\delta\,\phi(\beta)$ is true (Inductive Hypothesis).

Prove $\phi(\delta).$

Then, since the Inductive Schema is true, by Modus Ponens, $\forall\delta\in\alpha\,\phi(\delta)$ must be true.

It's a good exercise to Prove why Induction works.

Hint: Try a proof by contradiction, Use the Well-Ordering Principle.

Answer 2

Induction up to $\omega^2$ can occur (implicitly at least) when we have to show something like $\forall i \in\mathbb{N} \, \forall j \in\mathbb{N} \,\,[\,P(i,j)\,] $. We can write this statement equivalently as $\forall \alpha\in\omega^2 \,\,[\,Q(\alpha)\,]$. Here the predicate $Q$ is written based upon $P$ such that we always have $P(i,j)$ as equivalent to $Q(\omega \cdot j +i)$. Also note the domain and co-domain of the predicates $P$ and $Q$. We have $P:\mathbb{N}^2 \rightarrow \{0,1\}$ and $Q:\omega^2 \rightarrow \{0,1\}$.

So, in some cases, when we have to show $\forall i \in\mathbb{N} \, \forall j \in\mathbb{N} \,\,[\,P(i,j)\,] $ transfinite induction up to $\omega^2$ can occur. I think this can probably(?) occur in the argument for ackermann function eventually dominating every primitive recursive function (but perhaps depends on the specific argument), but I don't remember the specifics much.