הוכחות מתמטיות/תורת הקבוצות/משפט האינדקוציה הטרנספיניטית

תהי $(X,\le )$ קבוצה סדורה היטב, ותהי $A\subset X$ כך שמתקיים $\mathrm{\forall }x\in X:O(x)\subseteq A\Rightarrow x\in A$, אזי $A=X$.

משמעות המשפט היא, שאם תכונה מסויימת מתקיימת לחלק מהאיברים, אבל קיום התכונה לכל האיברים הקטנים מאיבר מסויים גורר את קיום התכונה עבור אותו האיבר, אזי התכונה נכונה לכל האיברים.

הוכחה

נניח בשלילה $A\ne X$, אזי $X\setminus A\ne \mathrm{\varnothing }$.
מכיוון ש-$X$ סדורה היטב, קיים $x_0=\min (X\setminus A)$.
לפי בנייתו, לכל $x<x_0$ מתקיים $x\in A$, כלומר $O(x_0)\subseteq A$, ולכן לפי הנתון $x_0\in A$, בסתירה.