# Transfinite Induction/Schema 1

## Theorem

Let $P \left({x}\right)$ be a property

Suppose that:

- If $P \left({x}\right)$ holds for all ordinals $x$ less than $y$, then $P \left({y}\right)$ also holds.

Then $P \left({x}\right)$ holds for all ordinals $x$.

## Proof 1

It should be noted that for any two ordinals, $x \lt y \iff x \in y$.

Let $P \left({x}\right)$ be a property that satisfies the above conditions.

Aiming for contradiction, let $y$ be an ordinal such that $\neg P \left({y}\right)$.

By the Rule of Transposition, it follows that if $y$ is an ordinal such that $\neg P \left({y}\right)$, then there exists an ordinal $x \lt y \iff x \in y$ such that $\neg P \left({x}\right)$.

Let $\alpha$ be the smallest ordinal in $y$ such that $\neg P \left({\alpha}\right)$.

We can choose such an element because an ordinal is strictly well-ordered by definition.

Since $\neg P \left({\alpha}\right)$, let $\beta$ be the smallest ordinal in $\alpha$ such that $\neg P \left({\beta}\right)$.

Since $y$ is transitive by definition:

- $\beta \in \alpha \land \alpha \in y \implies \beta \in y$

And so $\beta$ is an ordinal in $y$ such that $\neg P \left({\beta}\right)$.

But since $\beta \lt \alpha$, this contradicts the fact that $\alpha$ is the smallest ordinal of $y$ such that $\neg P \left({\alpha}\right)$.

Therefore $P \left({x}\right)$ holds for all ordinals.

Hence the result.

$\blacksquare$

## Proof 2

It should be noted that for any two ordinals, $x \lt y \iff x \in y$.

Let $P \left({x}\right)$ be a property that satisfies the above conditions.

Aiming for contradiction, let $y$ be an ordinal such that $\neg P \left({y}\right)$.

Let $S$ be the set defined as:

- $S = \left\{{x \in y^+: \neg P \left({x}\right)}\right\}$

It is seen that this set is non-empty because by Set is Element of Successor:

- $y \in y^+$

$y^+$ is an ordinal because of Successor Set of Ordinal is Ordinal.

By Element of Ordinal is Ordinal, $S$ is a set of ordinals.

By the Rule of Transposition, it follows that for every $x \in S$, there exists an ordinal $\alpha \lt x \iff \alpha \in x$ such that $\neg P \left({\alpha}\right)$.

But by transitivity:

- $\alpha \in x \land x \in y^+ \implies \alpha \in y^+$

So the epsilon restriction $\in_S$ is a right-total relation on $S$.

Therefore by the Axiom of Dependent Choice there exists a sequence $\left\langle{x_n}\right\rangle_{n \in \N}$ in $S$ such that:

- $\forall n \in \N: x_{n+1} \in x_n$

But this contradicts No Infinitely Descending Membership Chains.

And thus $P \left({x}\right)$ holds for all ordinals.

Hence the result.

$\blacksquare$

## Sources

- 2011: Kenneth Kunen:
*Set Theory*: $\S 1.9$