Generalization of simple and transfinite induction

108 Views Asked by At

Definition

For a set of ordinals $\boldsymbol\alpha$ and ordinals $\gamma$, $\beta$, let

$$\boldsymbol\alpha \xrightarrow[\gamma]{}\beta$$

symbolize the proposition that

  • $(\boldsymbol\alpha,<)$ has order-type $\gamma$ for the natural ordering $<$
    [alternatively: $\boldsymbol\alpha$ is a strictly increasing $\gamma$-indexed set of ordinals]
  • $\beta \not\in \boldsymbol\alpha$
  • $\beta$ is the supremum of $\boldsymbol\alpha$

(read: "$\boldsymbol\alpha$ is a $\gamma\rightarrow\beta$-sequence").

For all $\gamma\rightarrow\beta$-sequences $\boldsymbol\alpha$ it holds that

  • $\gamma \leq \beta$
  • $\gamma$ and $\beta$ are both limit or both successor ordinals

Examples

  1. $\boldsymbol\alpha \xrightarrow[1]{}\beta$ means $\boldsymbol\alpha = \lbrace \alpha \rbrace$ and $\beta = \alpha + 1$

  2. $\boldsymbol\alpha \xrightarrow[\omega]{}\beta$ means $\boldsymbol\alpha$ is a countable fundamental sequence with limit $\beta$

  3. $\boldsymbol\alpha \xrightarrow[\beta]{}\beta$ means $\boldsymbol\alpha=\beta = \lbrace \alpha : \alpha < \beta \rbrace$

  4. $\boldsymbol\alpha=\beta$ implies $\boldsymbol\alpha \xrightarrow[\beta]{}\beta$


Definition

With each ordinal number $\gamma$ a second-order property $\Pi_\gamma$ of properties $P$ of ordinal numbers is associated:

$$(\forall \beta)\ (\forall \boldsymbol\alpha \xrightarrow[\gamma]{}\beta)\ \Big( \big( (\forall \alpha \in \boldsymbol\alpha)\ P(\alpha)\big) \Rightarrow P(\beta)\Big)$$

This meta-property reads:

When for an arbitrary $\beta$ all members of an arbitrary $\gamma\rightarrow\beta$-sequence $\boldsymbol\alpha$ have property $P$, then also $\beta$ has (= inherits) property $P$.

Compare with the parameter-free second-order property $\Pi$:

$$(\forall \beta)\ (\forall \boldsymbol\alpha \xrightarrow[\beta]{}\beta)\ \Big( \big( (\forall \alpha \in \boldsymbol\alpha)\ P(\alpha)\big) \Rightarrow P(\beta)\Big)$$

which is a blown-up way to say $(\forall \beta) \big( (\forall \alpha < \beta)\ P(\alpha)\big) \Rightarrow P(\beta)$.


Examples of usage

[Simple induction]
If $P(0)$ and $P$ has property $\Pi_1$ then $P(\alpha)$ for all finite ordinals $\alpha$.

[Transfinite induction]
If $P(0)$ and $P$ has property $\Pi$ then $P(\alpha)$ for all ordinals $\alpha$.


Question

How do generalizations with respect to properties $\Pi_\gamma$ look like?

What would especially be the condition $\Phi_\omega$ in:

If $P(0)$ and $P$ has property $\Pi_\omega$ then $P(\alpha)$ for all ordinals $\alpha$ obeying condition $\Phi_\omega$.