משפט הסדר הטוב

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

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

נוסח המשפט

על כל קבוצה $A$ קיים יחס סדר מלא $\leq$ , כך שבכל תת-קבוצה לא-ריקה $B\subseteq A$ קיים איבר $b\in B$ , כך שלכל $a\in B$ מתקיים $b\leq a$ . במילים אחרות, לכל תת-קבוצה של $A$ יש איבר מינימלי. יחס סדר $\leq$ המקיים את התנאי הנ"ל נקרא סדר טוב.

יש לשים לב כי הסדר $\leq$ אינו בהכרח הסדר הטבעי המוגדר על הקבוצה $A$ . למשל הסדר הרגיל של חוג המספרים השלמים אינו סדר טוב (למשל אין מספר שלם מינימלי). עם זאת, אם נגדיר סדרה $0,-1,1,-2,2,\ldots$ , אז הסדר $\leq$ המוגדר כך ש-$a\leq b$ אם $a$ בא לפני $b$ בסדרה, הוא סדר טוב על קבוצת המספרים השלמים.

היסטוריה

אבי תורת הקבוצות, גאורג קנטור, קבע ב-1883 שמשפט הסדר הטוב נכון כ-“fundamental law of thought”. מכיוון שלתורת הקבוצות של קנטור לא היה בסיס אקסיומתי מוצק, הוכחה או הפרכה פורמלית של המשפט לא הייתה בגדר האפשר. מתמטיקאים רבים חלקו על קנטור, שכן התקשו לקבל קיום של סדר טוב על קבוצות מסובכות, כגון הישר הממשי.

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

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

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

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

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

הוכחה

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

תהא $A$ קבוצה. נסמן ב-$C={\mathcal {P}}(A)-\{\varnothing \}$ את קבוצת החזקה של 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(\varnothing )$ שאינו מוגדר. ומקרה שני אם קיים $\beta <\alpha$ עבורו $g(\beta )$ אינו מוגדר.

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

שקילות לאקסיומת הבחירה

במסגרת אקסיומות ZF משפט הסדר הטוב שקול לאקסיומת הבחירה. כלומר מספיק להניח רק אחד מהם כדי להוכיח את השני. ההוכחה של אקסיומת הבחירה תחת הנחת משפט הסדר הטוב פשוטה:

תהי $E$ משפחה של קבוצות. נסמן ב-$\cup E$ את איחוד כל הקבוצות ב-$E$ . לפי משפט הסדר הטוב קיים סדר טוב $\leq$ על $\cup E$ . כעת נגדיר את $f$ להיות הפונקציה המתאימה לכל קבוצה ב-$E$ את האיבר המינימלי שלה לפי $\leq$ כתת-קבוצה של $\cup E$ . זוהי פונקציית בחירה על $E$ כנדרש באקסיומת הבחירה.

שימושים

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

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

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

מסדרים את המספרים הממשיים בסדר טוב. מספר ממשי מסוים נמצא בבסיס המל אם ורק אם הוא אינו צירוף לינארי (סופי) של המספרים הקטנים ממנו.

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

ראו גם

• אקסיומת הבחירה
• הלמה של צורן