Well-Founded Induction
Theorem
Let $\struct {A, \RR}$ be a strictly well-founded relation.
Let $\RR^{-1} \sqbrk x$ 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: \paren {\RR^{-1} \sqbrk x \subseteq B \implies x \in B}$
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 \nsubseteq B$.
Then:
- $A \setminus B \ne 0$
By Strictly Well-Founded Relation determines Strictly Minimal Elements, $A \setminus B$ must have some strictly minimal element under $\RR$.
Let $\map \complement B$ be the set complement of $B$.
Then:
\(\ds \exists x \in A \setminus B: \, \) | \(\ds \paren {A \setminus B} \cap \RR^{-1} \sqbrk x\) | \(=\) | \(\ds \O\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \paren {A \cap \map \complement B} \cap \RR^{-1} \sqbrk x\) | \(=\) | \(\ds \O\) | Definition of Set Complement | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds A \cap \paren {\map \complement B \cap \RR^{-1} \sqbrk x }\) | \(=\) | \(\ds \O\) | Intersection is Associative | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds A \cap \paren {\RR^{-1} \sqbrk x \cap \map \complement B }\) | \(=\) | \(\ds \O\) | Intersection is Commutative | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \paren {A \cap \RR^{-1} \sqbrk x } \cap \map \complement B\) | \(=\) | \(\ds \O\) | Intersection is Associative |
So, by Intersection with Complement is Empty iff Subset:
- $A \cap \RR^{-1} \sqbrk x \subseteq B$
Since $\RR^{-1} \sqbrk x \subseteq A$, by definition of a subset:
- $\RR^{-1} \sqbrk x \subseteq B$
Thus, by hypothesis $(1)$:
- $x \in B$
But this contradicts the fact that:
- $x \in A \setminus B$
By Proof by Contradiction it follows that:
- $A \setminus B = \O$
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$