פרדוקס ראסל והגדרת המספר
בשנת 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 עם זו של שלוש, כך שבקבוצה שמתקבלת יש חמישה אברים. ניתן להגדיר כך בקלות גם חיסור, אם כי זה קצת מורכב יותר, אז נוותר על כך בפוסט הנוכחי.
ההגדרה הזו היא אינטואיטיבית. ישנו כלל לוגי שמנסח אותה, אבל הוא מורכב ואני לא בטוח איך וורדפרס תגיב לסימנים לוגיים. אפשר לבקש ממני אישית, אם רוצים. בכל מקרה, היא תקפה גם כך, מרגע שמבינים את הרעיון שלה. זו הגדרה לוגית למספר טבעי אריתמטי, כך שניתן לבצע בו פעולות, ושתקפה גם בתורת הקבוצות האקסיומטית - כלומר, גם אל נוכח פרדוקס ראסל.
היי! לא טענתי שקבוצה היא יש אונטולוגי, ולא טענתי שבעולם שבו יש דבר אחד יש, בעצם, שני דברים - טענתי שאפשר להגדיר קבוצה בעלת שני איברים. (חזרתי ובדקתי, אמנם כתבתי "אפשר למצוא שני עצמים בעולם כזה", אבל זו היתה הכוונה - וגם הבהרתי את זה אחר כך.)
וגם הטענה הזו מביאה לפרדוקסאליות.
אבל לפחות זו הפרדוקסליות שלי.
:)
מוצא חן בעיני שכל רשומה אצלך צומחת מהתגובות לרשומה שקדמה לה.
לא "כל רשומה", אבל יש כאן רצף לא רע. הרשומה הבאה בטוח לא. :)
טוב, ניטפוקים אין לי ממש אבל יש לי השגות חמורות למדי על הפסקה הבאה:
"פרדוקס ראסל חושף פגם בסיסי מאוד בתורת הקבוצות הנאיבית, כזה שהופך אותה לכמעט בלתי שמישה לחלוטין. יניב מדגים את זה באופן יוצא מהכלל בדיון שנערך בפוסט הקודם בנושא, שם יניב מנסה להגדיר את "2″ באמצעות תורת הקבוצות הנאיבית, כשהוא טוען ש"2″ הוא קבוצת כל הקבוצות שמכילות 2 אברים שונים."
הבעיה כאן היא שתורת הקבוצות הנאיבית, חד משמעית, היא כנראה הענף המתמטי השמיש ביותר שקיים. כמעט כל ספר מתמטיקה בסיסי (כזה שעוד טורח לספק מבוא שמתאר את המושגים המתמטיים שבהם משתמשים) יכיל מבוא שעוסק בתורת הקבוצות הנאיבית - וזאת בדיוק מכיוון שהיא כל כך הכרחית לכל תחום אחר. ואין הכוונה רק לדברים אלמנטריים לגמרי כמו איחודים, חיתוכים וכדומה; גם חשבון עוצמות וסודרים עשוי להיות רלוונטי במקומות רבים (דוגמאות מיידיות הן טופולוגיה קבוצתית ומידת לבג).
את תורת הקבוצות האקסיומטית, על אף חשיבותה, הספרים הללו לא טורחים לפרט, פשוט כי אין בכך צורך; כל עוד לא משתמשים בתורת הקבוצות במושגים מטורללים כמו קבוצת כל הקבוצות (או קבוצות ענק אחרות) לא נקלעים לבעיות (ולמעשה, לא חורגים מהתחום שתורת הקבוצות האקסיומטית "מוכיחה" את תקינותו).
האנלוגיה המתבקשת ביותר היא לתורת היחסות אל מול המכניקה הניוטונית. למרות שתורת היחסות מראה שהמכניקה הניוטונית פשוט שגויה, היא עדיין לא הופכת אותה ל"כמעט בלתי שמישה לחלוטין"; היא פשוט מראה כיצד צריך לטפל במקרי הקצה (שיכולים להיות מאוד חשובים בנסיבות מסויימות) שבהם המכניקה הניוטונית שוגה.
עוד דבר קצת בעייתי בציטוט הוא שאתה אומר, בשורה התחתונה "תראו כמה תורת הקבוצות הנאיבית בעייתית - X ניסה לעשות Y באמצעותה ולא הלך לו". מה הבעיה כאן? שאחר כך אתה מציג דרך פשוטה בהרבה לעשות את Y, שניתנת כולה לביצוע גם בתורת הקבוצות הנאיבית (וזה אכן מה שמלמדים כבר בתורת הקבוצות הנאיבית). באופן כללי נסיונות להראות שמשהו הוא קשה (או בלתי שמיש) על ידי הצגת נסיון כושל של מישהו (שאולי פשוט מסבך שלא לצורך) הם לא דברים משכנעים במיוחד לטעמי.
המשפט שלך "פרדוקס ראסל חושף פגם בסיסי מאוד בתורת הקבוצות הנאיבית, כזה שהופך אותה לכמעט בלתי שמישה לחלוטין" נכון רק אם אתה פילוסוף של המדעים, או לוגיקאי, או דרמה-קווין מסוג אחר. כשאני משתמש בתורת הקבוצות, אני לא משתמש באקסיומות ZFC, אלא עובד עם מה שהוא בעצם תורת הקבוצות הנאיבית. כל עוד לא מסתובבים באיזורים המפוקפקים שהפרדוקסים מסתובבים בהם (יד חרוצים, בפעם האחרונה שבדקתי), אין יותר מדי ממה לחשוש. הטענה שלך שקולה לאמירה
"פרדוקס ברטרנד [ראה לינק למטה] חושף פגם בסיסי מאוד בתורת ההסתברות, כזה שהופך אותה לכמעט בלתי שמישה לחלוטין"
או
"העובדה שפונקציית דיריכלה אינה אינטגרבילית-רימן חושף פגם בסיסי מאוד עם אינטגרל דיריכלה, כזה שהופך אותו לכמעט בלתי שמיש לחלוטין"
או, האהוב עלי
"משפט גדל חושף פגם בסיסי מאוד במתימטיקה, כזה שהופך אותה לכמעט בלתי שמישה לחלוטין"
וכן הלאה וכן הלאה.
והנה רשימת פרדוקסים בוויקיפדיה:
http://en.wikipedia.org/wiki/List_of_paradoxes
והנה לינק לפרדוקס של ברטרנד:
http://en.wikipedia.org/wiki/Bertrand%27s_paradox_(probability)
והנה לינק למידע על פונקציית דיריכלה:
http://en.wikipedia.org/wiki/Nowhere_continuous_function
הלינק האחרון לא כתוב כל כך טוב, וגם לא מזכיר את העובדה שפ' דיריכלה לא אינטגרבילית. אולי כדאי שאני אוסיף את זה).
למיטיבי לכת: הפתרון לצרה עם פונקציית דיריכלה הוא אינטגרל לבג המהולל, שבו פונקציית דיריכלה ודומותיה אינטגרביליות, והאינטגרל שלהן מתנהג כמו שהוא אמור להתנהג. רק שקשה יותר לעבוד עם אינטגרל לבג בסיטואציות מסויימות, אז האינטגרל שיותר נפוץ לעבוד איתו בסיטואציות מסויימות הוא בכל זאת אינטגרל רימן.
רגע, שכחתי את הכי טוב:
"פרדוקס בנך-טרסקי חושף פגם בסיסי מאוד עם הגיאומטריה, כזה שהופך אותה לכמעט בלתי שמישה לחלוטין"
http://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox
אלעד וגדי (ברוך הבא) - ציפיתי להערה הזו. בהחלט, תורת הקבוצות הנאיבית היא שמישה ביותר עבור אנשים שבאים מהמקצוע שלכם - מתמטיקאים וכאלה דברים מפוהקים :)
בתחום שלי, לעומת זאת - הלוגיקה בקונטקסט הפילוסופי שלה - תורת הקבוצות הנאיבית היא עצם בגרון. היא עצם בגרון בגלל החומרה שהלוגיקה דורשת. כשהיא בסביבה, כל שפת תחשיב הפרדיקטים - אולי הצורה הכי "טבעית" להצרנה של טענות מילוליות, וחוץ מזה השפה הלוגית האהובה עליי - יושבת על "באג", וזה, אם לנקוט בלשונו של ג'רי סיינפלד, קניידעלך די גדול.
נתנו לי פעם לבחור שלושה אנשים מתים שהייתי שמח לשבת אתם לקפה. הבחירה שלי הייתה, בסדר הזה, משה רבנו, אריסטו ופרגה. פרגה, כי אני לא מצליח להבין מדוע הוא זנח את כתיבת הכרך השני של יסודות האריתמטיקה - לפרדוקס ראסל ממילא לא הייתה שום נגיעה למקום בו פרגה הניח את עטו - כשגילה את הפגם בשיטה. אני מניח, והלוואי והייתה לי דרך לאשש את הטענה הזו, שפרגה חשב כפילוסוף אנליטי ולא כמתמטיקאי בשעה שהניח את עטו. הפילוסופיה האנליטית, אז באמצע מלחמה בעולם ההגליאני והפנומנולוגי של הפילוסופיה הקונטיננטאלית, לא הייתה יכולה להרשות לעצמה מפלה כזו בבסיס שלה.
שתי הטענות העיקריות שלכם, אם אני מבין אותן נכון, הן שתורת הקבוצות הנאיבית טובה לחלוטין כל עוד מתחמקים ממגע עם "בעיות ראסליאניות", ושהיא טובה מאוד לצורך המשגה. זה נכון, אבל זה נכון גם לגבי תורת הקבוצות האקסיומטית, והיא חפה מה"באג". כשיש לי - ואני מזכיר שאני מדבר כאן בכובע הפילוסוף ולא בכובע המתמטיקאי, מהטעם הפשוט שאין לי כובע כזה - שתי שיטות, שתכונותיהן דומות, והאחת סתירתית בעוד השניה נכונה, אני אעדיף את הנכונה. אם הייתי מוסיף, בסוף המשפט שהפריע לכם, את שתי המילים "בהקשר הזה", זה היה בוודאי מפחית את ההתנגדות, אלא שבשעת כתיבת הפוסט המשמעות המתמטית של תורת הקבוצות הנאיבית פשוט לא הייתה אצלי בתודעה. חטא, אני יודע, אבל חטא קטן, לפחות בעיניי. בכל אופן, אני באמת ובתמים שמח ששני המתמטיקאים שקוראים כאן (אלעד, אני לא יודע אם אתה מכיר את הבלוג של גדי, אבל נראה לי שהוא יכול להיות לך מאוד מעניין) תיקנו אותי בנושא הזה, ומקבל בהכנעה את התיקון. ואלעד, תודה על הקישורים המאלפים. אם יורשה לי, אולי כאן המקום להדגיש שהתגובות כאן מקבלות תגי הטמל, ואפשר בהחלט לשים קישורים אלגנטיים.
גדי, לעניין הערתך השניה, ממש לא טענתי "תראו, x ניסה לעשות y ולא הלך לו". כתבתי שמדובר בדוגמה טובה לבעייתיות שבתורת הקבוצות הנאיבית (יש איזה ראשי תיבות מקובלים לדבר הזה?) ותו לא, וזה נעשה קודם כל כדי לתת ליניב את הבמה שמגיעה לו - אני שמח מאוד על ההשתתפות הפעילה שלו כאן ונהניתי מאוד מהדיון איתו בפוסט הקודם, ורציתי להפנות את שבעים וכמה קוראי הרסס ומספר דומה או גדול ממנו של ביקורים ביום כאן לבלוג שלו - וכדי לתת לו את הקרדיט על שדחף אותי לכתוב את הפוסט הזה - אם תעיין פה קצת תראה שזה חורג מהנושאים שאני עוסק בהם ברגיל. מעבר לזה, זו באמת דוגמה טובה לחוסר השמישות הלוגי של תורת הקבוצות הנאיבית.
נכון, השיטה שהראיתי ניתנת כולה לעשייה בתורת הקבוצות הנאיבית (ובאמת, מי שהגה אותה היה אותו הפרגה, אם אינני טועה), אבל היות שהתורה הזו נטולת תוקף לוגי במובנו החמור, הבעייתיות הייתה נשארת לולא הייתה ניתנת לנו מערכת האקסיומות ZFC.
וחוץ מזה, הרבה זמן חלף מאז התדיינו ככה, אני אישית מרוצה. :)
מצחיק שגדי ניצח אותי בבערך חצי שעה. לא שמתי לב לזה כשכתבתי את התגובה שלי. אל הבלוג של גדי התוודעתי אחרי שראיתי את הלינק אצלך, וקראתי אחורה עד עמוד 5 בערך. מאד מאד מעניין.
לא טרחתי עם ההטמל כי מפחיד אותי הטמל בשילוב עם עברית (ואת זה אומר אדם שתכנת אתר בגיאוסיטיז חמוש רק בעורך טקסט, בשנת 96 לערך), אבל אני אשתדל להבא.
נמרוד, בנושא ZFC לעומד תורת הקבוצות הנאיבית, כתבת: "כשיש לי [...] שתי שיטות, שתכונותיהן דומות, והאחת סתירתית בעוד השניה נכונה, אני אעדיף את הנכונה."
הממ, עוד לא ראיתי פיזיקאי מחשב מהירות של גוף שמחליק על גבעה בעזרת מכניקת הקוונטים, או לחילופין בעזרת תורת היחסות. למען האמת, אני לא בטוח שראיתי פיזיקאי מחשב איזשהי אינטראקציה בין יותר משניים-שלושה חלקיקים בעזרת מכניקת הקוונטים.
כלומר, עם כל הכבוד לפרדוקסים כאלה ואחרים, כשאני מגדיר גרף כקבוצת קודקודים ועוד קבוצה של זוגות של קודקודים, אם סטודנט יעיר לי על הפרדוקס של ראסל הוא יחטוף מכות.
הצורה שדברים נראים מהצד שלכם אינה הצורה שהם נראים מהצד שלנו: אנחנו אשכרה צריכים לעבוד עם הדברים האלה, וכל עוד אני צריך להגדיר אובייקטים סבירים, פרדוקס ראסל לא מעניין אותי בכלל. הרי אנחנו לא באמת יכולים לעבוד עם ZFC. ברור שנעבוד עם תורת הקבוצות הנאיבית, כי כל בחירה אחרת תהיה טרחנית וטיפשית, כמו פיזיקאי שמתחשב באפקטים יחסותיים כשהוא מחשב את הזמן שיקח לו להגיע לחתונה שהוא מאחר אליה.
הוא שאמרתי, אלעד - לכם בוודאי יש שימוש בתורת הקבוצות הנאיבית. עבורי, היא קוץ בישבן, או עצם בגרון.
[...] הם נראים לי כמו המחשה לבלבול שנובע מהגדרות גרועות. גם הפרדוקס של ראסל לא מטריד אותי במיוחד, כי ברור לי שתורת הקבוצות הנאיבית [...]