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