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

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

הוכחה עריכה

תהא   קבוצה. נסמן ב-  את קבוצת החזקה של A, ללא הקבוצה הריקה. לפי אקסיומת הבחירה, קיימת פונקציה   המתאימה לכל   איבר  . נגדיר באינדוקציה טרנספיניטית פונקציה הפועלת על מספרים סודרים:

 

נשים לב כי ייתכן ש-  אינה מוגדרת בשני מקרים: מקרה ראשון, אם  , אז   שאינו מוגדר. ומקרה שני אם קיים   כך ש-  אינו מוגדר.

על אותם סודרים ש-  מוגדרת עליהם,   פונקציה חד-חד-ערכית: אם   אז   ולכן פונקציית הבחירה   לא יכולה לבחור את   כערך ל- .

לא ייתכן ש-  מוגדרת לכל סודר, כי אז   (הקיימת לפי החד-חד-ערכיות) היא פונקציה מהקבוצה   למחלקת כל הסודרים, לכן (לפי אקסיומת ההחלפה) מחלקת כל הסודרים היא קבוצה, בסתירה לפרדוקס בורלי-פורטי. מכאן שיש סודרים ש-  אינה מוגדרת לגביהם. הסודרים סדורים היטב ולכן יש סודר מינימלי   כך ש-  אינו מוגדר. מכיוון שלא קיים סודר קטן מ-  שהפונקציה אינה מוגדרת עליו, בהכרח הסיבה ש-  אינו מוגדר היא ש- .

לכן   התאמה חד-חד-ערכית ועל בין   ל- .

נגדיר סדר טוב על   בדרך הבאה:  . נראה כי זהו אכן סדר טוב:

  1. א-רפלקסיביות:  , לכן  .
  2. טרנזיטיביות:  .
  3. השוואה: יהו  . אז  .
  4. תהי  . אז מהחד-חד-ערכיות של   נקבל  . לכן יש איבר ראשון   ב . נסמן  . אז לכל   מתקיים  .