ארכיון חודשי: מאי 2009

משפט דיריכילה על סדרות חשבוניות

פורסם בתאריך על ידי
6

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

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

דוגמה לשאלה פשוטה שאפשר לשאול היא "האם יש אינסוף ראשוניים שמשאירים שארית 0 כשמחלקים אותם ב-4?" והתשובה כמובן שלילית, שכן אם השארית היא 0, אז המספר מתחלק ב-4 וודאי שאינו ראשוני. בדומה, שאלה כמו "האם יש אינסוף ראשוניים שמשאירים שארית 2 כשמחלקים אותם ב-4?" היא טיפשית, שכן מספר שמקיים תכונה זו מתחלק בודאות ב-2, ולכן יש רק ראשוני אחד בעל תכונה זו – 2 עצמו. באופן דומה, אין טעם לשאול שאלה בסגנון "האם יש אינסוף ראשוניים שמשאירים שארית \(b\) כשמחלקים אותם ב-\(a\)?" כאשר יש ל-\(a,b\) מחלק משותף גדול מ-1, שכן המחלק המשותף הזה יחלק כל מספר שמשאיר שארית \(b\) כשמחלקים אותו ב-\(a\). אם כן, משויתרנו על המקרה הטריוויאלי הזה, נותר לנו לשאול את עצמנו "האם יש אינסוף ראשוניים שמשאירים שארית \(b\) כשמחלקים אותם ב-\(a\), אם ל-\(a,b\) אין מחלק משותף?" והתשובה המדהימה של דיריכלה היא "כן!". ולא סתם כן – אלא גם שההתפלגות של הראשוניים היא אחידה – במובן מסויים. אם קובעים את \(a\), אז "כמות" הראשוניים שמשאירים שארית \(b\) בחלוקה ב-\(a\), כאשר \(b\) הוא מספר שזר ל-\(a\) וקטן ממנו, היא זהה.

את התיאור לעיל של חלוקה אפשר לנסח גם בלשון של סדרות חשבוניות. נתבונן בסדרה החשבונית שהאיבר הכללי שלה הוא \(an+b\). הטענה היא שבסדרה הזו, אם \(a,b\) זרים (ללא מחלק משותף גדול מ-1), יש אינסוף ראשוניים.

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

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

בתור התחלה, בואו ניזכר במה שאוילר "הראה" (כאמור, מה שאני מראה כאן הוא ניסוח מדוייק יותר של מה שאוילר עשה). ראשית, הגדרנו פונקציה \(\zeta\left(s\right)=\sum_{n=1}^{\infty}\frac{1}{n^{s}}\) עבור ערכים ממשיים \(s>1\) (זהו הבסיס לפונקצית הזטה המפורסמת של רימן). כעת, הראינו שיש לטור הזה גם הצגה "כפלית", שבה באורח פלא הכפל הוא על פני כל המספרים הראשוניים: \(\zeta\left(s\right)=\prod_{p}\frac{1}{1-p^{-s}}\). ההצגה הזו נותנת כפל על פני כל הראשוניים, אבל קל גם לקבל ממנה סכום על פני כל הראשוניים: הצורה הסטנדרטית להפיכת מכפלה לסכום היא הפעלת לוגריתם עליה (זהו אחד משימושיו המקוריים של הלוגריתם: הוא איפשר לבצע פעולות כפל על מספרים גדולים באמצעות פעולות חיבור – זהו הרעיון הבסיסי שמאחורי סרגלי החישוב מנוחתם עדן). ובכן, אחרי שמפעילים לוגריתם ועושים כמה להטוטים (שהבולט בהם הוא שימוש בזהות הקסומה \(-\ln\left(1-x\right)=\sum_{n=1}^{\infty}\frac{x^{n}}{n}\) שתקפה עבור \(\left|x\right|<1\)) מקבלים כי \(\ln\zeta\left(s\right)=\sum_{p}\frac{1}{p^{s}}+O\left(1\right)\). הסימון \(O\left(1\right)\) כאן מציין גודל שאולי משתנה כאשר \(s\) משתנה, אבל חסום על ידי קבוע (לסקרנים: הקבוע הוא \(2\zeta\left(2\right)\)).

כעת, כאשר משאיפים את \(s\) ל-1, הרי ש-\(\zeta\left(s\right)\) שואף לאינסוף (כי כפי שאמרתי בפוסט הקודם, הטור \(\sum_{n=1}^{\infty}\frac{1}{n}\) מתבדר לאינסוף), ולכן גם \(\ln\zeta\left(s\right)\) שואף לאינסוף, ולכן הטור \(\sum_{p}\frac{1}{p^{s}}\) שואף לאינסוף כש-\(s\) שואף ל-1, כלומר \(\sum_{p}\frac{1}{p}\) מתבדר. זוהי ההרחבה המידיית הראשונה של הוכחת אוילר, והיא כבר הייתה ידועה בימי דיריכלה. שימו לב שהתוצאה הזו אינה סתמית כלל ועיקר – היא לא רק מראה שיש אינסוף ראשוניים (כי אם היה מספר סופי, הטור לא היה יכול להתבדר) אלא גם נותנת הערכה מיידית לפיזור שלהם. מכיוון ש-\(\sum_{n=1}^{\infty}\frac{1}{n^{s}}\) מתכנס לכל \(s>1\), מה שמעיד על כך שיש "חורים יחסית גדולים" בין האיברים אותם סוכמים בטור, המסקנה היא שהפיזור של הראשוניים בין המספרים גדול יותר מאשר הפיזור של המספרים מהצורה \(n^{s}\). למשל, אם ניקח \(s=2\), נוכל לומר במדוייק שהפיזור של הראשוניים בין המספרים גדול יותר מאשר הפיזור של המספרים שהם ריבוע – כלומר, אם נעבור מספר מספר ונצעק "בום" כשנראה ראשוני, זה יקרה לעתים יותר קרובות מאשר אם נצעק כשנראה ריבוע. קיימת הערכה טובה בהרבה לפיזור הזה של הראשוניים – היא נקראת "משפט המספרים הראשוניים" ומהווה את התוצאה הקלאסית המרכזית של תורת המספרים האנליטית. לא אכנס לכך כעת.

