Transfinite induction, proving $\operatorname{P}(0)$ although $\alpha = 0$ is out from hypothesis.

41 Views Asked by At

In a transfinite induction, if I have to prove that a predicate $\operatorname{P}(\alpha)$ is true $\forall \alpha \gt 0$, can I proceed showing $\operatorname{P}(0), \; \operatorname{P}(\alpha) \rightarrow \operatorname{P}(\alpha + 1), \; \operatorname{P}(\alpha) \; \forall \alpha \lt \lambda \rightarrow \operatorname{P}(\lambda) \;\; \lambda$ limit ordinal? $\operatorname{P}(0)$ is true because $\alpha = 0$ is out from hypothesis, but, I'm wondering, is it enough to conclude that $\operatorname{P}(1)$ is true?

I thought about it proving this criterion: $\forall \alpha \gt 0 \; ( \omega^{\beta_k} \cdot n_k + \ldots + \omega^{\beta_1} \cdot n_1 + n_0 ) \cdot \omega^{\alpha} = \omega^{\beta_k + \alpha}, \; k, n_i \in \omega\! \smallsetminus\!\{0\} \; \forall i$.

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, there are two ways around this:

  1. Define $Q(\alpha)=\alpha=0\lor P(\alpha)$, and prove that $\forall\alpha\,P(\alpha)$. That is, forcefully add $0$ to your predicate.
  2. Define $Q(\alpha)=\alpha<\omega\to P(\alpha+1)\lor P(\alpha)$. That is, shift the natural numbers by $1$, and then go back to $P$.

In either case, the practice is that you can simply start your induction by with $1$. But now you will have to verify it by hand, like you would normally do for a basis case.