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

משפט: תהי $A$ קבוצה. אז קיים יחס סדר טוב על $A$.

הוכחה

תהא $A$ קבוצה. נסמן ב-$C={\mathcal {P}}(A)-\{\emptyset \}$ את קבוצת החזקה של A, ללא הקבוצה הריקה. לפי אקסיומת הבחירה, קיימת פונקציה $f:C\to A$ המתאימה לכל $B\in C$ איבר $b\in B$. נגדיר באינדוקציה טרנספיניטית פונקציה הפועלת על מספרים סודרים:

$g(\alpha )=f\left(A-\bigcup _{\beta <\alpha }\{g(\beta )\}\right)$

נשים לב כי ייתכן ש-$g(\alpha )$ אינה מוגדרת בשני מקרים: מקרה ראשון, אם $A=\cup _{\beta <\alpha }\{g(\beta )\}$, אז $g(\alpha )=f(\emptyset )$ שאינו מוגדר. ומקרה שני אם קיים $\beta <\alpha$ כך ש-$g(\beta )$ אינו מוגדר.

על אותם סודרים ש-$g$ מוגדרת עליהם, $g$ פונקציה חד-חד-ערכית: אם $\alpha _{1}<\alpha _{2}$ אז $g(\alpha _{1})\not \in A-\cup _{\beta <\alpha _{2}}\{g(\beta )\}$ ולכן פונקציית הבחירה $f$ לא יכולה לבחור את $g(\alpha _{1})$ כערך ל-$g(\alpha _{2})$.

לא ייתכן ש-$g$ מוגדרת לכל סודר, כי אז $g^{-1}$ (הקיימת לפי החד-חד-ערכיות) היא פונקציה מהקבוצה $A$ למחלקת כל הסודרים, לכן (לפי אקסיומת ההחלפה) מחלקת כל הסודרים היא קבוצה, בסתירה לפרדוקס בורלי-פורטי. מכאן שיש סודרים ש-$g$ אינה מוגדרת לגביהם. הסודרים סדורים היטב ולכן יש סודר מינימלי $\gamma$ כך ש-$g(\gamma )$ אינו מוגדר. מכיוון שלא קיים סודר קטן מ-$\gamma$ שהפונקציה אינה מוגדרת עליו, בהכרח הסיבה ש-$g(\gamma )$ אינו מוגדר היא ש-$A=\cup _{\beta <\gamma }\{g(\beta )\}$.

לכן $g:\gamma \to A$ התאמה חד-חד-ערכית ועל בין $\gamma$ ל-$A$.

נגדיר סדר טוב על $A$ בדרך הבאה: $x<y\Leftrightarrow g^{-1}(x)<g^{-1}(y)$. נראה כי זהו אכן סדר טוב:

1. א-רפלקסיביות: $g^{-1}(x)\not <g^{-1}(x)$, לכן $x\not <x$.
2. טרנזיטיביות: $x<y\land y<z\Rightarrow g^{-1}(x)<g^{-1}(y)\land g^{-1}(y)<g^{-1}(z)\Rightarrow g^{-1}(x)<g^{-1}(z)\Rightarrow x<z$.
3. השוואה: יהו $x,y\in A$. אז $g^{-1}(x)<g^{-1}(y)\lor g^{-1}(y)<g^{-1}(x)\Rightarrow x<y\lor y<x$.
4. תהי $\emptyset \neq S\subseteq A$. אז מהחד-חד-ערכיות של $g^{-1}$ נקבל $\emptyset \neq g^{-1}(S)\subseteq \gamma$. לכן יש איבר ראשון $\zeta$ ב$g^{-1}(S)$. נסמן $s=g(\zeta )$. אז לכל $x\in S$ מתקיים $g^{-1}(x)\in g^{-1}(S)\Rightarrow g^{-1}(s)=\zeta \leq g^{-1}(x)\Rightarrow s\leq x$.