הפרדוקס של ראסל ומשפט קנטור

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

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

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

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

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

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

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

נוהגים לסמן קבוצות עם סוגריים מסולסלים. למשל, \( A=\left\{ 1,2,5,1,4\right\} \) היא הקבוצה שהאיברים שלה הם 1,2,5,4 - אין חשיבות לסדר ההופעה של איברים ואם איבר מופיע פעמיים סופרים אותו רק פעם אחת (קיים מושג שנקרא Multiset שבו גם לכמות המופעים יש חשיבות, אבל אין לנו צורך בו). יש דרכי סימון יותר מחוכמות - כך למשל הסימון\( \mathbb{N}=\left\{ 1,2,3,\dots\right\} \) מייצג את קבוצת כל המספרים הטבעיים. אבל האופן הכי נפוץ שבו מסומנות קבוצות במתמטיקה הוא באמצעות קריטריון כלשהו. בצורת סימון זו עדיין כותבים סוגריים מסולסלים, אבל משתמשים בקו הפרדה באמצע שלהם, כשבצד ימין כתוב קריטריון כלשהו, ובצד שמאל כתוב “האיבר הכללי”של הקבוצה, באופן שנובע איכשהו מהקריטריון. זה מבלבל עד שרואים דוגמאות. למשל, \( \left\{ n^{2}|n\in\mathbb{N}\right\} \) היא קבוצת כל הריבועים; צריך לקרוא את זה בתור “כל האיברים מהצורה \( n^{2} \) כאשר \( n \) הוא מספר טבעי”.

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

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

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

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

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

בואו נחזור עכשיו לקנטור ולמשפט שלו. לצורך כך אני צריך לדבר על עוד מושג אחד, ולהציג עוד סימון אחד: תת-קבוצה. \( A \) היא תת-קבוצה של \( B \) אם כל איבר של \( A \) הוא גם איבר של \( B \), ובמילים - אם מתקיים שכאשר \( a\in A \) אז גם \( a\in B \). במקרה כזה מסמנים \( A\subseteq B \). למשל, עבור \( A=\left\{ 2,4,6,\dots\right\} \) מתקיים \( A\subseteq\mathbb{N} \) - הזוגיים הם תת-קבוצה של הטבעיים. אם \( A \) היא קבוצה, אז ב-\( P\left(A\right) \) מסמנים את קבוצת כל תתי הקבוצות של \( A \). למשל, אם \( A=\left\{ 1,2\right\} \) אז \( P\left(A\right)=\left\{ \emptyset,\left\{ 1\right\} ,\left\{ 2\right\} ,\left\{ 1,2\right\} \right\} \) כאשר \( \emptyset \) הוא הסימון המקובל עבור “הקבוצה שאין בה איברים” (כמו בקבוק שתיה ריק). ל-\( P\left(A\right) \) קוראים “קבוצת החזקה” של \( A \), אולי בגלל שאם ב-\( A \) יש \( n \) איברים, אז ב-\( P\left(A\right) \) יש \( 2^{n} \) איברים (זה נובע מקומבינטוריקה בסיסית - כל איבר יכול להיות שייך או לא שייך לתת-קבוצה של \( A \) בלי תלות ב-\( n \) האיברים האחרים, ולכן כל תת-קבוצה של \( A \) נקבעת על ידי סדרה באורך \( n \) של “כן”ו”לא”-ים). המושג של קבוצת החזקה אינו קל להבנה במיוחד, כך שאם איבדתם אותי נסו לשחק איתו טיפה בעצמכם.

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

ההוכחה פשוטה ויפה. נניח ש-\( f \) היא התאמה שכזו: כלומר, לכל \( a\in A \), נסמן ב-\( f\left(a\right) \) את האיבר של \( P\left(A\right) \) שאליו נעביר את \( a \). אם כן, \( f\left(a\right) \) היא קבוצה; תת קבוצה של \( A \) עצמה. כעת נגדיר את הקבוצה הבאה: \( X=\left\{ a\in A|a\notin f\left(a\right)\right\} \). במילים: כל האיברים של \( A \) שאינם איברים בקבוצה שהפונקציה “ציוותה”אותם איתה. מכיוון ש-\( X\subseteq A \) אז על פי ההנחה שלנו לגבי זה ש-\( A \) באותו גודל כמו \( P\left(A\right) \), קיים \( x\in A \) כך ש-\( f\left(x\right)=X \). אבל עכשיו אנחנו בבעיה - האם \( x\in X \) או לא?

\( x \) הוא בדיוק הספר שאינו מספר את עצמו. אם \( x\in X \) אז על פי הגדרת הקבוצה \( X \), מתקיים \( x\notin f\left(x\right)=X \) וזו סתירה. אבל אם \( x\notin X \) אז על פי הגדרת \( X \) מתקיים \( x\in f\left(x\right)=X \) וזו שוב סתירה. בקיצור, ההנחה שקיימת \( f \) כזו הייתה שגויה, ולכן הגודל של \( P\left(A\right) \) (אם בכלל ניתן לייחס לה גודל - זו לא הנחה טריוויאלית!) הוא גדול מזה של \( A \).

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