מה שדיריכלה ניסה לעשות הוא לבנות משוואה דומה ל-\(\ln\zeta\left(s\right)=\sum_{p}\frac{1}{p^{s}}+O\left(1\right)\), כך שבאגף ימין הסכימה תהיה רק על הראשוניים \(p\equiv a\left(q\right)\) עבור \(q,a\) כלשהם שזרים זה לזה, וכך שהפונקציה שבאגף שמאל עדיין תשאף לאינסוף כש-\(s\) שואף ל-1. האתגר הראשון, אם כן, הוא למצוא פונקציות אנליטיות שמבטאות בצורה כלשהי את המושג של "להיות שקול ל-\(a\) מודולו \(q\)". הפונקציות שדיריכלה השתמש בהן נקראות קרקטרים. מבלי להיכנס לתורה הכללית (שניתן לסכמה, למי שמכיר, כך: קרקטר דיריכלה הוא ההרחבה הטבעית ל-\(\mathbb{Z}\)של הומומורפיזם מ-\(\mathbb{Z}_{q}^{*}\) אל \(\mathbb{C}\)), דיריכלה מסתכל על פונקציות \(\chi:\mathbb{Z}\to\mathbb{C}\), כלומר שמקבלות מספר שלם ומחזירות מספר מרוכב, כך שמתקיימות התכונות הבאות:

  1. \(\chi\left(x\right)=\chi\left(x+q\right)\) לכל \(x\in\mathbb{Z}\) (עבור ה-\(q\) הספציפי שלנו).
  2. \(\chi\left(xy\right)=\chi\left(x\right)\chi\left(y\right)\) לכל \(x,y\in\mathbb{Z}\) – לתכונה הזו קוראים "כפליות".
  3. \(\chi\left(x\right)\ne0\) אם ורק אם \(x\) זר ל-\(q\).

התכונות הללו אינן שרירותיות, כמובן; אם נחזור לתיאור שנתתי בסוגריים, 1 ו-3 נובעים מכך ש-\(\chi\) הוא הרחבה של משהו שהוגדר במקור על \(\mathbb{Z}_{q}^{*}\) – אוסף המספרים השלמים הזרים ל-\(q\) – ו-2 נובע מכך שאותו "משהו" הוא הומומורפיזם. כאמור, מי שאינו מכיר את המושגים הללו, לא נורא.

קרקטרים הם יצורים מעניינים וחשובים לכשעצמם, ויש להם תכונות מועילות רבות. למשל, קל לראות מהר מאוד (תוך שימוש בכפליות \(\chi\) ובכך ש-\(\mathbb{Z}_{q}^{*}\) היא חבורה) כי לכל \(x\) שזר ל-\(q\), בהכרח \(\chi\left(x\right)\) יהיה אחד משורשי היחידה מסדר \(q\) – מספר מרוכב שכשהוא מועלה בחזקת \(q\), מתקבל 1. מכאן שלמרות ש-\(\chi\) הוגדר כפונקציה למספרים המרוכבים כולם, למעשה יש מספר קטן מאוד יחסית של ערכים שהוא יכול לקבל. לא אציג את כל הניתוח שאפשר לעשות לאוסף הקרקטרים (שעיקרו במסקנה היפה הבאה: אוסף כל הקרקטרים של חבורה אבלית סופית \(G\) הוא בעצמו חבורה, שאיזומורפית ל-\(G\)) ואדלג למסקנה שנשתמש בה: \(\sum_{\chi}\chi\left(x\right)\overline{\chi\left(y\right)}=\phi\left(q\right)\delta\left(x,y\right)\).

מה הולך כאן? ובכן, מבצעים סכום של איברים מהצורה \(\chi\left(x\right)\overline{\chi\left(y\right)}\) (קו עליון מסמן כאן את הצמוד המרוכב), כאשר \(x,y\) שניהם קבועים, ומה שמשתנה הוא הקרקטר – הסכום הוא על כל הקרקטרים האפשריים מודולו \(q\). התוצאה? אחד משניים. אם \(x\equiv y\left(q\right)\) (\(x\) שקול ל-\(y\) מודולו \(q\)), אז היא \(\phi\left(q\right)\) – פונקצית אוילר, שמתארת כמה מספרים קטנים מ-\(q\) וזרים לו קיימים; אחרת, אם \(x\not\equiv y\left(q\right)\), התוצאה היא 0. זה מה ש-\(\delta\left(x,y\right)\) מסמן – הוא 1 אם \(x\equiv y\left(q\right)\) ואחרת הוא 0 (לדבר כזה קוראים "הדלתא של קרונקר" והוא סימון מקוצר סטנדרטי למדי במתמטיקה. אל תדאגו – קרונקר עשה עוד דברים בחיים).

אם כן, זה הצעד הראשון בכיוון של מה שדיריכלה צריך – סכום של פונקציות שמסוגל "לזהות" מתי שני מספרים הם שקולים מודולו \(q\). הצעד השני הוא לשלב את הקרקטרים הללו בהוכחה המקורית של אוילר. כלומר, לבנות פונקציות שמשלבות את הטוב שבשני העולמות – גם מכילות קרקטרים במובן מסויים, וגם מכילות את פונקצית הזטה של רימן במובן מסויים. השילוב הזה נקרא "פונקציות ה-\(L\) של דיריכלה". פונקצית \(L\) היא פונקציה במשתנה יחיד \(s\), שמוגדרת באמצעות קרקטר דיריכלה כלשהו \(\chi\). ההגדרה של הפונקציה היא \(L_{\chi}\left(s\right)=\sum_{n=1}^{\infty}\frac{\chi\left(n\right)}{n^{s}}\). לצורך ההשוואה, פונקצית הזטה של רימן היא \(\zeta\left(s\right)=\sum_{n=1}^{\infty}\frac{1}{n^{s}}\); כלומר, ההבדל היחיד בינה ובין פונקצית \(L\) של דיריכלה הוא שבמונה לא חייב להיות 1, אלא באופן כללי יש את התוצאה של הפעלת \(\chi\) על הערכים השונים שעליהם רץ \(n\) (וזה, כזכור, יכול להיות שורשי יחידה או 0).

הצעד הראשון בהוכחה המקורית של אוילר הוא מעבר להצגה כפלית של הפונקציה, וזה גם מה שדיריכלה עושה – לא קשה לראות שמתקיים \(L_{\chi}\left(s\right)=\prod_{p}\left(1-\frac{\chi\left(p\right)}{p^{s}}\right)^{-1}\), מאותם שיקולים שפעלו על פונקצית הזטה של רימן, ותוך שימוש חזק בכפליות של \(\chi\). הצעד הבא, כפי שהראיתי בפוסט הזה, הוא לקיחת לוגריתם של שני הצדדים. כאן העלילה מסתבכת – באופן כללי, \(L_{\chi}\left(s\right)\) אינה פונקציה ממשית כי חלק משורשי היחידה שמופיעים בסכום שמגדיר אותה הם מרוכבים. כלומר, זוהי פונקציה מרוכבת, ולפונקציות שכאלו הוצאת לוגריתמים מלווה בסיבוך נוסף. אני הולך לדלג בקלילות מעל החלק הזה (שאינו מיידי) אל התוצאה הסופית – אפשר להראות, במובן מאוד מדוייק וקונקרטי, ש-\(\ln L_{\chi}\left(s\right)=\sum_{p}\frac{\chi\left(p\right)}{p^{s}}+O\left(1\right)\) (הסכום הוא על כל הראשוניים \(p\) שאינם מחלקים את \(q\) – זכרו ש-\(q\) אינו בהכרח ראשוני).

