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

תורת הקבוצות היא אחד מהנושאים הבסיסיים שלומדים סטודנטים למתמטיקה בימינו. המושג המרכזי שבו היא עוסקת הוא מושג האינסוף – ולא אינסוף פילוסופי אבסטרקטי "בלתי מושג" ו"בלתי מובן", אלא אינסוף מאוד קונקרטי ומתמטי; כל כך קונקרטי, שניתן לסווג גדלים אינסופיים למספר סוגים שונים של גדלים; יש אינסוף "קטן" ויש אינסוף "גדול יותר", ולמעשה יש אינסוף גדלים שונים של אינסוף. האינסוף הקטן ביותר הוא גודלה של קבוצת המספרים הטבעיים – למספרם של המספרים הטבעיים קוראים $latex \aleph_0$ (ממש האות העברית אלף – זו האות שבה בחר קנטור, ממציא תורת הקבוצות, להשתמש). לעומת זאת, אפשר להראות שגודל קבוצת המספרים הממשיים הוא אינסוף שהוא "גדול ממש" מ-$latex \aleph_0$ (ההוכחה נקראת "האלכסון של קנטור" וכבר הראיתי אותה כאן), וגודל זה מסומן בתור $latex \aleph$ (בלי אפס). ואז צצה השאלה המעניינת – האם יש גודל אינסופי שהוא "בין" $latex \aleph_0$ ובין $latex \aleph$? גדול ממש מהאחד, אבל קטן ממש מהשני? הסברה הרווחת בזמנו של קנטור, כאשר השאלה עלתה, היא שלא קיים גודל שכזה, וסברה זו נקראה "השערת הרצף".

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

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

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

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

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

כדי לתאר טענות צריך להשתמש בשפה כלשהי. במתמטיקה לא משתמשים בעברית או באנגלית אלא בשפות פורמליות, שמכילות סימנים עבור משתנים, קבועים, פונקציות ויחסים. למשל, $latex x,y$ יכולים להיות משתנים, $latex <$ הוא סימן יחס, ו-$latex x<y$ היא כבר טענה של ממש, שבה טוענים שבין הערך של המשתנה $latex x$ והערך של המשתנה $latex y$ יש את היחס ">". מה שמעניין כאן הוא שלא ברור את מה המשתנים מייצגים בעצם – האם אלו מספרים? ואולי אלו דווקא עצים בינאריים? או מילים בשפה העברית? או בני אדם? ומה הסימן ">" מייצג? האם זה "קטן מ-", או שיש לו משמעות אחרת?

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

חזרה לשפה. יש הרבה סוגים שונים של שפות שאפשר לדבר עליהן, אבל כל מה שאנחנו נתעסק בו הוא מה שנקרא "שפה מסדר ראשון". בשפה כזו אפשר לטעון טענות "אטומיות" על משתנים וקבועים ($latex x<y$ היא דוגמה לטענה כזו; אבל גם "$latex x$ זוגי" היא טענה לגיטימית, כל עוד מתייחסים ל"זוגי" בתור שם כלשהו לתכונה ולא מייחסים לה, בשלב זה, משמעות כלשהי), וכמו כן ניתן לטעון טענות "מכומתות" שלא מדברות על איבר ספציפי אלא על איבר כלשהו מבין כל האיברים הקיימים, כמו "כל $latex x$ הוא זוגי", או "קיים $latex x$ שהוא זוגי". ה"סדר ראשון" שיש בשם השפה מעיד על כך שאפשר לכמת רק איברים בודדים; בשפה מסדר שני אפשר לטעון גם טענות כמו "אם לכל קבוצה של $latex x$-ים מתקיים כך וכך אז קיימת קבוצה של $latex x$-ים שמקיימת כך וכך", אבל כאמור, לא על זה נדבר כאן. מי שלא ממש הבין על מה דיברתי בפסקה הזו, לא נורא; זה לא הכרחי כדי להבין את הרעיון הכללי, אם כי זה קריטי למי שמנסה ללמוד את הדברים הללו בצורה מסודרת.

