משפט קנטור
מסקנות והשלכות > שיטת האלכסון

הוכחת משפט קנטור יחד עם טיעון האלכסון של קנטור שהוצג לצדה הולידו שיטה כללית להוכחת טענות המשמשת בתחומים רבים במתמטיקה. השיטה נקראת אלכסון, והיא משמשת בעיקר במדעי המחשב ובלוגיקה מתמטית.
הרעיון הכללי בשיטת האלכסון הוא לבנות אובייקט מתמטי קביל המתייחס לעצמו באופן עקיף. אופי ההתייחסות תלוי בטענה שאותה רוצים להוכיח. הוכחה כללית בשיטה זו בנויה כך: בהינתן אוסף של איברים  \Lambda  ואוסף של אובייקטים מהצורה  \phi _{\alpha }, לכל  \alpha \in \Lambda . נניח שכל אובייקט  \phi _{\alpha } פועל בצורה כלשהי על איברי  \Lambda . נסמן את הפעולה של  \phi _{\alpha } על  \beta \in \Lambda  כ- \phi _{\alpha }(\beta ) (ניתן לחשוב על  \phi _{\alpha } כפונקציה של איברי  \Lambda ). מגדירים אובייקט  \phi _{D} שנקרא ה"אלכסון", כך שתוצאת הפעולה  \phi _{D}(\beta ) נקבעת על פי תוצאת הפעולה  \phi _{\beta }(\beta ). אם קיים  \gamma \in \Lambda  כך ש- \phi _{\gamma }=\phi _{D}, אז הכרח שהוא מתייחס לעצמו, שכן לפי ההגדרה,  \phi _{D}(\gamma ) נקבע על פי  \phi _{\gamma }(\gamma ), כלומר על פי עצמו.
השם "אלכסון" מקורו בהמחשה הוויזואלית של שיטת ההוכחה, כפי שהיא מודגמת בטיעון האלכסון של קנטור. הרעיון הוא לדמיין טבלה (אינסופית לרוב) שכל שורה בה מייצגת איבר  \alpha  וכל עמודה בה מייצגת אובייקט  \phi _{\alpha } (באותו הסדר). בהצטלבות בין השורה של  \beta  לעמודה של  \phi _{\alpha } מופיע  \phi _{\alpha }(\beta ). אובייקט ה"אלכסון"  \phi _{D} נבנה על סמך התאים בטבלה שהם מהצורה  \phi _{\beta }(\beta ), שמסודרים בקו אלכסוני לאורך ורוחב הטבלה.
להלן דוגמאות חשובות להוכחה בשיטת האלכסון:
הוכחת משפט קנטור היא מקרה כללי של הוכחה בשיטת האלכסון. נדגים זאת עם נוסח ההוכחה לפונקציות מציינות, שנוח יותר לשימוש במקרה הזה. האוסף  \Lambda  הוא הקבוצה  A. מניחים בשלילה כי לכל פונקציה מציינת של  A ניתן להתאים איבר של  A. האובייקט  \phi _{\alpha } הוא הפונקציה המציינת שהותאמה לאיבר  \alpha \in A. הפעולה  \phi _{\alpha }(\beta ) היא פשוט הפעולה הרגילה של הפונקציה  \phi _{\alpha } על האיבר  \beta . אובייקט האלכסון  \phi _{D} הוא פונקציה מציינת כך ש- \phi _{D}(\beta ) מוגדר כהיפך מ- \phi _{\beta }(\beta ) (0 אם הוא 1, ו-1 אם הוא 0). לפי ההנחה קיים  \gamma \in A כך ש- \phi _{\gamma }=\phi _{D}, ולכן  \phi _{\gamma }(\gamma )\neq \phi _{D}(\gamma )=\phi _{\gamma }(\gamma ). זוהי סתירה, ולכן ההנחה שגויה ומשפט קנטור נכון.
כאמור, אלן טיורינג הוכיח בלכסון כי בעיית העצירה אינה ניתנת להכרעה. כלומר לא קיימת תוכנית מחשב שבהינתן כל תוכנית מחשב וקלט אפשרי, תכריע האם התוכנית הנתונה תסיים את פועלה על הקלט הנתון, או שתכנס ללולאה אינסופית. במקרה הזה  \Lambda  היא קבוצת כל תוכניות המחשב (בשפה כלשהי). נניח שקיימת תוכנית  \phi  שבהינתן תוכנית  \alpha  וקלט  \beta  מכריעה האם  \alpha  עוצרת על  \beta . הביטוי  \phi _{\alpha }(\beta ) יהיה "כן" אם  \alpha  עוצרת על  \beta , ו"לא" אם  \alpha  נכנסת ללולאה אינסופית בהינתן  \beta . נגדיר תוכנית  D שבהינתן קלט  \beta , מריצה את  \phi  כדי לגלות מהו  \phi _{\beta }(\beta ) (תוכנית יכולה לקבל כקלט את עצמה, שכן כל תוכנית היא בסך הכל רצף של סימנים בשפה) - אם  \phi _{\beta }(\beta ) הוא "לא" אז  D משיבה "כן", ואם  \phi _{\beta }(\beta ) הוא "לא", אז  D לא עוצרת. מכאן ש- \phi _{D}(\beta ) הוא "כן" אם  \phi _{\beta }(\beta ) הוא "לא", והוא "לא" אם  \phi _{\beta }(\beta ) הוא "כן". כמסקנה נקבל ש- \phi _{D}(D) הוא ההפך מעצמו. סתירה זו מראה כי ההנחה שלנו כי קיימת תוכנית  \phi  שמסוגלת להכריע את בעיית העצירה היא שגויה.
משפט האי-שלמות הראשון, שהוכח על ידי קורט גדל בשנת 1931, הוא משפט מרכזי בלוגיקה מתמטית. המשפט קובע שבכל תורה העונה לתנאים מסוימים, קיימות טענות עצמאיות שלא ניתנות להוכחה או להפרכה. השלב העיקרי בהוכחת גדל מתבצע בלכסון. במסגרת ההוכחה מתעניינים בכל התכונות שניתן לנסח בתורה הנוגעות למספרים טבעיים. את התכונה שמספרה הוא  n (מספור גדל מראה כיצד להצמיד לכל תכונה מספר משלה) נסמן  \phi _{n}. הביטוי  \phi _{n}(k) הוא הטענה שהמספר  k מקיים את התכונה  \phi  (הטענה עשויה להיות נכונה או שגויה). גדל הראה כיצד ניתן לבנות בשפה תכונה  \phi _{m} (זוהי  \phi _{D}) שמתקיימת רק לאותם מספרים טבעיים שלגביהם לא קיימת הוכחה לטענה  \phi _{n}(n). כלומר הטענה  \phi _{m}(n) נכונה אם ורק אם אין הוכחה לטענה  \phi _{n}(n). כעת נפרש את המשמעות של הטענה  \phi _{m}(m). לפי הבניה, זוהי טענה שנכונה אם ורק אם אין הוכחה ל- \phi _{m}(m). כלומר זוהי טענה שאומרת "אני נכונה אם ורק אם אי אפשר להוכיח אותי".