Well-Founded Induction

From ProofWiki
Jump to navigation Jump to search


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}$


$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$.


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


$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$.


\(\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$


$A = B$


Also see

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