בתשובה לאלון עמית, 27/04/05 0:09
 |
|
 |
||
|
||||
 |
זה יהיה מתעלק מדי לבקש הסבר תמציתי על משפט גדל וההשלכות שלו עבור הקוראים חסרי ההשכלה המתמטית? |  |
 |
 |
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
לא מתעלק, רק מסוכן: יהיו כאלה שיניחו שאת ההודעה שלך שלחתי אני כדי שלא יהיה לי משעמם (ולא, לא משעמם לי. ממש לא. למעשה, ממש ממש ממש *ממש* לא). בקיצור נמרץ: לאור מספר טעויות היסטוריות וויכוחים על שאלות-יסוד, התעורר בסוף המאה ה-19 הרצון לבסס בזהירות את "כל המתמטיקה" על מספר קטן ומוסכם של הנחות-יסוד (אקסיומות) ומספר קטן ומוסכם של כללי-היסק. בגיאומטריה של המישור זה עבד היטב, והמטרה הבאה היתה תורת המספרים (תחום פשוט-לכאורה הדן בתכונותיהם של המספרים הטבעיים 1, 2, 3, וכו'). כדי להשתכנע שמערכת מסוג זה (אקסיומות וכללי-היסק) היא סבירה, ביקשו שתהיינה לה התכונות הבאות: 1. "סופיות": אם מישהו מראה לך טענה מסויימת ואת ההוכחה המדוייקת שלה, אתה תוכל להפעיל תהליך סופי ומכני כדי לוודא שההוכחה נכונה. לא היו אז מחשבים, אבל אילו היו, היו אומרים: הוכחה מתמטית צריכה להיות ניתנת לבדיקה ע"י מחשב. 2. "עקביות": המערכת לא מובילה לסתירה. אי אפשר להוכיח בעזרתה גם את "1 איננו 0" וגם את "1 שווה ל-0". 3. "שלמות": המערכת חזקה מספיק כדי להוכיח כל טענה נכונה. אין מצב שבו לא ניתן להוכיח את X וגם לא ניתן להוכיח את לא-X. את 1. רצו כדי שלא ניתן יהיה להתווכח אם הוכחה היא נכונה או לא: הוכחה היא תהליך מסודר שניתן לווידוא מכני. את 2. רצו מסיבות מובנות. את 3. רצו כי אם אי-אפשר להוכיח ש-X נכון וגם אי-אפשר להוכיח ש-X לא נכון, נראה שהמערכת חלשה מדי (ברור שאחד מהם נכון). חוץ מזה, בלי משהו כמו 3 זה "לא חכמה": מערכת טיפשית שיש בה אקסיומה אחת "הים הוא מלוח" ואף כלל-היסק עונה על 1 ו-2, אבל היא חלשה מכדי להגיד משהו מעניין על מספרים. מה שגדל הראה הוא שאין אפשרות לעשות זאת. כל מערכת לוגית (בעלת תכונות סבירות כמו 1) שהיא חזקה מספיק כדי לדבר על המספרים הטבעיים תהיה או לא עקבית או לא שלמה. לגבי ההשלכות: אלמלא משפט גדל, אפשר היה לדמיין את הלוגיקה המתמטית "נגמרת". היו בונים מערכת נוחה לכל המתמטיקה, מראים שהיא עקבית ושלמה, ושלום על ישראל. בגלל המשפט המפתיע הזה נוצר הצורך להבין את גבולות היכולת של מערכות פורמליות שונות, למה ניתן לצפות ולמה לא ניתן לצפות. חוץ מזה, נוצרה אפשרות מבהילה-קצת לפיה טענה מסויימת (כמו "כל זוגי הוא סכום של שני ראשוניים") תהיה לא-ניתנת-להוכחה וגם לא-ניתנת-לסתירה (במערכת פורמלית מסויימת). במהלך השנים נתגלו כמה תוצאות מעניינות מסוג זה. לבסוף, המשפט יצר מעין אופנה, או תרבות, או רוח-זמן, של תוצאות שוללניות בעלות אופי דומה, המצביעות על גבולות היכולת של מערכות מסויימות. כאמור, היו שניסו לייצר מכך טענות פילוסופיות דרמטיות למדי, ללא הצלחה מיוחדת להערכתי. כל זה בקיצור וקצת חפיפי, מקווה שזה עזר. |
|
|
|
|
|
|
||
|
||||
|
"בגלל המשפט המפתיע הזה נוצר הצורך להבין את גבולות היכולת של מערכות פורמליות שונות, למה ניתן לצפות ולמה לא ניתן לצפות" אתה יכול להרחיב קצת לגבי הנקודה הזאת? (כלומר, מה משפט גדל שינה לגבי התפיסה שלנו את גבולות היכולת של מערכות פורמליות שונות?) |
|
|
|
|
|
|
||
|
||||
|
פשוט מאוד: הוא הראה שיש כאלה (גבולות, זאת אומרת). לפני גדל, קיוו לבנות מערכת פורמלית שבתוכה ניתן יהיה להוכיח או להפריך כל טענה בתורת-המספרים, נניח. בעקבות המשפט, הבינו שלא ניתן לצפות שמערכת פורמלית אחת תיתן מענה לכל השאלות. למערכת פורמלית נתונה יש "כוח" מסויים (דברים שהיא מסוגלת להראות), והכוח הזה לא תמיד מתלכד עם מה שהיית רוצה (דברים שהיא מסוגלת לדבר עליהם). לדוגמה, אף מערכת פורמלית (מעניינת, עקבית) איננה מסוגלת להוכיח את העקביות של עצמה, למרות שהרבה מערכות פורמליות מסוגלות לנסח את העקביות של עצמן כטענה (כלומר "לדבר על זה"). השינוי התפיסתי הרחב יותר הוא שמאז גדל, בכל פעם שמנסים להתמודד עם שאלה שנראית מסובכת, במיוחד שאלות בעלות אופי מאוד כללי (אלגוריתם הבודק אם יריעה היא כדור, השאלה אם P=NP, תהליך לבדיקת פתירות של משוואה דיופנטית), מנקר תמיד החשש שמא התשובה היא שאין תשובה (במסגרת האקסיומטית הנוכחית). לפעמים החשש אפילו מיתרגם לעובדה, לפעמים לא, אבל הוא בכל מקרה שם, ואני חושב שהוא לא ממש היה שם לפני 1931. |
|
|
|
|
|
|
||
|
||||
|
בגלל הבורות שלי בתחום אני לא כ"כ מבין מה זה אומר " מערכת שאיננה מסוגלת להוכיח את העקביות של עצמה" אגב, יש אפשרות להסביר את ההוכחה המתמטית של גדל בצורה שתהיה מובנת לאנשים חסרי השכלה מתמטית? |
|
|
|
|
|
|
||
|
||||
|
בטח שיש. בשביל מה המציאו את הופשטטר? (תגובה 4582, תראו כמה מזמן הספר הזה הופיע באייל...). לא שצריך כל-כך הרבה עמודים בשביל זה, אבל זה ספר שלדעתי כדאי לקרוא (למרות מגרעותיו). יש עוד ספרים פופולריים על ההוכחה, אבל לא עולה לי בראש שם מתאים. אם תרצה אחפש. לשאלתך הראשונה: מערכת פורמלית של תורת המספרים מאפשרת לנסח טענות על מספרים. זה פשוט אוסף של סימנים מוסכמים (כמו "0", "y", "+", "=") וכל-מיני כללים האומרים איך אפשר לחבר את הסימנים האלה לפסוקים, מה האקסיומות, ומה הכללים המאפשרים להסיק מסקנות. פסוק יכול להיות משהו כמו A x E a,b,c,d | x=a^2+b^2+c^2+d^2 (נסה לקרוא את הפסוק הזה בקול כשאתה מחליף A ב"לכל", E ב-"יש" ו-"|" ב-"כך ש"). נניח שיש לך מערכת כזו, נקרא לה PA. על פניו נראה שהמשפט "PA היא עקבית" הוא משפט שאנחנו, בני-האדם, יכולים להגיד *על* PA. הוא לא נראה כמו פסוק שאפשר לנסח *בתוך* המערכת (כמו הפסוק "כל מספר הוא סכום של ארבעה ריבועים" שהדגמתי). זו לא (נראית כמו) טענה מתמטית, אלא כמו טענה מטא-מתמטית. אחד הדברים שגדל גילה הוא שזו אשלייה: אפשר לנסח ב-PA את הטענה "PA עקבית".אם אפשר לנסח את הטענה הזו, הצעד הבא הוא לנסות להוכיח אותה. את זה אי-אפשר לעשות, לא ב-PA. אפשר לעשות זאת בתוך מערכת חזקה יותר, אבל אז את העקביות *שלה*... וכו'. |
|
|
|
|
|
|
||
|
||||
|
אולי אני טועה, אבל יכול להיות שההסבר הברור שלך הזכיר לי במעומעם קורס בחישוביות(?) שלקחתי לפני שנות אלף אצל שוויקה? | |
|
|
|
|
|
||
|
||||
|
היחיד שיכול לומר אם זה הזכיר לך או לא זה בעל הזיכרון - אתה (יש על זה מאמר מעניין באייל שהתפרסם לאחרונה, לא זוכר של מי. כדאי לך לקרוא). כן, בטח שיכול להיות... התוצאות הבסיסיות בחישוביות דומות מאוד. |
|
|
|
|
|
|
||
|
||||
|
תודה | |
|
|
|
|
|
||
|
||||
|
(אני לא בטוח שעניתי על השאלה, אם צריך אולי תוכל לחדד אותה קצת). | |
|
|
|
|
|
||
|
||||
|
דבר אחד שעדיין לא הבנתי בכל הנוגע למשפט גדל היא הנקודה של "יש דברים שאי אפשר להוכיח או להפריך, אבל הם *נכונים*". פנרוז, למשל, חוגג על זה ב-"The emperor's new mind" וטוען שבזה מותר האדם מהמחשב, או משהו. האם השערת הרצף היא "נכונה" במובן זה? ומשפט גודשטיין? | |
|
|
|
|
|
||
|
||||
|
אני, כמובן, לא יכול לענות לך, אבל רוצה לנצל את ההזדמנות להגיד משהו שקשור לזה: מה שפנרוז עשה עם משפט גדל גובל בפלילים. אין לי שום דבר נגד מי שרוצה לעשות ספקולציות פרועות עם כל עניין בעולם, אבל יואיל נא לציין בפני קהל קוראיו התמים שאלו ספקולציות שלו ולא משהו מוכח מתמטית כמשפט גדל עצמו. אחרת, כפי שקרה עם פנרוז, אתה נתקל באנשים שלא יודעים לחבר שתיים ושתיים בלי לקבל שש שמספרים לך בבטחון על כך ש"מתמטיקאים הוכיחו שהמוח אינו מכונה" או כל מיני בוקי סרוקי כאלה, מהם נובע כביכול שיש משהו על-טבעי באותו ליטר וחצי חומר אורגני שתחום ע"י עצמות הגולגולת. תופעה דומה קיימת גם בפיזיקה, בזכות הרעיון המשונה של ויגנר על התודעה האנושית שנחוצה כדי שפונקציית הגל תקרוס, והחתול המעונה של שרדינגר יוכל להחליט אם הוא חי או מת. מה עוד צריך כדי להוכיח קיום של איזו נשמה מסתורית שנמצאת מחוץ לתחומי הפיזיקה? כלום. המשפט "תורת הקוואנטים מוכיחה ש..." מחליף את "ויגנר העלה שפקולציה מוזרה ש..." בכל כך הרבה מקומות, עד שבא להקיא. |
|
|
|
|
|
|
||
|
||||
|
אכן, אלא שפנרוז ללא ספק יודע לחבר שתיים ועוד שתיים ולקבל ארבע, והספר שלו בכל זאת סוקר לא רע את התחומים שעליהם הוא מדבר, ולכן אני נוטה להקשיב לו (ולא להסכים) מאשר לקרוא למשטרה. אני גם לא חושב שהטענה שלו היא ''המוח אינו מכונה'', אלא לכל היותר ''המוח אינו מחשב'' - וייתכן שזה מעיד בעיקר על המגבלות של המחשבים כפי שהם קיימים כיום (אף אחד לא ''הוכיח'' את התזה של צ'רץ' וטיורינג, דומני). | |
|
|
|
|
|
||
|
||||
|
אין לי ספק שפנרוז עצמו מבין טוב מאד, ואני גם לא מוטרד מסטודנטים למתמטיקה שקוראים אותו. גם ויגנר ידע דבר או שניים בפיזיקה, וסטיבן גולד לא היה זקוק לקורס בדארויניזם. הבעיה היא שכשאתה כותב ספר לקהל הרחב ואתה לא מפריד באופן ברור ומוצהר בין הרעיונות שלך לבין משפטים, הוכחות ומה שמקובל בתחום, אתה פותח פתח לשרולטנים ולבורים (ויגנר פטור מהאשמה הזאת, כי עד כמה שאני יודע הוא לא כתב ספר פופולרי על הרעיונות שלו). |
|
|
|
|
|
|
||
|
||||
|
לא השתכנעתי בכלל מ-Emperor's New Mind וגם לא מספר ההמשך (שכחתי את שמו); פנרוז הוא פנרוז, אבל לדעתי כאן הוא פישל. אני חושב שאני יודע למה אתה מתכוון בביטוי "יש דברים שאי אפשר להוכיח או להפריך, אבל הם *נכונים*"; צריך רק להיזהר קצת כשאומרים דברים כאלה. "אי אפשר להוכיח" זה תמיד במסגרת של מערכת פורמלית מסויימת; אין תוצאות (בטח לא משפט גדל) שמראות שמשהו אינו ניתן להוכחה באיזשהו אופן *אבסולוטי*. גם לא תהיינה כאלה: תמיד אפשר להוסיף את הטעון-הוכחה כאקסיומה. צריך לזכור מה אנחנו מנסים לעשות עם כל המערכות הפורמליות האלה: לפרמל באופן פשוט, יחסית, מושגים מורכבים מאוד כמו "המספרים הטבעיים", ולהוכיח במסגרת זו מיני טענות. הניסיון לפרמל כך הוא ראוי ומוצלח, אבל אף-אחד לא הבטיח לנו שזה יעבוד, ולפעמים ההתרגשות הגדולה מכך שזה לא נראית לי משונה (אם לחזור רגע לפנרוז). אני לא אומר שאין כאן נקודות מבלבלות - יש הרבה - אבל מה הפלא בכך שמערכת מסויימת, נגיד PA, לא חזקה מספיק כדי להוכיח משהו? PA היא חמודה, נכון; היא נראית, אולי, "מספיקה" באופן אינטואיטיבי, נכון; אז? (אגב, אני לא יורד פה עליך, חלילה, אלא על צד שלישי מסתורי שטוען את הטענה שהזכרת). משפט גודסטין נובע מ-ZFC, למעשה ממערכות חלשות הרבה יותר (נראה לי, למשל, שאפשר לוותר על C). כיוון שכולם מאמינים ל-ZF, סביר להניח שמשפט גודסטין הוא נכון. בוא נזכור, שוב, מה מבלבל בו: אי אפשר להוכיחו ב-PA. מפתיע, משעשע, אולי אפילו מצער קצת, אבל זה לא אומר יותר מדי; בטח לא שהוא "לא נכון". השערת הרצף זה סיפור אחר. היא לא תלויה אפילו ב-ZFC, וגם לא באף אחד מבין הרבה חיזוקים שונים ומשונים של ZFC שרובם נמצאים תחת הכותרת "קרדינלים גדולים" (אין קשר לראצינגר). היא כן נובעת מ-V=L, שזו בערך ההנחה שכל הקבוצות בעולם ניתנות לבנייה מפורשת. האם היא נכונה "באמת"? אף אחד לא יודע. לא ברור שזו שאלה בעלת משמעות: האם אקסיומת המקבילים נכונה באמת? יש גאומטריות בהן כן, וגאומטריות בהן לא. מהי הגאומטריה הנכונה? זו התקפה ביקום הפיזיקלי? למה? יש אנשים הסבורים שיש דבר *אחד* כזה, "קבוצות", ובו CH או נכונה או לא נכונה. בימים זוגיים אני נוטה לקבל את ההנחה הזו; במקרה כזה, האנלוגיה לגאומטריה היא אחרת: עלינו פשוט למצוא את "אקסיומת המקבילים" המתאימה, זו שהיא גם מובנת-מאליה וגם מכריעה את CH. כאמור, עד היום לא נמצאה כזו (V=L רחוקה מלהיות מובנת-מאליה). |
|
|
|
|
|
|
||
|
||||
|
לי אישית מפריעות הטענות שמשהו נכון באופן "אבסולוטי". הרי אני יכול מחר להמציא תורת מספרים שבה 1+1=0 (יש שמועות שכבר יש כזו), וזה יהיה "נכון", למרות שבאופן "אבסולוטי" זה לא נכון (כי הרי כל ילד יודע ש1+1=2). לכן המושג שלי של "נכונות" מתמצה ב"יכיחות", ואם משהו לא ניתן להוכחה ממערכת אקסיומטית מסויימת, אני גם לא יכול לומר שהוא נכון בה. כמובן, כשאנחנו ניגשים למציאות עם המושג האינטואיטיבי שלנו של "נכון", ברור לנו ש-1+1=2 ולכן התוצאה 1+1=0 "לא נכונה". אבל אי הנכונות הזו פירושה שהמערכת האקסיומטית שלנו שבה 1+1=0 פשוט לא *מתאימה* למציאות שאותה אנחנו מנסים למדל, לא שהיא "לא נכונה". אבל כשלמדתי לוגיקה טיפה הסתבכתי, כי שם דיברו על דברים שהם "נכונים" בתוך *מערכת אקסיומות* כלשהי, אבל לא יכיחים מתוכה. ואת זה כבר לא הבנתי, לפחות לא את המשמעות הפילוסופית. |
|
|
|
|
|
|
||
|
||||
|
המשפט האחרון בתגובה שלך הוא לוז העניין, אבל אלון יסביר את זה הרבה יותר טוב ממני. | |
|
|
|
|
|
||
|
||||
|
הגזמת. תורת המספרים שלך (זו עם מציין 2) היא תורה, אבל לא תורת-*ה*מספרים. אתה לא מקבל שיש דבר כזה "המספרים הטבעיים"? אתה מאמין שמשפט פרמה נכון? למה? כי הוכיחו אותו? מאילו אקסיומות? כנראה, ZFC. למה אתה מקבל את האקסיומות של ZFC כנכונות? אם "נכונות" זה "יכיחות", איך אתה מקבל איזושהי אקסיומה בכלל? הזכרת את "המציאות שאותה אנחנו מנסים למדל". אם יש כזו, אז יש כזה דבר "נכון". נניח שמחר מוכיחים שההשערה על קיום אינסוף ראשוניים-תאומים (twin primes) איננה תלויה ב-ZFC; זה לא בלתי-אפשרי. מה תאמר אז? ש-TP אינו נכון ואינו לא נכון, או שהוא אחד מאלה ורק חסרה אקסיומה? אחרת הדרכים לפרש את משפט גדל היא לומר, בדיוק, ש"נכונות" (של טענות במודל מסויים) *אינה* יכולה להתמצות ב"יכיחות" (במסגרת מערכת אקסיומות מסויימת לאותו מודל). זה כנראה מה שבלבל אותך בקורס בלוגיקה (את המשפט "דברים שהם "נכונים" בתוך *מערכת אקסיומות* כלשהי" אני מתקשה לפענח). |
|
|
|
|
|
|
||
|
||||
|
טוב, לשאלות האלה אני כבר לא יכול לענות בלי לעורר אצלך עוד שאלות מאותו סוג, ולכן אקח אותן כחומר למחשבה. | |
|
|
|
|
|
||
|
||||
|
< (את המשפט "דברים שהם "נכונים" בתוך *מערכת אקסיומות* כלשהי" אני מתקשה לפענח). יתכן והכוונה דברים שנכונים ב*מודל* מסוים של האקסיומות. |
|
|
|
|
|
|
||
|
||||
|
ממה שאני זוכר, ההוכחה של משפט אי השלמות עצמו בונה פסוק מהסוג הזה: הוא לא יכיח אבל הוא "נכון". האם זה באמת אומר שהכוונה היא שהוא יהיה נכון ב*כל* מודל שמתאים לאקסיומות? | |
|
|
|
|
|
||
|
||||
|
זה שהוא ''נכון'' לא אומר שהוא נכון. אם היה נכון בכל מודל של התורה , הרי היה יכיח ע''פ משפט השלמות. | |
|
|
|
|
|
||
|
||||
|
לכן אני כותב ''''נכון'''' ולא ''נכון'', ולכן אני אומר שלא הבנתי את המשמעות הפילוסופית (וכנראה פשוט לא הבנתי מה שהמרצה אמר). | |
|
|
|
|
|
||
|
||||
|
זו לא "משמעות פילוסופית", אלא דווקא הבנה של המשפט מבחינה מתמטית. הפסוק שגדל בנה אומר, בערך, "אני לא יכיח במערכת X", כש-X היא מערכת פורמלית מסויימת (הפסוק הוא אחר לכל מערכת). צריך לשם לב לכך שזה שהוא *אומר* שהוא לא יכיח לא אומר שהוא לא יכיח: הפסוק יכול להיות שקרי. אלא מאי, אם הוא כן יכיח, אז המערכת X מוכיחה משפט שקרי, שאז היא לא עקבית. אם הוא, באמת, לא יכיח, אז הוא נכון, והרי לנו משפט נכון שאיננו יכיח והמערכת X אינה שלמה. לסיכום, קיומו של הפסוק מראה ש-X היא *או* לא עקבית *או* לא שלמה (או שניהם). הוא לא מראה שהיא אחד מסויים משני אלה. כתבת למעלה: "ההוכחה של משפט אי השלמות עצמו בונה פסוק מהסוג הזה: הוא לא יכיח אבל הוא "נכון"". זה לא מדוייק: אי-אפשר להראות שפסוק מסויים אינו יכיח במערכת X מבלי להוכיח ש-X עקבית. משפט גדל רחוק מלהראות זאת. הוא תקף בכל מערכת פורמלית מספיק חזקה, ויש הרבה מערכות כאלה שהן דווקא לא עקביות. |
|
|
|
|
|
|
||
|
||||
|
תודה. לכן אומרים שלא ניתן (או לא הצליחו עד עתה) להוכיח ש-ZF עקבית? האם ניתן להוכיח ש-ZF עקבית? | |
|
|
|
|
|
||
|
||||
|
משפט אחר של גדל, דומה ברוחו, אומר שאף מערכת (חזקה מספיק) אינה יכולה להוכיח את העקביות של עצמה. לכן, אם מעוניינים להראות ש-ZF עקבית, יש לעבוד במערכת אחרת - אולי ZF עם עוד אקסיומות, אולי משהו אחר. לא מוכרות לי מועמדות מוצלחות למערכות כאלה. מהי מועמדת מוצלחת? כזו שהאקסיומות שלה נראות מובנות-מאליהן, כמו אלו של ZF; מה זה "מובן מאליו" זו כבר שאלה די נזילה. הבעייה היא שאם אותה מערכת חדשה המוכיחה את עקביות ZF - נקרא לה GA - היא מובנת-מאליה, אין סיבה שלא נהפוך *אותה* למערכת המתמטית הסטנדרטית, נוציא את ZF לגמלאות, ונישאר תקועים עם השאלה "האם GA עקבית?". אם GA איננה ממש מובנת-מאליה, אני לא חושב שמישהו ירצה לקבל אותה: הרבה יותר פשוט סתם להניח שאי-אפשר להוכיח ב-ZF ש-5=2+2. |
|
|
|
|
|
|
||
|
||||
|
החלטת בסוף לפרסם את מערכת האקסיומות שלנו? | |
|
|
|
|
|
||
|
||||
|
חשבתי דווקא לתת כבוד לבן-שיחי. | |
|
|
| חזרה לעמוד הראשי |  |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |