אז מה זו תורת הקבוצות?

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

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

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

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

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

האופן שבו כותבים קבוצות באופן במתמטיקה הוא בדרך כלל בעזרת סוגריים מסולסלים שביניהם כתובים האיברים של הקבוצה כשהם מופרדים על ידי פסיקים. למשל \( \left\{ 1,3,7\right\} \) היא קבוצה בת שלושה איברים: המספרים “אחד”, “שלוש” ו”שבע”. אני אוהב גם לכתוב התחכמויות כמו הקבוצה }חתול, \( \pi \), פריז{ כדי להראות שאפשר לערבב כל מני דברים לא קשורים בתוך אותה קבוצה - אבל בפועל אנחנו לא באמת עושים את זה במתמטיקה, וקבוצות הן לא סתם איברים אקראיים שנבחרים בצורה חסרת הגיון בשביל הקטע.

עכשיו, נניח שאני רוצה לכתוב את קבוצת כל המספרים הטבעיים בין 1 ל-10 שהבטחתי קודם. איך אני אעשה את זה? אני יכול לכתוב \( \left\{ 1,2,3,4,5,6,7,8,9,10\right\} \) אבל זו בערך הפעם האחרונה אי פעם שארצה לכתוב משהו כל כך ארוך ומזעזע. זכרו את כלל היסוד של המתמטיקה: מתמטיקאים הם עצלנים. המטרה של המתמטיקאים היא לחסוך כאב ראש, לא להרבות אותו. אז איך נכתוב את הקבוצה הזו עם פחות כאב ראש? הנה דרך אחת:

\( \left\{ 1,2,\dots,10\right\} \)

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

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

\( \left\{ n\in\mathbb{N}\ |\ 1\le n\le10\right\} \)

מה הולך פה? פתאום הוספתי למשחק המון סימנים חדשים ולא מוכרים. בואו נסביר אותם. \( \mathbb{N} \) היא קבוצת המספרים הטבעיים (“אבל לא הגדרת עדיין מספרים טבעיים!” זועקים החכמולוגים - וזה נכון, עוד נגדיר אותה בהמשך, עכשיו אני מדגים דברים בסיסיים).. הסימן \( \le \) הוא היחס “קטן-שווה” (“אבל לא הגדרת עדיין יחסים וקטן-שווה” זועקים החכמולוגים - אוקיי, שמעו חברים, הבנתי) והאות \( n \) היא “משתנה” - היא משהו שיכול לקבל כל מני ערכים שונים ומשונים. בנוסף לכל אלו יש גם קו אנכי שתקוע באמצע הקבוצה. הרעיון הוא שמה שמשמאל לקו מתאר איזו שהיא צורה כללית של איבר של הקבוצה, ומה שמימין לקו מתאר קריטריון כלשהו שמגביל את האיבר הכללי. בעצם מה שכתבתי כאן הוא “קבוצת כל המספרים הטבעיים (עד כאן צד שמאל) שבין 1 ל-10 (זהו צד ימין)”.

קודם אמרתי שההנחה שלנו היא שלכל קבוצה \( A \) ולכל איבר \( a \), או שמתקיים \( a\in A \) או שמתקיים \( a\notin A \). מה אם לכל \( a \) ביקום, מתקיים \( a\notin A \)? האם אנחנו מרשים כזו סיטואציה, של קבוצה שאין לה איברים בכלל? התשובה חיובית. אנחנו מניחים שקיימת קבוצה \( \emptyset \) שנקראת הקבוצה הריקה ולכל \( a \) אפשרי, \( a\notin\emptyset \). אפשר לסמן את הקבוצה הזו גם בתור \( \left\{ \right\} \), כלומר סוגריים מסולסלים שאין כלום ביניהם, אבל אני מעדיף את \( \emptyset \) (הערה טרחנית - הסימון \( \emptyset \) מקורו באות נורווגית; זו לא האות “פי” היוונית, \( \phi \) - אבל למי אכפת, בעצם).

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

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

\( 0\triangleq\emptyset \)

עכשיו אני אגדיר את 1 להיות הקבוצה שהאיבר היחיד שלה הוא 0:

\( 1\triangleq\left\{ 0\right\} \)

ואת 2 אני אגדיר להיות הקבוצה שהאיברים שלה הם \( 0,1 \):

\( 2\triangleq\left\{ 0,1\right\} \)

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

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

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

\( \omega\triangleq\left\{ 0,1,2,\dots\right\} \)

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

\( \omega+1\triangleq\left\{ 0,1,2,\dots,\omega\right\} \)

ואפשר גם להשתגע עם זה עוד ועוד, למשל:

\( \omega+\omega\triangleq\left\{ 0,1,2,\dots,\omega,\omega+1,\omega+2,\dots\right\} \)

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

אני רוצה עכשיו להציג “בעיה” ומיד לאחר מכן את הפתרון שלה. נתחיל משאלה פשוטה - מתי בעצם שתי קבוצות שוות זו לזו? מתי \( A=B \)? הגישה שלנו היא זו: קבוצות הן שוות אם יש להן את אותם האיברים. כלומר, בניסוח מתמטי, אם לכל איבר \( a \) מתקיים \( a\in A\iff a\in B \) (את החץ הדו-כיווני הזה צריך לקרוא בתור “אם ורק אם”; פירושו הוא שאם אחד מהאגפים מתקיים אז גם השני מתקיים). זה אומר שאם יש לי שתי קופסאות שבשתיהן יש את האיברים \( 1,2 \) ותו לא, אז זו אותה קופסה. ולא משנה אם אחת צבועה בצבעים עליזים ירוקים והשניה באפור מצער; ולא משנה אם על אחת כתוב “תיבת הפלאים של אליס” ועל השני כתוב “הכספת של בוב”. אותם איברים? אותה קבוצה.

בפרט, מהגישה הזו נובע ש-\( \left\{ 1,2\right\} =\left\{ 2,1\right\} \). למה? כי בשתי הקבוצות הללו יש את אותם איברים. האיברים כתובים בסדר שונה, אבל זה לא משפיע על שאלת השייכות/אי השייכות לקבוצה. זה לא שאפשר לומר “1 שייך לקבוצה אבל לפני 2”. זה מושג שלא קיים בעולם המושגים שלי בכלל. באופן דומה, \( \left\{ 1,1\right\} =\left\{ 1\right\} \). כלומר, איבר לא יכול להיות “שייך פעמיים” לקבוצה; הוא או שייך או לא שייך, וזהו. אפשר לכתוב את אותו איבר כמה פעמים וזה גם נוח לפעמים, אבל עותקים “מיותרים” של אותו איבר לא משפיעים על זהות הקבוצה.

שני הדברים הללו נראים כמו חסרונות מהותיים של מושג הקבוצה. איך אפשר לייצר סדר מתוך האי-סדר הזה? המושג שאני רוצה לייצר הוא מה שנקרא זוג סדור וכולנו כנראה נתקלנו בו פעם - למשל, בתור קואורדינטות. אני מסמן זוג סדור ב-\( \left(x,y\right) \) והרעיון הוא ש-\( \left(x,y\right)=\left(a,b\right) \) אם ורק אם \( x=a \) וגם \( y=b \). כלומר, \( \left(1,2\right)\ne\left(2,1\right) \), למשל. עכשיו, אני יכול פשוט להוסיף את המושג הזה של “זוג סדור” למתמטיקה ולעבוד איתו וחסל, וכך עושים בהרבה מקומות; אבל זה תרגיל נחמד להיות טהרן של קבוצות ולחשוב איך אפשר “לממש” זוג סדור בעזרת קבוצות בלבד, שאין בהן סדר.

ברור שאני לא יכול להגדיר \( \left(x,y\right)\triangleq\left\{ x,y\right\} \) כי אז נקבל \( \left(1,2\right)=\left\{ 1,2\right\} =\left\{ 2,1\right\} =\left(2,1\right) \) וזה בדיוק מה שרציתי להימנע ממנו. צריך איכשהו “לשבור סימטריה”. אם כל הכלים שיש לי בעולם הם קבוצות, אז הדרך “לשבור סימטריה” היא “לעטוף” את אחד האיברים בקבוצה ואת השני לא. כלומר, על פניו נראה שזה רעיון טוב להגדיר \( \left(x,y\right)\triangleq\left\{ x,\left\{ y\right\} \right\} \). זה כמעט עובד אבל גם זה יכול להיכשל, בצורות די מטופשות.

הנה דרך ממש טיפשית שבה העסק יכול להתחרבש: מה אם \( x=\left\{ 1\right\} \) ואילו \( y=2 \)? במקרה הזה, על פי ההגדרה נקבל \( \left(x,y\right)=\left(\left\{ 1\right\} ,2\right)=\left\{ \left\{ 1\right\} ,\left\{ 2\right\} \right\} \). כלומר, התוצאה שלנו הפכה לסימטרית, וזה בדיוק מה שחששנו מפניו: באותה מידה גם יתקיים \( \left(\left\{ 2\right\} ,1\right)=\left\{ \left\{ 1\right\} ,\left\{ 2\right\} \right\} \) אבל כמובן ש-\( \left(\left\{ 1\right\} ,2\right)\ne\left(\left\{ 2\right\} ,1\right) \).

הדרך לפתור את הבעיה הזו היא לוודא ש-\( x,y \) עטופים באותה כמות סוגריים וליצור חוסר סימטריה בצורה טיפה שונה: \( \left(x,y\right)\triangleq\left\{ \left\{ x\right\} ,\left\{ x,y\right\} \right\} \). הבניה הזו עובדת: מקבלים באמת ש-\( \left(x,y\right)=\left(a,b\right) \) (כאן זה שוויון קבוצות) אם ורק אם \( x=a \) וגם \( y=b \). נסו להוכיח זאת!

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

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

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

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

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

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

אם \( D\in D \), אז בפרט \( D \) מקיימת את הקריטריון שקובע מתי איברים שייכים ל-\( D \). הקריטריון הזה היה, כזכור, \( A\notin A \). אם \( D \) מקיימת אותו, אז אנחנו אמורים להיות מסוגלים להציב אותה במקום האיבר הכללי \( A \). כלומר, המסקנה מ-\( D\in D \) היא שמתקיים \( D\notin D \). אבל שני אלו לא יכולים להתקיים בו זמנית, והגענו לסתירה.

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

עכשיו בואו נניח ש-\( D\notin D \). אם \( D \) אינה איבר של \( D \), אז \( D \) אינה מקיימת את הקריטריון שמגדיר שייכות ל-\( D \); כלומר, היא אינה מקיימת את \( A\notin A \). מכיוון שיכול להתקיים רק \( A\notin A \) או \( A\in A \), המסקנה היא ש-\( D \) כן מקיימת את \( A\in A \), כלומר \( D\in D \), והגענו שוב לסתירה ושום דבר לא יעזור לנו.

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

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