אקסיומת הבחירה, עקרון הסדר הטוב, הלמה של צורן - מי יודע?

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

הרקע שלנו הוא תורת הקבוצות; לא צריך לדעת הרבה יותר מאשר מהי קבוצה, מהי פונקציה ומהו סדר על אברים, אבל אני אניח שהקורא יודע ולא מפחד ממתמטיקה. נתחיל עם אקסיומת הבחירה שדורשת הכי מעט ידע מוקדם - היא אומרת, בפשטות, שאם יש לנו אוסף של קבוצות לא ריקות, אפשר לבחור איבר מכל אחת מהקבוצות הללו. פורמלית, אם \( \mathcal{F} \) היא משפחה של קבוצות לא ריקות, אז קיימת פונקציה \( f:\mathcal{F}\to\bigcup\mathcal{F} \) כך ש-\( f\left(A\right)\in A \) לכל \( A\in\mathcal{F} \). במילים אחרות, הפונקציה מקבלת קבוצה מתוך \( \mathcal{F} \) ומחזירה איבר כלשהו מתוך אותה קבוצה. לא נשמע ביג דיל במיוחד, נכון? ובכן, לכן “אקסיומת הבחירה בבירור נכונה”.

הבעיה היא שלא תמיד ברור איך לבנות פונקציה כזו. נניח לרגע ש-\( \mathcal{F}=2^{\mathbb{N}} \), שזה סימון נחמד לתיאור אוסף כל תת-הקבוצות של הטבעיים (אופס! הוא כולל גם את הקבוצה הריקה. אז בואו נעיף אותה מ-\( \mathcal{F} \)). האם אנחנו יודעים לבנות פונקציה כזו? ובכן, כן: \( f\left(A\right)=\min A \), האיבר המינימלי ב-\( A \). יש כזה, כי בכל קבוצה של טבעיים יש איבר מינימלי.

אוקיי, ומה אם \( \mathcal{F}=2^{\mathbb{Z}} \)? כבר לא נכון לומר שבכל קבוצה של שלמים יש איבר מינימלי, אבל זה קושי שקל מאוד לעקוף - נבחר איבר שהוא מינימלי בערך המוחלט שלו, ואם יש שני מספרים ששווים בערך המוחלט שלהם, אז נבחר את השלילי מביניהם. או את החיובי. מה שתרצו.

אוקיי, ומה אם \( \mathcal{F}=2^{\mathbb{Q}} \)? כאן זה קצת יותר טריקי, אבל אפשר עדיין להתחכם: מספר רציונלי הוא מהצורה \( \frac{a}{b} \) כאשר \( b\ge1 \), אז בהינתן \( A \) נסתכל על כל המספרים ב-\( A \) שעבורם \( b \) מינימלי, ואז מביניהם נסתכל על זה שעבורו \( a \) מינימלי בערכו המוחלט.

אוקיי, ומה אם \( \mathcal{F}=2^{\mathbb{R}} \)? אה…

אה…

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

מה שצריך להבין כשמדובר על אקסיומת הבחירה הוא שכשאנחנו באים לעשות מתמטיקה בצורה פורמלית, לא כל מה שאנחנו אומרים בהכרח מתקיים. צריך להוכיח, ולהוכיח בזהירות. וכשמוכיחים, צריך להוכיח מתוך משהו. ובתורת הקבוצות המשהו הזה הוא מאוד קונקרטי - לרוב מדובר על מערכת האקסיומות של צרמלו-פרנקל, ZF, שלא אציג במפורש עכשיו אבל מגדירה מאוד בזהירות באילו דרכים אפשר לבנות קבוצות. וכלל לא ברור שאם מצייתים ל”חוקים” של ZF אז אפשר יהיה לבנות פונקצית בחירה עבור כל אוסף \( \mathcal{F} \); למעשה, בואו נשים את הקלפים על השולחן - אי אפשר. יש הוכחה לכך שאקסיומות הבחירה היא בלתי תלויה באקסיומות של ZF, כלומר אפשר להוסיף אותה ל-ZF ולקבל מערכת אקסיומות עקבית (ולכן כזו שמתארת “עולם” מתמטי לגיטימי כלשהו) שנקראת ZFC, אבל אפשר גם להוסיף את שלילתה ל-ZF ועדיין לקבל מערכת אקסיומות עקבית. בדרך כלל מוסיפים את אקסיומת הבחירה; בטקסטים מתמטיים שלא מתעסקים ישירות בתורת הקבוצות פה ושם אפשר לראות את משפט המחץ “כאן השתמשנו באקסיומת הבחירה”. אפשר לקיים דיון פילוסופי ארוך ומייגע בשאלה אם “נכון” להוסיף את אקסיומת הבחירה למתמטיקה או לא; אני לא מעוניין בו כרגע אלא בתוצאה המתמטית המגניבה שאקסיומת הבחירה שקולה ללמה של צורן ולעקרון הסדר הטוב.