כעת אפשר לתאר תורות. כל תורה מוגדרת מעל שפה כלשהי, ומכילה אוסף של אקסיומות שמנוסחות בלשון אותה שפה. למשל, אם בשפה שלנו יש את התכונה "זוגי" ואת הפונקציה "+", אז אפשר להכניס לתורה את האקסיומה "$latex x$ זוגי אם ורק אם קיים $latex y$ כך ש-$latex x=y+y$". זו דוגמה לטענה שניתן לנסח בשפה, גם באופן פורמלי לחלוטין: $latex A(x)\leftrightarrow \exists y(x=y+y)$, כאשר אנחנו משתמשים ב-$latex A(x)$ בתור ייצוג סימבולי של היחס "$latex x$ זוגי". העובדה שהאקסיומה הזו היא חלק מהתורה שלנו גורמת ליחס "זוגי", שעד כה היה חסר משמעות לגמרי, לקבל משמעות כלשהי – מעתה, $latex x$ הוא זוגי אם ורק אם קיים $latex y$ כך ש-$latex x=y+y$. אלא שמשמעות הטענה האחרונה הזו לא ברורה עד הסוף, כי לא ברור מה המשמעות של "=" ושל "+" כאן – תחת פרשנויות שונות של הסימנים הללו, גם המשמעות של "$latex x$ זוגי" תשתנה.

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

השפה של תורת החבורות כוללת משתנים (שמסמנים בדרך כלל ב-$latex x,y,z,\dots$), קבוע $latex e$ שבא לייצג איבר מיוחד, סימן פונקציה יחיד, שבא לייצג פעולה בין שני איברים בחבורה (כשתוצאת הפעולה היא עצמה איבר בחבורה) ומסומן בנקודה (כמו פעולת "כפל"), וביחס בודד – שוויון. בכל תורה שיש בה את יחס השוויון יש אקסיומות שנותנות לפעולת השוויון משמעות הדומה לזו האינטואיטיבית (איבר יכול להיות שווה רק לעצמו, למשל) אבל לא נציג אותן כאן כדי לא לסבך, אלא נתמקד רק באקסיומות המיוחדות של תורת החבורות, ומה הן?

  1. $latex \forall x,y,z(x\cdot(y\cdot z)=(x\cdot y)\cdot z)$ ("אסוציאטיביות")
  2. $latex \forall y(e\cdot y=y \wedge y\cdot e=y)$ ("איבר יחידה")
  3. $latex \forall x\exists y(x\cdot y=e \wedge y\cdot x=e)$ ("קיום הופכי")

אם כן, מה האקסיומות אומרות? הראשונה אומרת שכאשר "כופלים" שלושה איברים (מעתה והלאה אקרא לפעולה "כפל" גם בלי מרכאות, אבל כפי שנראה בהמשך, היא לא חייבת לייצג את פעולת הכפל הרגילה) אין חשיבות לשאלה האם קודם כל נכפול את $latex x$ ב-$latex y$ ורק את התוצאה נכפול ב-$latex z$, או שמא קודם כל נכפול את $latex y$ ב-$latex z$ ורק אחר כך נכפול את $latex x$ בתוצאה.

האקסיומה השניה אומרת שהאיבר המיוחד שסומן באות $latex e$ הוא בעל התכונה שכל איבר שמוכפל בו (הן מימין והן משמאל) לא משתנה. האקסיומה השלישית אומרת שלכל איבר קיים איבר "הופכי" כך שהמכפלה של שניהם (ושוב, לא משנה מי מימין ומי משמאל) מחזירה את האיבר המיוחד $latex e$.

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

אבל אין מה לעשות. אם לוקחים שלושה מספרים שלמים $latex x,y,z$ רואים שמתקיים $latex x+(y+z)=(x+y)+z$ (איך רואים? איך מוכיחים את זה? זו שאלה לדיון נפרד). כמו כן, המספר 0 הוא בעל התכונה המעניינת ש-$latex x+0=0+x=x$, ולכל מספר שלם $latex x$ קיים מספר $latex -x$ כך ש-$latex x+(-x)=(-x)+x=0$. אם כן, זה נראה כמו חבורה, וההבדל היחיד הוא בסימונים – במקום $latex \cdot$ אנחנו משתמשים בסימן +, ובמקום $latex e$ אנחנו משתמשים בסימון $latex 0$. אם כן, המספרים השלמים הם פרשנות אפשרית אחת לתורת החבורות, פרשנות שבה ה"עולם" שאיברים ממנו מיוצגים בידי משתנים הוא אוסף המספרים השלמים, הסימן $latex e$ מפורש בתור המספר אפס, והסימון $latex \cdot$ מפורש בתור פעולת החיבור. שימו לב מה אני עושה כאן – אני מתאים סימון, שהוא בסך הכל אוסף של תווים, למשהו בעל משמעות, כמו פעולה חשבונית, או מספר.

