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

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

הוכחה

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

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

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

על אותם סודרים ש-$g$ מוגדרת עליהם, $g$ פונקציה חד-חד-ערכית: אם ${\alpha }_1<{\alpha }_2$ אז $g({\alpha }_1)\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\iff g^{-1}(x)<g^{-1}(y)$. נראה כי זהו אכן סדר טוב:

1. א-רפלקסיביות: $g^{-1}(x)<g^{-1}(x)$, לכן $x<x$.
2. טרנזיטיביות: $x<y\wedge y<z\Rightarrow g^{-1}(x)<g^{-1}(y)\wedge 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)\vee g^{-1}(y)<g^{-1}(x)\Rightarrow x<y\vee y<x$.
4. תהי $\mathrm{\varnothing }\ne S\subseteq A$. אז מהחד-חד-ערכיות של $g^{-1}$ נקבל $\mathrm{\varnothing }\ne 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 \le g^{-1}(x)\Rightarrow s\le x$.