לדלג לתוכן

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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

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

הוכחה

[עריכה]

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

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

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

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

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

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

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