בשביל שני אלו צריך לדבר על סדר. סדר חלקי על קבוצה \( A \) הוא יחס (אוסף של זוגות של איברים מ-\( A \)) שאני בדרך כלל מסמן בתור \( a<b \) וקורא בתור “\( a \) קטן מ-\( b \)”. מה שחשוב הוא שאף איבר לא קטן יותר מעצמו (לא מתקיים \( a<a \) לאף \( a\in A \)), ושהוא טרנזיטיבי, כלומר אם \( a<b \) וגם \( b<c \) אז \( a<c \) (שימו לב שנובע משני אלו מייד שהיחס לא סימטרי, כלומר לא ייתכן שגם \( a<b \) וגם \( b<a \)). יחס הסדר הרגיל על מספרים הוא כמובן סדר שכזה, אבל גם היחס “\( a \) מחלק את \( b \)” (שמסומן בד”כ בתור \( a|b \)) הוא יחס סדר, וכזה שבו יש איברים שבכלל אי אפשר להשוות (לכו תשוו את 3 ו-5). גם היחס “\( A\subseteq B \)” על קבוצות הוא יחס סדר (וחלקי, כי לכו תשוו את \( \left\{ 1\right\} ,\left\{ 2\right\} \)).

נניח שיש לנו קבוצה גדולה \( X \) שעליה מוגדר יחס סדר, ויש לנו תת-קבוצה שלה, \( A\subseteq X \). מן הסתם יחס הסדר על \( X \) תקף גם עבור \( A \) (למה? תוכיחו, זה קל). אם יש ב-\( X \) איבר שגדול לפחות כמו כל אברי \( A \) (כלומר, \( a\le x \) לכל \( a\in A \) עבור \( x\in X \) מסויים - כאשר \( a\le x \) פירושו \( a<x \) או \( a=x \)) אז קוראים לאיבר שכזה “חסם מלעיל” של \( A \). למשל, אם נסתכל על \( \left(0,1\right) \) - כל המספרים הממשיים בין 0 ל-1 - אז 1 הוא חסם מלעיל שכזה. וגם 2. וגם \( \pi \).

עוד שתי הגדרות קטנות. ראשית, אם \( a\in X \) הוא איבר כזה כך שלא קיים \( b\in X \) עבורו \( a<b \) אומרים ש-\( a \) מקסימלי (שימו לב שזה לא אומר ש-\( b\le a \) עבור כל \( b\in X \); ייתכן שיש גם איברים שאינם ניתנים להשוואה עם \( a \)). שנית, אם \( A \) היא תת-קבוצה של \( X \) שבה כל שני איברים ניתנים להשוואה (אומרים במקרה כזה שהסדר על \( A \) הוא מלא או לינארי) אז קוראים ל-\( A \) “שרשרת” (כי אפשר לחשוב על האיברים של \( A \) בתור חוליות בשרשרת… עזבו, לא חשוב). עכשיו סוף סוף אפשר לנסח פורמלית את הלמה של צורן: אם \( X \) היא קבוצה שמוגדר עליה יחס סדר בעל התכונה שלכל שרשרת יש חסם מלעיל, אז יש ב-\( X \) איבר מקסימלי.

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

נעבור לעקרון הסדר הטוב (לפעמים קוראים לו “משפט הסדר הטוב” ומשתמשים ב”עקרון הסדר הטוב” כדי להתכוון למשהו אחר לגמרי, כי זה מה שמתמטיקאים אוהבים לעשות - לבלבל). מה זה יחס סדר כבר הסברתי. אפילו יחס סדר מלא כבר הזכרתי. סדר טוב הוא הבן המוצלח של סדר מלא: הוא סדר מלא על \( X \) כך שבכל תת-קבוצה \( A\subseteq X \) יש איבר מינימלי ביחס לסדר הזה, כשמינימלי, כצפוי, הוא איבר \( a\in A \) כך שלכל \( b\in A \) מתקיים \( a\le b \) (ליתר דיוק, כך שלא קיים \( b\in A \) עבורו \( b<a \), אבל מכיוון שהסדר מלא זה שקול). האב-טיפוס של קבוצה עם סדר טוב הוא המספרים הטבעיים; ובמובן מסויים, כל קבוצה שסדורה בסדר טוב ניתנת לתיאור על ידי סודר כלשהו (פורמלית - איזומורפית לסודר כלשהו, כשאיזומורפיזם פה צריך לשמר את יחס הסדר). זה מעלה את השאלה המעניינת האם כל קבוצה אפשר לסדר בסדר טוב שכזה (בבירור יחסי הסדר ה”רגילים” על \( \mathbb{Z},\mathbb{Q},\mathbb{R} \) אינם כאלו, ועל \( \mathbb{C} \) בכלל אין יחס סדר “טבעי”, ואלו עוד קבוצות פשוטות יחסית). עקרון הסדר הטוב אומר שכן, על כל קבוצה אפשר להגדיר סדר טוב. וזה מוזר. זה ממש מוזר. אין לי מילים לומר כמה זה מוזר. בעוד שעל \( \mathbb{Z} \) ו-\( \mathbb{Q} \) אני עוד יכול לנחש איך להגדיר סדר טוב (ועשיתי את זה קודם כבר בפוסט הזה, אם תשימו לב - וכמובן שלא במקרה), על \( \mathbb{R} \) כבר אין לי מושג איך סדר טוב ייראה. אז איך בכל זאת אפשר להגדיר אותו? ניחשתם נכון - עם אקסיומת הבחירה.

