# Well-Ordered Induction

While the contents of this page could be useful, they are currently not being maintained. The correctness, lay-out and usefulness of the article may be compromised, so use whatever you get from here |

## Theorem

Let $\struct {A, \prec}$ be a strict well-ordering.

For all $x \in A$, let the $\prec$-initial segment of $x$ be a small class.

Let $B$ be a class such that $B \subseteq A$.

Let:

- $(1): \quad \forall x \in A: \paren {\paren {A \mathop \cap \map {\prec^{-1} } x} \subseteq B \implies x \in B}$

Then:

- $A = B$

That is, if a property passes from the initial segment of $x$ to $x$, then this property is true for all $x \in A$.

## Proof

Aiming for a contradiction, suppose that $A \nsubseteq B$.

Then:

- $A \setminus B \ne 0$.

By Proper Well-Ordering Determines Smallest Elements, $A \setminus B$ must have some $\prec$-minimal element.

Thus:

- $\ds \exists x \in \paren {A \setminus B}: \paren {A \setminus B} \cap \map {\prec^{-1} } x = \O$

implies that:

- $A \cap \map {\prec^{-1} } x \subseteq B$

Hence this fulfils the hypothesis for $(1)$.

We have that $x \in A$.

so by $(1)$:

- $x \in B$

But this contradicts the fact that $x \in \paren {A \setminus B}$.

Thus by Proof by Contradiction:

- $A \subseteq B$

It follows by definition of set equality that:

- $A = B$

$\blacksquare$

## Also see

- Well-Founded Induction shows that it is possible to weaken the hypotheses in order to drop the requirements that $\prec$ be well-ordering, replacing it with the requirement that $\prec$ be simply strictly well-founded (hence, the name well-founded induction) and to drop the requirement that the initial segments be sets (they may also be proper classes).

- It is important to note that such an approach involves the use of the axiom of foundation.

## Sources

- 1971: Gaisi Takeuti and Wilson M. Zaring:
*Introduction to Axiomatic Set Theory*: $\S 6.27$