בסיס מוצק מי ימצא

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

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

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

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

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

עכשיו, נניח שנתונה לנו קבוצה בלתי תלויה \( A \) של וקטורים. נגדיר את אוסף הקבוצות שעליו נרצה להפעיל את הלמה של צורן בתור אוסף הקבוצות הבלתי תלויות של איברים שמכילות את \( A \). אם נמצא איזו שהיא קבוצה בלתי תלויה “מקסימלית” \( B \) מבין כל הקבוצות הללו, נסיים. למה? כי מהמקסימליות נובע שכל איבר שנוסיף לה יהפוך אותה לתלויה לינארית (כי אם כשמוסיפים את האיבר \( x \) לקבוצה \( B \) מקבלים שוב קבוצה בלתי תלויה זו סתירה למקסימליות של \( B \), שכן \( B\subseteq B\cup\{x\} \).

כדי להשתמש בלמה של צורן, אם כן, יש צורך לקחת “שרשרת”, להראות שיש לה חסם מלעיל. נניח ש-\( A_\Lambda \) היא שרשרת שכזו (האינדקס המשונה - האות היוונית למבדא - בא לציין שהשרשרת אינה בהכרח מכילה מספר בן מניה בלבד של איברים. מי שזה לא מסתדר לו עם קיום יחס הסדר יכול להיזכר שגם על המספרים הממשיים מוגדר יחס סדר). התעלול המקובל הוא להגדיר את חסם המלעיל בתור איחוד כל הקבוצות הללו: \( C=\cup A_\Lambda \). ברור שהוא חסם מלעיל לשרשרת (כי הוא מכיל כל איבר באיחוד), וכל מה שצריך להראות הוא שגם הוא איבר באוסף כל הקבוצות הבלתי תלויות שמכילות את \( A \).

טוב, ברור שהוא מכיל את \( A \) (למה?) אבל פחות ברור שהוא בלתי תלוי. כדי להראות את זה מניחים בשלילה שהוא תלוי ולכן יש מספר סופי של וקטורים \( a_1,\dots,a_n\in C \) שיוצרים את 0 בצירוף לינארי לא טריוויאלי. כאן נכנס העוקץ לתמונה: אמרנו ש-\( C \) היא איחוד של כל ה-\( A_\Lambda \), ולכןכל איבר \( a_i \) שייך לאיזו שהיא קבוצה \( A_i \) מהשרשרת. מכיוון שכולן מקיימות יחס סדר, פשוט בוחרים את הקבוצה הגדולה ביותר מתוך \( n \) הקבוצות הללו ומובטח שהיא תכיל את כל \( n \) האיברים \( a_1,\dots, a_n \) (למה?) אבל הקבוצה הזו היא קבוצה בלתי תלויה, על פי הגדרת השרשרת… ולכן לא ייתכן שהצירוף של \( a_1,\dots, a_n \) נותן 0 בצורה לא טריוויאלית, וזה מסיים את ההוכחה.

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

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

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

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

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

המטרה: שלכל היותר מספר סופי של אנשים יטעו בתשובה שיתנו.

בהצלחה!