זו פרשנות אפשרית אחת. פרשנות אפשרית אחרת היא מטריצות הפיכות מסדר 2 מעל הממשיים, למשל. מי שאינו מכיר מטריצות, לא נורא; די לדעת שמדובר במעין טבלאות של מספרים, ושמוגדרת עליהן פעולת כפל מחוכמת למדי; הפעולה מקיימת את כל האקסיומות של חבורה, אבל בנוסף אם $latex A,B$ הן מטריצות אז ייתכן שיתקיים $latex A\cdot B\ne B\cdot A$, כלומר בכל פעולת כפל יש חשיבות לשאלה מי מימין ומי משמאל (שימו לב שזה שונה מתכונת ה"אין חשיבות לסדר" של האסוציאטיביות, כי באסוציאטיביות לא מחליפים פעולה של כפל מימין בפעולה של כפל משמאל).

אם כן, ניתן לפרש את תורת החבורות גם כאילו האיברים שלה הן מטריצות הפיכות מסדר 2 מעל הממשיים, הסימן $latex \cdot$ מייצג פעולה של כפל מטריצות, והסימן $latex e$ מייצג את מטריצת היחידה (מטריצה שיש אחדות באלכסון שלה, וכל שאר הכניסות שלה הן 0). די ברור שזוהי פרשנות שונה מהותית מאשר הפרשנות של "מספרים שלמים"; לא רק בגלל שהאובייקטים שבשתי הפרשנויות שונים (מטריצות אל מול מספרים), אלא בעיקר בגלל שיש טענות שנכונות רק בפרשנות אחת, ולא בפרשנות אחרת – בפרט, הטענה $latex \forall x,y(x\cdot y=y\cdot x)$  (שבניסוח מילולי אומרת "החבורה היא אבלית") נכונה עבור שלמים אך לא נכונה עבור מטריצות.

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

בשביל מה כל המשחק הזה טוב? המטרה הסופית שלנו בבניית תורות היא להוכיח בהן משפטים. הנה דוגמה למשפט שאפשר להוכיח בתורת החבורות: "איבר היחידה הוא יחיד", ובניסוח פורמלי: $latex \forall x(\forall y(x\cdot y=y \wedge y\cdot x=y))\rightarrow x=e$. כלומר, אם $latex x$ כלשהו מקיים את התכונה שמגדירה את איבר היחידה, הוא בהכרח שווה לו. קל למדי להוכיח את המשפט הזה רק מתוך האקסיומות שהצגתי לעיל – נסו זאת בתור תרגיל (ההוכחה שלכם לא תהיה פורמלית לגמרי, כי לא אמרתי במפורש מהם כללי ההיסק, אבל אני מניח שהרעיון יהיה ברור). כעת ניתן לקטוף את הפירות – אם הוכחנו משפט כלשהו בתורה שלנו, נובע מכך שהוא נכון לכל המודלים של התורה הזו. כלומר, גם בשלמים וגם במטריצות, איבר היחידה יהיה יחיד. לתכונה הזו – אם בתורה ניתן להוכיח משהו אז הוא נכון בכל מודל של התורה – קוראים "נאותות" של התורה. התכונה הזו כלל לא טריוויאלית – אם נבחר כללי היסק "עקומים", ייתכן שהיא פשוט לא תתקיים. יש צורך להראות שהיא מתקיימת עבור שפות מסדר ראשון עם כללי ההיסק הרגילים (הדבר הזה מכונה "משפט הנאותות"), אבל מן הסתם לא אכנס לכך כעת.

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

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

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

