Well-Ordered Induction

This article is not under active maintenance. 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 with caution. To discuss this page in more detail, feel free to use the talk page.

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$