Transfinite Induction/Principle 1

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\operatorname{On}$ denote the class of all ordinals.

Let $A$ denote a class.


Suppose that:

For all elements $x$ of $\operatorname{On}$, if $x$ is a subset of $A$, then $x$ is an element of $A$.


Then $\operatorname{On} \subseteq A$.


Proof

NotZFC.jpg

This page is beyond the scope of ZFC, and should not be used in anything other than the theory in which it resides.

If you see any proofs that link to this page, please insert this template at the top.

If you believe that the contents of this page can be reworked to allow ZFC, then you can discuss it at the talk page.


Aiming for a contradiction, suppose that $\neg \operatorname{On} \subseteq A$.

Then:

$\left({\operatorname{On} \setminus A}\right) \ne \varnothing$

From Set Difference is Subset, $\operatorname{On} \setminus A$ is a subclass of the ordinals.

By Epsilon Relation is Strongly Well-Founded on Ordinal Class, $\operatorname{On} \setminus A$ must have a $\in$-minimal element $y$.

By Element of Ordinal is Ordinal, $y$ must be a subset of $\operatorname{On}$, the class of all ordinals.

However, from the fact that $y$ is a $\in$-minimal element of $\operatorname{On} \setminus A$:

$\left({\operatorname{On} \setminus A}\right) \cap y = \varnothing$.

So by its subsethood of $\operatorname{On}$:

$\left({\operatorname{On} \cap y}\right) \setminus A = \left({y \setminus A}\right) = \varnothing$

Therefore $y \subseteq A$.

However, by the hypothesis, $y$ must also be an element of $A$.

This contradicts the fact that $y$ is an element of $\operatorname{On} \setminus A$.


Therefore $\operatorname{On} \subseteq A$.

$\blacksquare$

Law of the Excluded Middle

This proof depends on the Law of the Excluded Middle, by way of Reductio ad Absurdum.

This is one of the axioms of logic that was determined by Aristotle, and forms part of the backbone of classical (Aristotelian) logic.

However, the intuitionist school rejects the Law of the Excluded Middle as a valid logical axiom. This in turn invalidates this proof from an intuitionistic perspective.


Sources