Transfinite Induction/Schema 1/Proof 2

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

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$


Axiom of Dependent Choice

This theorem depends on the Axiom of Dependent Choice.

Although not as strong as the Axiom of Choice, the Axiom of Dependent Choice is similarly independent of the Zermelo-Fraenkel axioms.

The consensus in conventional mathematics is that it is true and that it should be accepted.