אם כן, איך מגיעים מ"לכל תורה עקבית יש מודל" ל"כל טענה שנכונה בכל מודל של התורה, יכיחה ממנה"? פשוט מאוד. נניח שיש לנו תורה ויש טענה $latex \varphi$ שנכונה בכל מודל של התורה אך אינה יכיחה ממנה; כעת לוקחים את התורה שלנו ומוסיפים לה אקסיומה בודדת – השלילה של הטענה $latex \varphi$. התוצאה שמתקבל היא תורה שהיא עדיין עקבית (זה נובע מכך שלא ניתן להוכיח את $latex \varphi$) ולכן קיים לה מודל; אבל על פי משפט הנאותות שהזכרתי למעלה, כל משפט שניתן להוכיח מהתורה מתקיים באותו המודל, כלומר יש לנו מודל שבו הטענה $latex \varphi$ דווקא לא מתקיימת – סתירה.

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

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

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

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

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

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

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

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

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

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

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

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

  1. פסוט מאוד מעניין. יש לי שאלה קטנה אם אפשר:

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

  2. היא שונה, אבל היא מכילה אותה, ולכן כל מודל שלה הוא בהכרח מודל של התורה המקורית (כי הוא מקיים את כל האקסיומות של התורה החדשה, ולכן בוודאי שמקיים את כל האקסיומות של התורה המקורית).

    אז מצאנו איכשהו מודל לתורה *המקורית*, שהנוסחה פי לא מתקיימת בו.

  3. אח… "צא וחשוב" מסדרת ניצנים… מה שמעלה בי את ההשערה שאתה עוד אחד מהקורבנות של "אני שונא מתמטיקה".

    האם התקבלו תוצאות מעניינות (וברות הסבר להמונים) הנובעות מן ההבדלים בין המודלים של תורת הקבוצות?

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

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

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

  7. גדי,
    מדוע אינך משתמש ב- Math ML עבור הנוסחאות?
    http://www.w3.org/Math/

    נהניתי מהפוסט, כרגיל :-).

    אמור לי, יש מצב לאיזה סדרת פוסטים על תורת המידה והסתברות?

  8. אני לא מכיר את Math ML. האם אפשר להשתמש בה כחלק מ-WordPress? מה היתרונות? שים לב שאני לא כותב את הפוסטים ישירות כאן, אלא בעורך טקסט מתמטי (LyX) ו"ממיר" את הקובץ באופן אוטומטי לפורמט של הבלוג (באמצעות סקריפט שכתבתי, אין משהו ברשת שידוע לי עליו).

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

  9. האם אתה מכיר בלוגים מתמטיים נוספים (אנגלית / עברית) שאתה ממליץ על קריאה בהם כדי להעשיר ידע?
    אולי אפילו כאלה שכן עוסקים בתורת המידה / הסתברות וכו'?

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

    ד"א, חבל שאין לך מייל באתר.

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

    בינתיים אני מרוצה מפתרון הכתיבה הנוכחי שלי כך שאוותר על ההצעה על MathML, אבל תודה.

    בכל הנוגע למייל, דווקא יש – היכנס ל"אודות".

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

    Drazick: נסה את הבלוג של terry tao ואת הבלוג של tim gowers. גם הבלוג של scott aaronson טוב, וגם זה של luca trevisan. ובמיוחד הבלוג של גיל קלעי (כלומר gil kalai). ועוד רבים וטובים. נועם ניסן לאחרונה פתח בלוג. הבלוג של dick lipton מצויין. ואפשר להמשיך. יש משהו שנקרא carnival of mathematics שמשותף לבלוגים מתימטיים רבים, והוא דרך טובה למצוא בלוגים. צא וגגל.

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

  13. פוסט נהדר!

    ורק תיקון קטנטן:

    בהצרנה של הטענה "איבר היחידה הוא יחיד", במקום: "לכל x, אם (xy=y וגם yx=x) אזי x=e", צ"ל:
    "לכל x, אם (לכל y מתקיים (xy=y וגם yx=x)) אזי x=e"
    (דרך אחת להבהיר למה זה צריך להיות ככה, היא ש-y חייב להיות משתנה קשור. הרי הטענות היחידות שניתן להוכיח הן נוסחאות סגורות…)

  14. פינגבאק: מי הזיז את הטור שלי? « לא מדויק

  15. פינגבאק: פרק שלישי, ובו אנחנו נותנים לגופים לנוע, צוללים קצת לתוך המתמטיקה שמ

  16. פינגבאק: משפט ה-PCP או: איך למדתי להפסיק לדאוג ולאהוב הוכחות הניתנות לבדיקה הס

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

    מצטער אם השאלה טריוויאלית.

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

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

    פי נובע משני אלו על פי כלל ההיסק של לוגיקה מסדר ראשון (MP).

  19. פינגבאק: משפטי אי השלמות של גדל – מה הם כן אומרים? « לא מדויק

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

    אני הבנתי את זה נכון?

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

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

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

  24. אני לא יודע בקשר לשאלה על תורת הקבוצות.

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

    https://he.wikipedia.org/wiki/%D7%90%D7%A7%D7%A1%D7%99%D7%95%D7%9E%D7%AA_%D7%94%D7%9E%D7%A7%D7%91%D7%99%D7%9C%D7%99%D7%9D#.D7.AA.D7.9B.D7.95.D7.A0.D7.95.D7.AA_.D7.A9.D7.A7.D7.95.D7.9C.D7.95.D7.AA

  25. הבנתי שניתן להוסיף אקסיומה כי קיימת עוצמה בין א ל-א0 וניתן להוסיף את שלילת… אבל האם כאשר קיימת עוצמה כזו חייבת להיות רק אחת או שניתן שיהיו יותר? יכולות להיות אינסוף עוצמות בינהן? אם לא יכולות להיות יותר ממספר סופי של עוצמות?

    בכל מקרה, תודה רבה על הפוסט, הוא היה מאוד מהנה

כתיבת תגובה

האימייל לא יוצג באתר.