גם התוצאה הזו מאוד מזכירה את מה שכבר ראינו עם פונקצית הזטה – ההבדל היחיד (פרט להוכחה הקשה יותר) הוא בכך ש-\(\chi\left(p\right)\) הצליח להסתנן פנימה. כעת דיריכלה מתחיל לבצע להטוטים במטרה להשתמש בזהות \(\sum_{\chi}\chi\left(x\right)\overline{\chi\left(y\right)}=\phi\left(q\right)\delta\left(x,y\right)\) שראינו קודם – ראשית, הוא מכפיל את שני האגפים של המשוואה ב-\(\overline{\chi\left(a\right)}\) (\(a\) הוא המספר הקבוע שאנו רוצים להראות שיש אינסוף ראשוניים השקולים לו מודולו \(q\)) ומקבל את המשוואה \(\ln L_{\chi}\left(s\right)\overline{\chi\left(a\right)}=\sum_{p}\frac{\chi\left(p\right)\overline{\chi\left(a\right)}}{p^{s}}+O\left(1\right)\). אם כן, התקרבנו לתבנית של \(\chi\left(x\right)\overline{\chi\left(y\right)}\) שרצינו. מה חסר? סכימה על כל ה-\(\chi\). על כן, דיריכלה עובר לשלב הבא: את המשוואה \(\ln L_{\chi}\left(s\right)\overline{\chi\left(a\right)}=\sum_{p}\frac{\chi\left(p\right)\overline{\chi\left(a\right)}}{p^{s}}+O\left(1\right)\) הוא קיבל לכל קרקטר \(\chi\) מודולו \(q\), ולכן אפשר לבצע סכום של כל המשוואות הללו (יש רק מספר סופי של קרקטרים כך שאין כאן שום בעייתיות), ולקבל:

\(\sum_{\chi}\ln L_{\chi}\left(s\right)\overline{\chi\left(a\right)} = \sum_{p}\sum_{\chi}\frac{\chi\left(p\right)\overline{\chi\left(a\right)}}{p^{s}}+O\left(1\right)\)

וכאן השגנו בדיוק את מה שרצינו – סכום על כל הקרקטרים, שלא ייעלם רק כאשר \(p\) שקול ל-\(a\) מודולו \(q\). פורמלית, מקבלים:

\(\sum_{\chi}\ln L_{\chi}\left(s\right)\overline{\chi\left(a\right)} = \sum_{p\equiv a\left(q\right)}\frac{\phi\left(q\right)}{p^{s}}+O\left(1\right)\)

אם כן, באגף ימין יש סכום כלשהו שנלקח על הראשוניים השקולים ל-\(a\) מודולו \(q\); באגף שמאל יש איזו פונקציה מפלצתית. אם נראה שכאשר \(s\) שואף ל-1, המפלצת באגף שמאל שואפת לאינסוף, סיימנו; גם המפלצת באגף ימין חייבת לשאוף לאינסוף, ומכאן שיש אינסוף ראשוניים השקולים ל-\(a\) מודולו \(q\) (למעשה, אפשר לדעת יותר – ה-\(\phi\left(q\right)\) גורר, בסופו של דבר, שהפרופורציה שלהם מכלל הראשוניים היא בדיוק \(\frac{1}{\phi\left(q\right)}\), ומכיוון שיש בדיוק \(\phi\left(q\right)\) מספרים \(a\) שזרים ל-\(q\) וקטנים ממנו, נובע מכך שבכל סדרה חשבונית \(a+nq\) יש "בערך אותה כמות ראשוניים", אבל לא אכנס לזה).

כאן בדיוק נכנס הניתוח האנליטי של פונקציות ה-\(L\) לתמונה. לא קשה להראות (נסו! זה מסתמך על מה שידוע על פונקצית הזטה של רימן) שאם \(\chi\) הוא הקרקטר הטריוויאלי \(\chi_{0}\), זה שנותן 1 לכל ערך שזר ל-\(q\) ו-0 ליתר, אז \(\ln L_{\chi_{0}}\left(s\right)\) שואף לאינסוף כאשר \(s\) שואף ל-1. אם כן, האם סיימנו? לא מיידית; הבעיה היא שאת \(\ln L_{\chi_{0}}\left(s\right)\) מחברים עם עוד הרבה פונקציות \(L\) אחרות; אולי אחרת מהן מתנהגת בדיוק כמו \(L_{\chi_{0}}\left(s\right)\), רק עם סימן הפוך, ולכן היא מבטלת אותה? לכן צריך להראות ש-\(\ln L_{\chi}\left(s\right)\) נשאר חסום כאשר \(s\) שואף ל-1, וזאת לכל \(\chi\) שאיננו טריוויאלי. אולי במפתיע, אבל זהו החלק המורכב ביותר של הוכחת המשפט. לא רק שהניתוח של פונקציות ה-\(L\) הוא טכני למדי, הוא גם מתפצל – ההוכחה שונה לגמרי עבור קרקטר \(\chi\) שיכול לתת ערכים מרוכבים, וקרקטר \(\chi\) שנותן רק ערכים ממשיים (אולי במפתיע, המקרה הראשון הוא דווקא הקל יותר). אולי בעתיד אכתוב פוסט טכני שמתאר את ההוכחה, אך לעת עתה הפוסט הזה טכני דיו.

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

הוכחת אוילר לקיום אינסוף ראשוניים

פורסם בתאריך על ידי
12

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

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

