Transfinite Induction/Schema 1

From ProofWiki
Jump to navigation Jump to search

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