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

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

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

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

נוסח המשפט

משפט הסדר הטוב. על כל קבוצה $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)-\{\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 ניתן לסדר בסדר טוב לפי $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$ כנדרש באקסיומת הבחירה.

שימושים

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

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

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

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

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

ראו גם

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