פרדוקס ראסל והגדרת המספר

בשנת 1901 שלח הפילוסוף ברטראנד ראסל מכתב לגוטלוב פרגה – אביה המעשי של הפילוסופיה האנליטית – בזמן שהאחרון שקד על הכרך השני של ספרו "יסודות האריתמטיקה", מכתב ובו שאלה אחת. למקרא השאלה, הניח פרגה את השלמת הספר.

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

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

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

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

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

פרדוקס ראסל חושף פגם בסיסי מאוד בתורת הקבוצות הנאיבית, כזה שהופך אותה לכמעט בלתי שמישה לחלוטין. יניב מדגים את זה באופן יוצא מהכלל בדיון שנערך בפוסט הקודם בנושא, שם יניב מנסה להגדיר את "2″ באמצעות תורת הקבוצות הנאיבית, כשהוא טוען ש"2″ הוא קבוצת כל הקבוצות שמכילות 2 אברים שונים. "קבוצת כל הקבוצות" היא מתכון בטוח לצרות צרורות. למשל, את ההגדרה של יניב ניתן בקלות להביא לאבסורד: בעולם שבו יש רק שתי קבוצות שמכילות שני אברים, האם קבוצת כל הקבוצות שמכילות שני אברים כוללת את עצמה או לא? אם היא כוללת את עצמה, אז יש בה שלושה אברים והיא לא צריכה לכלול את עצמה. אם היא לא כוללת את עצמה, אז יש בה שני אברים והיא צריכה לכלול את עצמה. זה תקף בין אם קיים עולם כזה אם לאו – הגדרת המספר צריכה להיות אוניברסלית, כי 2+2=4 תמיד.

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

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

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

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

ככה זה ממשיך. שלוש יכיל קבוצה שמכילה את 2 (קרי, קבוצה שיש בה קבוצה ריקה וקבוצה שמכילה את הקבוצה הריקה) ואת 2 – קבוצה שמכילה קבוצה ריקה וקבוצה ריקה.

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

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

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

*אמריקאי: 10 בחזקת 18, אירופאי: טריליון, מיליון מיליונים.