Well-Founded Induction

Theorem

Let $\left({A, \prec}\right)$ be a foundational relation.

Let $\prec^{-1} \left({x}\right)$ denote the preimage of $x$ for each $x \in A$.

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

Suppose that:

$(1): \quad \forall x \in A: \left({ \prec^{-1} \left({ x }\right) \subseteq B \implies x \in B }\right)$

Then:

$A = B$

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

Proof

Aiming for a contradiction, suppose $A \not \subseteq B$.

Then $A \setminus B \not = 0$.

By Well-Founded Relation Determines Minimal Elements, $A \setminus B$ must have some $\prec$-minimal element.

Then:

$\displaystyle \exists x \in \left({ A \setminus B }\right): \left({ A \setminus B }\right) \cap \prec^{-1} \left({ x }\right) = \varnothing$

so:

$A \cap \prec^{-1} \left({ x }\right) \subseteq B$

Since $\prec^{-1} \left({ x }\right) \subseteq A$:

$\prec^{-1} \left({ x }\right) \subseteq B$

Thus, by hypothesis $(1)$:

$x \in B$

But this contradicts the fact that:

$x \in \left({A \setminus B}\right)$

By Proof by Contradiction it follows that:

$\left({A \setminus B}\right) = \varnothing$

and so:

$A \subseteq B$

Therefore:

$A = B$

$\blacksquare$

Also see

Well-Ordered Induction, a weaker theorem that does not require the Axiom of Foundation.

Sources

• 1971: Gaisi Takeuti and Wilson M. Zaring: Introduction to Axiomatic Set Theory: $\S 9.22$