יפה, אז הצגנו את שלושת המשפטים הללו. כעת בואו נוכיח שכולם שקולים, כלומר מספיק להניח אחד מהם כדי להוכיח את שני האחרים. מה שנעשה יהיה להוכיח שאקסיומת הבחירה שקולה הן לעקרון הסדר הטוב והן ללמה של צורן; מכך כבר נובע היתר. ההוכחה לא תהיה פורמלית עד הסוף כי אני הולך להתבסס על משהו שאף פעם לא הגדרתי במפורש - רקורסיה על-סופית, שהיא פשוט דרך להגדיר סדרות של איברים על ידי כך שאני מגדיר איך כל איבר בסדרה מתקבל כפונקציה של כל קודמיו, אבל כאן “סדרה” מאונדקסת על ידי סודר כללי ולאו דווקא על ידי קבוצת המספרים הטבעיים וזהו (דוגמה לסדרה קצת יותר כללית: \( a_{0},a_{1},a_{2},a_{3},\dots,a_{\omega},a_{\omega+1},\dots,a_{\omega\cdot2},a_{\omega\cdot2+1} \) - זו סדרה שה”אורך” שלה הוא הסודר \( \omega\cdot2+2 \)). להוכחה פורמלית ממש כדאי ללכת לספרים (הספר של Jech, למשל).

נתחיל עם אקסיומת הבחירה ועקרון הסדר הטוב. אם עקרון הסדר הטוב נכון, אז אקסיומת הבחירה נובעת בקלות: בהינתן \( \mathcal{F} \), נסדר את \( \bigcup\mathcal{F} \) בסדר טוב ונגדיר \( f\left(A\right)=\min A \), בדיוק כמו שעשיתי בתחילת הפוסט. הכיוון השני הוא המעניין פה.

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

קצת יותר פורמלית, בכל זאת: נגדיר \( \mathcal{F}=2^{A} \) (כרגיל, בלי הקבוצה הריקה). אז מאקסיומת הבחירה, יש פונקצית בחירה \( f:\mathcal{F}\to A \). כעת, לכל סודר \( \alpha \) נגדיר \( a_{\alpha}=f\left(A\backslash\left\{ a_{\beta}|\beta<\alpha\right\} \right) \). זו כנראה ההגדרה המסובכת ביותר בפוסט, והיא פשוט אומרת “תפעיל את \( f \) על תת-הקבוצה של \( A \) שמתקבלת על ידי הסרה מ-\( A \) של כל האיברים בסדרה שאנחנו בונים שהאינדקס שלהם קטן מ-\( \alpha \)”.

הבניה הזו חייבת להיתקע מתישהו - כלומר, מתישהו נגיע לסודר \( \alpha \) כך ש-\( A=\left\{ a_{\beta}|\beta<\alpha\right\} \) ולכן אין יותר איברים לבחור - אבל זה טוב לנו, כי זה אומר שבניית הסדרה שלנו תסתיים מתישהו בהצלחה (למה הבניה חייבת להיתקע? כי אחרת היינו מקבלים שב-\( A \) יש איבר ייחודי לכל סודר - אבל “קבוצת כל הסודרים” גדולה מדי מכדי להיות קבוצה, וזה יסתור את זה ש-\( A \) היא קבוצה). זה משלים את ההוכחה, מודולו הפרטים הטכניים שטאטאתי באלגנטיות רבה מתחת לשטיח.

נעבור ללמה של צורן. כאן אין כיוון טריוויאלי, אז בואו נתחיל דווקא מלהוכיח את הלמה של צורן עם אקסיומת הבחירה. אז נתונה לנו קבוצה \( X \) שבה לכל שרשרת יש חסם מלעיל. אנחנו רוצים למצוא איבר מקסימלי ב-\( X \). מה עושים? פשוט מאוד! בונים בהדרגה (כלומר, ברקורסיה על-סופית) שרשרת; אם מתישהו נתקעים, אז בהכרח האיבר שבסוף השרשרת הוא מקסימלי; אם לא נתקעים, אז קיבלנו שרשרת “גדולה מדי” (כמקודם, זה אומר שיש איבר בשרשרת לכל סודר אפשרי, וזה בלתי אפשרי).

