Is it valid to conclude that P holds for every ordinal if P(0) holds and P(β) implies P(β+1) for every β? Give a counterexample if not.

No: P(α): α<ω satisfies both conditions but fails at ω

Yes, because every ordinal is 0 or a successor

No, because 0 is not an ordinal

Exercise · ZW-TRANSFINITE-INDUCTION-009 · ★★★ Advanced

Is it valid to conclude that \(P\) holds for every ordinal if \(P(0)\) holds and \(P(\beta)\) implies \(P(\beta+1)\) for every \(\beta\)? Give a counterexample if not.

Choose one option.

Show answer

A. No: \(P(\alpha): \alpha<\omega\) satisfies both conditions but fails at \(\omega\)

Explanation

With \(P(\alpha):\alpha<\omega\), both \(P(0)\) and the successor step hold, but \(\omega<\omega\) is false, so the limit case is also needed.

Study Set theory in ZWMath →

Review the concept: Transfinite induction

Principle that proves a property holds for all ordinal numbers \(\mathrm{On}\) by showing that if it holds for all ordinals below a given \(\alpha\), it also holds for \(\alpha\).

\[\forall\alpha[\forall\beta<\alpha P(\beta)\to P(\alpha)]\to\forall\alpha P(\alpha)\]

Is it valid to conclude that \(P\) holds for every ordinal if \(P(0)\) holds and \(P(\beta)\) implies \(P(\beta+1)\) for every \(\beta\)? Give a counterexample if not.

Explanation

Review the concept: Transfinite induction

More practice problems: transfinite induction