לבחור או לא לבחור - זו השאלה

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

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

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

ובכן, מה היא אקסיומת הבחירה? היא הטענה הפשוטה הבאה: נניח שיש לנו קבוצה \( X \) של קבוצות לא ריקות. אקסיומת הבחירה אומרת כי קיימת פונקציה המתאימה לכל קבוצה מתוך \( X \) איבר השייך לה. בכתיבה פורמלית: יש פונקציה \( f \) כך שלכל \( A\in X \) מתקיים \( f(A)\in A \).

הנה דוגמה לפונקציה שכזו עבור מקרה ספציפי: נניח ש-\( X=\{\{1,2\},\{a,b,c\}\} \), אז פונקצית בחירה לדוגמה היא הפונקציה הבאה: \( f(\{1,2\})=1, f(\{a,b,c\})=c \).

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

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

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

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

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

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

בצורה מתמטית התיאור של כל הבלאגן הזה פשוט יותר. נגדיר \( X=\left\{y|y\notin y\right\} \) . אם נניח שזו קבוצה, נגיע מיד לסתירה מכיוון שלא ייתכן ש-\( X\in X \), וגם לא ייתכן שזה לא מתקיים (למה?)

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

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

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

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