קצת יותר פורמלית, שוב פעם אנחנו מניחים קיום של פונקצית בחירה \( f:2^{X}\to X \) ובונים סדרה כך: \( a_{\alpha}=f\left(\left\{ x\in X\ |\ x>\left\{ a_{\beta}|\beta<\alpha\right\} \right\} \right) \). הסימון של “\( x \) גדול מקבוצה” הוא המצאה פרועה שלי ובסך הכל אומר ש-\( x \) הוא חסם מלעיל של הקבוצה ואינו שייך אליה. גם פה הבניה חייבת “להיתקע” מתישהו ולכן האיבר הגדול ביותר בסדרה יהיה איבר מקסימלי ב-\( X \) באופן כללי (כי אם הוא אינו מקסימלי, אז קיים איבר שגדול ממנו ולכן הוא חסם מלעיל של כל הסדרה).

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

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

במבט ראשון, לא ברור איך לגשת לסיפור הזה. יש לנו \( \mathcal{F} \) וצריך לבנות פונקצית בחירה עבורה, אבל איך נשתמש בלמה של צורן? צריך בשביל זה יחס סדר. איזה יחס סדר? האם כדאי להגדיר יחס סדר על \( \mathcal{F} \)? על הקבוצות ב-\( \mathcal{F} \)? מה עושים? ובכן, בלי פאניקה. החוכמה כאן היא לבחור את הקבוצה ה”נכונה” להשתמש בלמה של צורן עליה. בואו נגדיר קבוצה חדשה \( \mathcal{B} \) של כל הפונקציות שהן פונקציות בחירה חלקיות על \( \mathcal{F} \). כלומר, פונקציות שמקיימות \( f\left(A\right)\in A \) לכל \( A\in\mathcal{F} \) שעליו הן מוגדרות, אבל לא חייבות להיות מוגדרות על כל הקבוצות ב-\( \mathcal{F} \). על הקבוצה הזו מושרה יחס סדר טבעי למדי: \( f<g \) אם ורק אם \( g \) מוגדרת על כל מי ש-\( f \) מוגדר עליו ומחזירה אותו ערך (אבל אולי מוגדרת על ערכים רבים יותר). במתמטית אומרים ש-\( f \) הוא צמצום של \( g \); ועוד יותר פורמלית אפשר פשוט לכתוב \( f\subseteq g \) (כי פונקציות, בשורה התחתונה, הן קבוצות של זוגות שמקיימים תנאים מסויימים).

אם נראה שיש איבר מקסימלי ב-\( \mathcal{B} \), סיימנו; זו תהיה פונקצית הבחירה המבוקשת. זאת מכיוון שאם האיבר המקסימלי, שאסמן ב-\( f \), הוא לא פונקצית בחירה, אז יש \( B\in\mathcal{B} \) שעליו \( f \) לא מוגדרת, ומכיוון ש-\( B \) לא ריקה יש איזה \( b\in B \), אז אפשר להגדיר \( f^{\prime} \) שתהיה זהה ל-\( f \) על כל הקלטים שעליהם \( f \) מוגדרת, ובנוסף \( f^{\prime}\left(B\right)=b \) והופה - סתירה למקסימליות \( f \) (ייתכן שאתם רוצים עכשיו לשאול “אבל רגע, איך בחרת את \( b \) ב-\( B \) בלי אקסיומת הבחירה?”. התשובה היא שאין בעיה מבחינה מתמטית לבחור איבר מקבוצה יחידה; הבעיה מתעוררת כאשר צריך לבחור “בבת אחת” מאינסוף קבוצות).

כדי להראות שיש איבר מקסימלי ב-\( \mathcal{B} \) צריך להראות שלכל שרשרת יש חסם מלעיל, וזה כבר באמת נעשה באופן ה”סטנדרטי”: נניח שיש לנו שרשרת \( \mathcal{C} \) כלשהי של פונקציות בחירה חלקיות; נגדיר פונקציה חדשה בתור \( \bigcup\mathcal{C} \) (ובמילים - פונקציה שלכל \( A\in\mathcal{F} \) שמישהו ב-\( \mathcal{C} \) מוגדר עליה, מחזירה את הערך שאותו מישהו נותן ל-\( A \) - צריך טיפונת לעבוד כדי להראות שההגדרה המילולית הזו לא יוצרת בעיות של דו משמעות). הפונקציה הזו היא בבירור חסם מלעיל של השרשרת, מה שמסיים את ההוכחה.

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