לצורך הבנת ההוכחה צריך להכיר את התיאוריה הבסיסית שמאחורי טורים אינסופיים, שכבר הצגתי כאן פעם ואזכיר בקצרה: ניקח סדרה של מספרים ממשיים שתסומן כ-\(a_{1},a_{2},a_{3},\dots\) (\(a_{1}\) הוא האיבר הראשון, \(a_{2}\) הוא השני וכו'). כעת נסתכל על סכום אברי הסדרה, ובאופן פרטני – סכום \(N\) האיברים הראשונים, מה שמסומן כ-\(S_{N}=\sum_{n=1}^{N}a_{n}\). לסכום הזה קוראים "סכום חלקי" של הסדרה – כלומר, מהסדרה \(a_{1},a_{2},a_{3},\dots\) קיבלנו סדרת סכומים חלקיים \(S_{1},S_{2},S_{3},\dots\). כעת, מגדירים את סכום הסדרה כולה להיות הגבול של סדרת הסכומים החלקיים, כלומר מסמנים \(\sum_{n=1}^{\infty}a_{n}=\lim_{N\to\infty}S_{N}\). לא אציג כאן שוב את ההגדרה הפורמלית ל"גבול" – אינטואיטיבית, אפשר לחשוב עליו בתור מספר שאברי הסדרה הולכים ומתקרבים אליו "עד כמה שנרצה" ככל שמתקדמים בסדרה.

לרוע המזל (או למרבה המזל, כפי שנראה בקרוב) לא עבור כל הטורים סדרת הסכומים החלקיים בכלל מתכנסת, אז לפעמים אין משמעות לביטוי \(\sum_{n=1}^{\infty}a_{n}\) (ואז אומרים שהטור "מתבדר"). עם זאת, יש גם מקרה ביניים חשוב בין טור שמתכנס, וטור ש"ממש לא מתכנס" – ייתכן שהטור אינו מתכנס, אבל סדרת הסכומים החלקיים שלו מפגינה התנהגות ברורה – הסכום הולך וגדל ככל שמחברים עוד איברים, כך שהוא יהיה גדול מכל מספר ממשי שרק נרצה, אם רק נסכום מספיק איברים. על טור כזה אפשר לומר שהוא "מתבדר לאינסוף" ואפילו לסמן \(\sum_{n=1}^{\infty}a_{n}=\infty\).

דוגמה פשוטה לטור שמתכנס לאינסוף הוא הטור שמתקבל מהסדרה שכל איבריה הם 1, כלומר \(1+1+1+\dots\). באותו אופן, כל טור של סדרה קבועה וחיובית מתבדר לאינסוף, ומכך נובע שכל טור שאפשר לחסום את כל האיברים בו מלמטה עם מספר חיובי כלשהו גם כן מתבדר לאינסוף (למשל, הטור \(\sum_{n}\left(1+\frac{1}{n}\right)\) מתבדר לאינסוף כי אפשר לחסום כל אחד מהאיברים שבו מלמטה על ידי 1). לכן מלכתחילה שאלות של התכנסות הן מעניינות רק על טורים שהאיבר הכללי שלהם שואף לאפס; והסדרות הפשוטות ביותר שהאיבר הכללי שלהן שואף לאפס הן מהצורה \(\frac{1}{n^{s}}\), כאשר \(s>0\). אחת מהשאלות הראשונות ששואלים על טורים היא מהם הערכים של \(s\) שעבורם הטור \(\sum_{n=1}^{\infty}\frac{1}{n^{s}}\) מתכנס למספר סופי. התשובה היא אולי מפתיעה למדי במבט ראשון: אם \(s>1\), הטור מתכנס; ואילו אם \(s\le1\) הטור אינו מתכנס (כלומר, הוא מתבדר לאינסוף). מכאן שהנקודה \(s=1\), שמניבה את הטור \(\sum_{n=1}^{\infty}\frac{1}{n}\) (שנקרא "הטור ההרמוני") היא מעין נקודת גבול בין המתכנס והמתבדר. זה בדיוק המחקר של נקודת הגבול הזו שמוביל לתוצאות שאני רוצה לדבר עליהן.

לפני כן, סימון: אמרתי שעבור כל \(s>1\) הטור \(\sum_{n=1}^{\infty}\frac{1}{n^{s}}\) מתכנס, כלומר קיים מספר ששווה לסכום הטור הזה. לכל \(s\) נקבל מספר אחר – למשל, עבור \(s=2\) מקבלים \(\frac{\pi^{2}}{6}\) ועבור \(s=4\) מקבלים \(\frac{\pi^{4}}{90}\). באופן כללי זה קשה לחשב במדוייק את הערכים שמקבלים לכל ה-\(s\)-ים; את הערכים שכתבתי כאן ניתן לקבל באמצעות כמה תעלולים נחמדים שמתבססים על אנליזת פורייה – זה נושא לפוסט נפרד – אך שלא ניתן להשתמש בהם עבור רוב הערכים האפשריים של \(s\). בכל זאת, אין מניעה מלהגדיר פונקציה שמקבלת \(s\) ומחזירה את הערך המתאים: \(\zeta\left(s\right)=\sum_{n=1}^{\infty}\frac{1}{n^{s}}\). הפונקציה הזו היא הבסיס של "פונקצית הזטא של רימן" המפורסמת. למה רק הבסיס? כי את הפונקציה "שלי" הגדרתי רק על ערכים ממשיים שמקיימים \(s>1\), בעוד שפונקצית הזטא של רימן מוגדרת לכל מספר מרוכב (אך היא מזדהה עם הפונקציה "שלי" על המספרים הממשיים שמקיימים \(s>1\)) פרט למספר \(s=1\), שבו הפונקציה "מתפוצצת" (נקודה שכזו נקראת "קוטב", ובתורת הפונקציות המרוכבות מתייחסים גם אליה בתור נקודה שבה הפונקציה מוגדרת, אך לא אכנס לזה כעת).

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

נתחיל מתזכורת מבית הספר: טור הנדסי הוא טור מהצורה \(\sum_{n=0}^{\infty}a_{0}q^{n}\) עבור \(q\) ממשי כלשהו. למשל, \(1+2+4+8+16+\dots\) הוא טור הנדסי שכזה. תוצאה בסיסית בחשבון אינפיניטסימלי מראה כי אם \(\left|q\right|<1\), אז סכום הטור הזה הוא \(\frac{a_{0}}{1-q}\) (אם \(\left|q\right|\ge1\) הטור מתבדר). בפרט, אם ניקח מספר ראשוני \(p\) כלשהו, הרי שלכתוב \(\frac{1}{1-p^{-1}}\) יהיה אותו הדבר בדיוק כמו לכתוב \(1+p^{-1}+p^{-2}+p^{-3}+\dots\).

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

מה יקרה אם נגדיל את מספר האיברים בכל סוגר? או שנגדיל את מספר הסוגריים? הרעיון יישאר אותו רעיון – נקבל סכום של איברים, שבו כל איבר הוא מכפלה של איבר מכל סוגר. ומה יקרה אם הסכום שיש בכל סוגר הוא אינסופי? אז נקבל סכום שגם הוא אינסופי, אבל אנחנו יודעים בדיוק מי הם אבריו; אנסה לתת לכך דוגמה. נניח ש-\(p,q\) הם ראשוניים, ונתבונן במכפלה \(\left(1+p^{-1}+p^{-2}+\dots\right)\left(1+q^{-1}+q^{-2}+\dots\right)\). מהדיון הקודם ברור שכשנפתח את המכפלה, נקבל סכום של איברים, כך שכל איבר הוא מהצורה \(p^{-i}q^{-j}\) עבור \(i,j\) טבעיים כלשהם (כולל אפס). עד כאן הכל בסדר? אז בואו רק נשים לב לכך שניתן להציג את המכפלה של שני הסכומים הללו בדרך קומפקטית יותר: \(\left(\frac{1}{1-p^{-1}}\right)\left(\frac{1}{1-q^{-1}}\right)\).

כעת אוילר לוקח את הרעיון הזה לשלב הבא – מה יקרה אם נכפול זה בזה לא רק שניים, אלא מספר אינסופי של סכומים? אז נקבל סכום אינסופי, שכל איבר בו הוא בעצמו מכפלה אינסופית. מבלבל? אז בואו נראה את זה בעיניים. מה שאוילר מציע לעשות הוא להתבונן במכפלה \(\prod_{i=1}^{\infty}\left(1+p_{i}^{-1}+p_{i}^{-2}+\dots\right)\) (הסימן \(\prod\) מציין מכפלה מקוצרת, בדומה לסימן \(\sum\) המציין סכום), כך ש-\(p_{i}\) הוא הראשוני ה-\(i\) במספר בסדרת הראשוניים (כלומר, \(p_{1}=2,p_{2}=3,p_{3}=5\) וכו'). אם נפתח את המכפלה הזו, נקבל סכום של איברים, כך שכל איבר הוא מהצורה \(\prod_{i=1}^{\infty}p^{-k_{i}}\), כאשר \(-k_{i}\) הוא החזקה ש"בחרנו" עבור הראשוני ה-\(i\) במכפלה.

שימו לב שאם \(k_{i}>0\) אז \(p^{-k_{i}}<1\). לא קשה להראות שמכפלה של אינסוף איברים שקטנים מ-1 שואפת לאפס, ולכן רוב האיברים בסכום נעלמים – היחידים ששורדים הם אלו שמהווים מכפלה של ראשוניים כך שהחל ממקום מסויים במכפלה, כל החזקות \(k_{i}\) שנבחרו הם 0. למשל: \(2^{-1}\cdot3^{0}\cdot5^{0}\cdot7^{0}\cdots=2^{-1}\). מכאן שכל איבר בסכום, בסופו של דבר, יהיה ניתן לתיאור בתור \(\prod_{i=1}^{n}p^{-k_{i}}\) עבור \(n\) סופי כלשהו (לאיברים אחרים יהיו \(n\)-ים אחרים). למעשה, אפשר להוציא את המינוס החוצה, ולקבל שהאיבר יהיה מהצורה \(\left(\prod_{i=1}^{n}p^{k_{i}}\right)^{-1}\). אם כן, כדי להבין את המכפלה \(\prod_{i=1}^{\infty}\left(1+p_{i}^{-1}+p_{i}^{-2}+\dots\right)\) מספיק להבין מהם האיברים מהצורה \(\prod_{i=1}^{n}p^{k_{i}}\) – אבל מה הם באמת? הם בדיוק כל המספרים הטבעיים, וכל אחד מהם מופיע בדיוק פעם אחת, כי לכל מספר פירוק יחיד לגורמים כמכפלה של ראשוניים (מכפלה שניתן לחשוב עליה כמכפלת כל אינסוף הראשוניים, בתנאי שכולם פרט למספר סופי הם בעלי החזקה 0). זה לב לבו של העניין – כאן נכנס המשפט היסודי של האריתמטיקה לתמונה.

את כל הדיון הזה אפשר לצמצם לכדי הנוסחה הבאה: \(\prod_{p}\frac{1}{1-p^{-1}} = \sum_{n=1}^{\infty}\frac{1}{n}\)

המכפלה שבאגף שמאל היא המכפלה שעליה דיברנו, כשהיא נלקחת על כל הראשוניים (השימוש ב-\(p\) באינדקס, כדי לציין "האינדקס רץ על פני כל המספרים הראשוניים" הוא סטנדרטי ומקובל), בהצגה הקומפקטית שבה \(1+p_{i}^{-1}+p_{i}^{-2}+\dots\) מוצג בתור \(\frac{1}{1-p^{-1}}\). באגף ימין יש לנו את סכום כל האיברים ש"שרדו", שכאמור הם בדיוק כל הטבעיים, בחזקת המינוס 1 שהוצאנו החוצה. כלומר, אפשר להציג את הטור ההרמוני בתור מכפלה – ולא סתם מכפלה, כזו שנלקחת בדיוק על המספרים הראשוניים.

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

לרוע המזל, מבחינה מתמטית מדוייקת ביצעתי כמה וכמה חיפופים ועיגולי פינות (אני בטוח שחלקכם שמו אליהם לב). מבלי להיכנס במדויק לשאלה מה לא בסדר, אציג את התיקון – במקום לשאול את עצמנו מה קורה בנקודה \(s=1\) הבעייתית של פונקציית הזטא, מסתכלים על ערכים \(s>1\), ועבורם מוכיחים את המשוואה הבאה:

\(\zeta\left(s\right) = \sum_{n=1}^{\infty}\frac{1}{n^{s}}=\prod_{p}\frac{1}{1-p^{-s}}\)

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

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

משפט אי השלמות הראשון של גדל – איך (בערך) מוכיחים אותו?

פורסם בתאריך על ידי
21

הקדמה

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

מספור גדל

הבה ונזכור מהי הוכחה – סדרה של טענות, כשכל טענה היא סדרה של תווים מעל אלף-בית כלשהו של סימנים. לא כל סדרת תווים היא חוקית – יש כללים שקובעים אילו סדרות הן חוקיות (לסדרות כאלו, שמהוות טענה חוקית, לפעמים קוראים "Well formed formula" ומייד מקצרים ל-wff והופכים את יתר הטקסט לבלתי קריא) ואילו לא. מה שגדל מציע הוא לקודד כל טענה באמצעות מספר באופן הבא: ראשית, לכל תו באלף-בית נצמיד מספר טבעי – כך למשל "\(\wedge\)" שמסמל "וגם" יכול לקבל את המספר 3, בעוד "\(x\)" שהוא משתנה יכול לקבל 5 (יש אינסוף משתנים, אבל זו לא בעיה – כל משתנה יקבל מספר אחר. באופן כללי, אם \(t\) הוא סימן כלשהו, אז \(g\left(t\right)\) יהיה הערך שגדל מתאים לו.

עכשיו, בהינתן פסוק, למשל \(x\wedge\neg z\), אפשר להתאים לו מספר באופן הבא: \(2^{g\left(x\right)}\cdot3^{g\left(\wedge\right)}\cdot5^{g\left(\neg\right)}\cdot7^{g\left(z\right)}\). כלומר, המספר שמותאם לפסוק הוא מכפלה של ראשוניים, כאשר החזקה של הראשוני ה-\(k\)-י במכפלה היא הערך המספרי שהותאם לתו ה-\(k\)-י באותו פסוק. השימוש בראשוניים נובע מכך שלכל מספר יש פירוק יחיד לראשוניים, כך שלא ייתכן ששתי מכפלות שונות של ראשוניים יתנו את אותו מספר, ולכן כל פסוק מקודד באופן ייחודי.

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

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

פונקציות רקורסיביות

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

באופן כללי, הדיון עוסק בפונקציות מהמספרים הטבעיים לטבעיים. כדי להקל על החיים, מרשים לפונקציה לקבל ולהחזיר סדרות סופיות של טבעיים, כלומר באופן כללי אנחנו מדברים על פונקציה \(f:\mathbb{N}^{n}\to\mathbb{N}^{m}\). ההגיון הוא שכל דבר שניתן לחישוב ניתן לתאר (באמצעות קידוד מתאים) כחישוב על טבעיים – ואכן, זה גם מה שגדל עושה – מתרגם פונקציות על טענות והוכחות (למשל, פונקציה שמחזירה 1 רק אם הוכחה מסויימת היא תקפה) לפונקציות על מספרים טבעיים.

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

  1. הפונקציה הקבועה אפס: \(f\left(x_{1},\dots,x_{n}\right)=0\) (לכל\(n\) טבעי, כלומר \(f\left(x\right)=0\), וגם \(f\left(x_{1},x_{2}\right)=0\) וכו').
  2. פונקצית העוקב: \(g\left(x\right)=x+1\).
  3. פונקצית ההטלה על הרכיב ה-\(i\): \(h_{i}\left(x_{1},\dots,x_{n}\right)=x_{i}\)

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

דרך אחת לבנות פונקציות חדשות מהישנות היא הרכבה. הניסוח הפורמלי מעט מסורבל, ולכן קודם כל דוגמה למקרה פשוט: אם יש לנו שתי פונקציות רקורסיביות,\(f\left(x\right),g\left(x\right)\), אז אפשר לבנות פונקציה חדשה שמסמלת קודם כל הפעלה של \(g\) ואחרי הפעלה של \(f\). בכתיבה פורמלית,\(h\left(x\right)=f\left(g\left(x\right)\right)\). די בבירור אם\(f,g\) ניתנות לחישוב, גם \(h\) ניתנת לחישוב (קודם כל מחשבים את \(g\left(x\right)\), ואז מחשבים מה \(f\) מחזיר על התוצאה).

באופן כללי הניסוח מסורבל מעט יותר, כאמור: אם \(g_{1}\dots g_{n}\) כולן פונקציות רקורסיביות ב-\(m\) משתנים, ו-\(f\) היא פונקציה ב-\(n\) משתנים, אז אפשר להגדיר כך פונקציה \(h\) מ-\(m\):\(h\left(x_{1},\dots,x_{m}\right)=f\left(g_{1}\left(x_{1},\dots,x_{m}\right),\dots,g_{n}\left(x_{1},\dots,x_{m}\right)\right)\).

הבניה המרכזית והמעניינת ביותר, שנתנה לפונקציות את שמן, היא הרקורסיה. במשמעות ה"רגילה" של המילה, פונקציה רקורסיבית היא כזו שמוגדרת באמצעות עצמה, אך על קלט פשוט יותר. למשל, \(f\left(n\right)=f\left(n-1\right)+f\left(n-2\right)\) היא פונקציה רקורסיבית (שמגדירה את מספר פיבונאצ'י ה-\(n\)-י) כדי שיהיה טעם ברקורסיה, חייבים להיות מוגדרים לה "תנאי עצירה" – הגדרה מפורשת של ערכיה כאשר הקלט קטן דיו. עבור פיבונאצ'י, למשל, הגדרה אפשרית אחת היא \(f\left(0\right)=0,f\left(1\right)=1\).

פורמלית, פעולת הרקורסיה מוגדרת כך. נניח שיש לנו פונקציה רקורסיבית (במובן של "ניתנת לחישוב") \(f\left(y,z,x_{1},\dots,x_{n}\right)\) ופונקציה רקורסיבית \(g\left(x_{1},\dots,x_{n}\right)\) (זוהי הפונקציה של "תנאי ההתחלה"), אז אפשר להגדיר פונקציה רקורסיבית חדשה \(h\left(y,x_{1},\dots,x_{n}\right)\) באופן הבא:

\(h\left(0,x_{1},\dots,x_{n}\right) = g\left(x_{1},\dots,x_{n}\right) = h\left(n+1,x_{1},\dots,x_{n}\right) = f\left(n,h\left(n,x_{1},\dots,x_{n}\right),x_{1},\dots,x_{n}\right)\)

אם כן, \(h\left(n,x_{1},\dots,x_{n}\right)\) פירושו "\(h\) עבור הערך \(n\) והפרמטרים הקבועים \(x_{1},\dots,x_{n}\)". כאשר הערך \(n=0\), אז \(h\) פשוט מחזירה את תנאי ההתחלה, וכאשר הוא גדול יותר מחזירים את מה ש-\(f\) נותנת, שמתבסס על \(n\), על \(x_{1},\dots,x_{n}\), ועל הערך הקטן יותר של \(h\).

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

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

בזמנו של גדל, כמובן, כל זה לא היה ידוע. זו הסיבה שבגללה השלב הבא בהוכחה שלו הוא כל כך טכני ומורכב. מה שגדל רוצה לעשות כעת הוא לבנות פונקציה רקורסיבית \(B\left(x,y\right)\) שמחזירה 1 אם המספר הטבעי \(x\) הוא קידוד של הוכחה עבור הטענה שמקודדת על ידי המספר\(y\) (למעשה, גדל מגדיר יחס ולא פונקציה, אך שני המושגים שקולים זה לזה ולא אתעמק בהבחנה הזו). אם אנחנו יודעים שקיימת פונקציה רקורסיבית עבור כל תוכנית מחשב, הקיום של \(B\) אינו מפתיע במיוחד – בהינתן \(x,y\), זה עניין טכני ומכני בלבד לפענח את הקידוד של \(x\) ולקבל סדרה של טענות, ואז זה עניין טכני ומכני בלבד לבדוק שכל טענה בסדרה היא או אקסיומה או נובעת מקודמותיה, ושהפסוק האחרון בסדרה הוא מה ש-\(y\) מקודד; זה בדיוק המקום שבו נדרש ממערכת ההוכחה להיות אפקטיבית, כך שבדיקה שכזו תהיה אפשרית בכלל – אם המערכת לא הייתה אפקטיבית, ככל הנראה הפונקציה\(B\) המדוברת לא הייתה רקורסיבית (כמובן, עדיין ניתן היה להגדיר את \(B\) באופן מילולי; פשוט לא היינו יכולים לעשות בה את השימוש שגדל עושה אחר כך, ומצריך ממנה להיות רקורסיבית).

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

ייצוג הפונקציות הרקורסיביות

אוקיי, אז גדל הראה שאותה \(B\left(x,y\right)\) היא רקורסיבית. מה עכשיו? כעת גדל מגיע לפאנץ' ליין של השימוש בפונקציות רקורסיביות – הוא מראה שבתורה שאותה הוא "תוקף", אפשר לייצג את הפונקציות הללו. המשמעות המדוייק של הייצוג הזה היא מעט טכנית ולא אכנס אליה, ולכן לצורך העניין ניתן לחשוב על כך (באופן לא מדוייק לגמרי) כאילו ניתן להשתמש בפונקציות רקורסיביות בצורה חופשית בפסוקים של התורה, כאילו הן היו חלק מהשפה עצמה. גדל אמנם מראה זאת רק עבור תורה ספציפית – זו של ראסל וויטהד - אבל בהמשך הוא מראה כי די בפעולות החיבור והכפל ה"סטנדרטיות": כדי שאפשר יהיה להגדיר את הפונקציות הרקורסיביות. זו נקודה מעניינת, ולכן אני רוצה להתעכב גם עליה.

פונקציה רקורסיבית בסיסית, כמו \(f\left(x\right)=0\) קל לייצג, כי יש לנו סימן עבור 0 בשפה; ובדומה, גם \(f\left(x\right)=x+1\) קל לייצוג כי יש לנו בשפה סימן עבור עוקב. גם הטלות והרכבות לא קשה לייצג – האתגר האמיתי הוא פעולת הרקורסיה (שהיא, כאמור, הפעולה עם ה"בשר" כאן). בנפנוף ידיים, מה שצריך לעשות כדי לייצג פונקציה שנבנתה ברקורסיה, הוא לבנות פסוק שאומר "קיימת סדרת ערכים, כך שהערך הראשון מתקבל מבסיס הרקורסיה, וכל ערך גדול יותר מתקבל מקודמו על ידי הפעלת פונקצית הרקורסיה, והערך האחרון הוא הפלט של הפונקציה" (קצת מזכיר הוכחה פורמלית, לא?). האתגר שבבניית פסוק שכזה הוא בדיוק בטענת ה"קיימת סדרה" – הרי בלוגיקה מסדר ראשון אין דרך לכמת קבוצות של איברים, וסדרה היא קבוצה שכזו. כל מה שניתן לעשות הוא לטעון טענות "קיים מספר", לא "קיימת סדרת מספרים". אז איך עוקפים את זה?

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

אם כן, סיכום ביניים: גדל משתמש בפונקצית ה-\(\beta\) כדי להראות שכל הפונקציות הרקורסיביות ניתנות לייצוג בכל תורה אריתמטית. הוא כבר הראה שבכל תורה אפקטיבית, הפונקציה \(B\left(x,y\right)\) של "\(x\) היא הוכחה ל-\(y\)" היא רקורסיבית. משני אלו עולה שהיא ניתנת לייצוג בתורה שהיא אריתמטית ואפקטיבית. כעת הגענו לישורת האחרונה.

שובו של האלכסון

החלקים הטכניים של ההוכחה כבר פחות או יותר מאחורינו – כל מה שנותר הוא רעיון חדש אחד או שניים, שניתנים להבנה גם עבור מי שלא בקיא בפרטים הקטנים של מה שהלך עד כה. ראשית כל ננסה לתת את המוטביציה להגדרה החדשה. יש לנו כבר יכולת לומר "\(x\) הוא הוכחה ל-\(y\)" והיינו רוצים לבנות פסוק \(G\) שאומר "אין הוכחה עבורי". כעת, כל נוסחה \(\varphi\) מיוצגת, כזכור, על ידי מספר – זהו מספור גדל המדובר. נסמן את המספר הזה בתור \(\left|\varphi\right|\). אם כן, מדוע לא לבנות את הפסוק הבא: \(G=\forall x\left(\neg B\left(x,\left|G\right|\right)\right)\)? כלומר, \(G\) הוא הפסוק שאומר "לא קיים \(x\) שהוא הוכחה עבורי" – זה יסיים את העניין.

לרוע המזל, ההפניה העצמית שאנו כל כך אוהבים פונה כאן כנגדנו. שימו לב איך הגדרתי את הפסוק \(G\): חלק ממנו הוא \(\left|G\right|\), שהוא מספר טבעי שמיוצג בתורה שלנו באמצעות הפעלות חוזרות ונשנות של פונקצית העוקב על 0 – כלומר, זו מחרוזת ארוכה ומסובכת. מצד שני, הערך המספרי שאותה מחרוזת מייצגת הוא משהו שכדי לחשב אותו עלינו כבר לדעת את כל הנוסחה \(G\); במילים אחרות, ההגדרה שלנו היא מעגלית – כל עוד לא כתבנו במפורש את \(G\) אין משמעות ל-\(\left|G\right|\), אבל מבלי שתהיה משמעות ל-\(\left|G\right|\) אי אפשר לכתוב את \(G\)! בקיצור, נתקענו, ואנו זקוקים לתעלול כדי לפתור את הבעיה. תעלול שכזה הוא בדיוק מה שגדל מספק; בסופו של דבר הוא יאפשר, בצורה עקיפה, להציב את \(\left|G\right|\) בתוך \(G\).

ראשית, בואו נבהיר הגדרה חשובה אחת: "פסוק" פירושו של דבר שאין בו משתנים שאינם נופלים תחת כמת כלשהו. למשל, \(\varphi=\forall x,y\left(x+y=y+x\right)\) הוא פסוק; לעומת זאת, \(\varphi^{\prime}=x+y>0\) אינו פסוק. ההבדל מהותי: ל-\(\varphi\) יש ערך אמת מוגדר, או שהוא נכון, או שלא. לעומת זאת, ערך האמת של \(\varphi^{\prime}\) תלוי בערכים הספציפיים של\(x,y\) ש"נציב" בו.

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

דוגמה טיפשית: נניח ש-\(\varphi=\exists x\left(y>x\wedge2\cdot y<x\right)\). נניח שאחרי חישובים קשים מצאנו כי \(\left|\varphi\right|=1231\) (מספר מפוברק, כמובן). אז \(\varphi\left(\left|\varphi\right|\right)=\exists x\left(1231>x\wedge2\cdot1231<x\right)\), וזהו פסוק שיש לו או ערך אמת, או ערך שקר. כאן אנחנו מתחילים לראות את ההתייחסות העצמית המדוברת של משפט גדל – אפשר לשאול את \(\varphi\)"מה אתה אומר על עצמך?". אלן טיורינג ישתמש בדיוק ברעיון הזה מספר שנים לאחר מכן, ולא במקרה, אלא בהשראת הרעיון הזה של גדל.

מה בעצם משמעות המילה "לכסון" כאן? הנה אינטואיציה. חשבו על טבלה שבה לכל נוסחה במשתנה אחד \(\varphi\left(y\right)\) יש שורה, ולכל מספר טבעי שמתאים לנוסחה שכזו יש עמודה. בעמודה \(n\) בשורה של \(\varphi\) יהיה 1 אם \(\varphi\left(n\right)\) מקבל ערך אמת, ו-0 אחרת. כעת, אם נסדר את הנוסחאות \(\varphi\) על פי סדר הגודל של מספרי גדל שלהם, הרי שהערכים של \(\varphi\left(\left|\varphi\right|\right)\) יהיו בדיוק האלכסון של הטבלה.

כאמור, גם הלכסון של \(\varphi\) הוא נוסחה, ולכן יש לו מספר גדל משל עצמו. זה פותח פתח להגדרת הפונקציה הבאה: \(diag\left(n\right)=k\) אם \(k\) הוא מספר גדל של הלכסון של הנוסחה \(\varphi\) שעבורה \(\left|\varphi\right|=n\). כלומר, אם נתנו לנו \(n\) אנחנו "מפענחים" את הנוסחה \(\varphi\) שהוא מקודד, כותבים פורמלית את הנוסחה \(\varphi\left(\left|\varphi\right|\right)\) (שכאמור, שונה פיזית מהנוסחה \(\varphi\left(y\right)\) – סדרת הסמלים שמרכיבים אותה שונה, ולכן מספר גדל שלה יהיה שונה), מקודדים אותה בחזרה ומוציאים כפלט את המספר. ההסבר הזה הוא גם "אלגוריתם" לחישוב הפונקציה, ומכאן שהיא פונקציה רקורסיבית, ומכאן שהיא ניתנת לייצוג בתורה. בזאת סיימנו לדבר על הכלי החזק ביותר שבו נשתמש.

כעת נקשור את שני הרעיונות המרכזיים של גדל – הלכסון, והפונקציה \(B\left(x,y\right)\). נגדיר את הנוסחה הבאה: \(U\left(y\right)=\forall x\neg B\left(x,diag\left(y\right)\right)\). הנוסחה הזו אומרת "לא קיימת הוכחה לפסוק שמיוצג על ידי המספר\(diag\left(y\right)\)". אנחנו כבר ממש ממש שם, נשארה רק עוד הגדרה אחת, אחרונה, שהיא הטוויסט הסופי – מה שמקבלים כאשר מלכסנים את \(U\) עצמה.

אם כן, נגדיר \(G=U\left(\left|U\right|\right)\). הנוסחה \(G\) הזו היא היעד הסופי שלנו – זה הפסוק שאינו ניתן להוכחה ועם זאת הוא נכון. ראשית, ברור שמדובר בפסוק, כי אין בו משתנים חופשיים. שנית, מה בעצם הוא אומר? הפסוק מקבל ערך אמת אם ורק אם הערך של \(U\) על \(\left|U\right|\) הוא אמת; אבל \(U\) מקבל ערך אמת על \(\left|U\right|\) אם ורק אם לא קיימת הוכחה לפסוק שמיוצג על ידי המספר \(diag\left(\left|U\right|\right)\). אבל מה זה הפסוק הזה? נזכר בהגדרה: \(diag\left(\left|U\right|\right)\) הוא מספר גדל של הלכסון של \(U\), כלומר של הפסוק \(G=U\left(\left|U\right|\right)\). כלומר, בסיכומו של דבר קיבלנו ש-\(G\) מקבל ערך אמת אם ורק אם לא קיימת הוכחה לפסוק שמיוצג על ידי \(G\) – זהו הניסוח הפחות או יותר מדוייק לתיאור האינטואיטיבי של "\(G\) אומרת שאין לה הוכחה".

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

מה עוד נשאר?

למרות שבנינו את \(G\), עדיין לא סיימנו. הטיעון שנתתי לעיל, של "\(G\) אומרת שאין לה הוכחה" הוא טיעון בנפנופי ידיים – טיעון "סמנטי" שמתבסס על המשמעות שאני מייחס ל-\(G\). עבור הוכחה פורמלית צריך להראות ממש שלא ניתן להוכיח את \(G\). בסימון פורמלי, \(\vdash\varphi\) אומר "ניתן להוכיח את \(\varphi\)". אם כן, אנו רוצים להראות כי \(\not\vdash G\). נניח אם כן כי \(\vdash G\); כלומר, קיימת הוכחה של \(G\) במערכת שלנו, ולכן לאותה הוכחה קיים מספר גדל כלשהו, נניח \(m\); מכאן שמתקיים \(B\left(m,\left|G\right|\right)\), כלומר מתקיים \(B\left(m,diag\left(\left|U\right|\right)\right)\) (כל זה – על פי ההגדרות). כעת, לא ממש הסברתי עד הסוף מה זה אומר ש-\(B\)"מיוצגת" בתורה שלנו, אבל אחת מההשלכות של ה"ייצוג" הזה הוא שמתקיים \(\vdash B\left(m,diag\left(\left|U\right|\right)\right)\).

מצד שני, \(G=\forall x\neg B\left(x,diag\left(\left|U\right|\right)\right)\) על פי הבניה שלנו, ולכן \(\vdash\forall x\neg B\left(x,diag\left(\left|U\right|\right)\right)\); מכללי ההיסק הסטנדרטיים נובע ש-\(\vdash\neg B\left(m,diag\left(\left|U\right|\right)\right)\) (אם ניתן להוכיח שזה קורה לכל \(x\), ניתן להוכיח שזה קורה ספציפתי עבור \(x=m\)). לכן קיבלנו שהמערכת שלנו מוכיחה משפט ושלילתו – סתירה לכך שהיא עקבית.

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

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

משפטי אי השלמות של גדל – מה הם כן אומרים?

פורסם בתאריך על ידי
18

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

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

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

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

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

את המשמעות של תורות מספקים המודלים שלהן. מודל (בנפנוף ידיים פרוע) הוא קבוצה של אובייקטים מתמטיים שמותאמים לסמלים שבשפה ונותנים להם פרשנות אפשרית אחת (בדוגמה של הפוסט הקודם הבאתי את תורת החבורות, שבה הסימן \(\cdot\) שמסמן את פעולת החבורה יכול לקבל פרשנות של "חיבור מספרים שלמים" ופרשנות אחרת של "כפל מטריצות"). מכיוון שמודל הוא יצור "אמיתי", אפשר לשאול את עצמנו האם טענות שמנוסחות בשפה הפורמלית אכן מתקיימות בפרשנות שמציע המודל (בפוסט הקודם הדוגמה הייתה הטענה הפורמלית \(\forall x,y\left(x\cdot y=y\cdot x\right)\) שהייתה נכונה בפרשנות של "מספרים שלמים" אך לא נכונה בפרשנות של "מטריצות"). כדי שמשהו יהיה מודל עבור תורה מסויימת צריך, מן הסתם, שהאקסיומות של התורה יהיו נכונות עבורו.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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