בתשובה לעוזי ו., 27/07/05 0:05
 |
|
 |
||
|
||||
 |
1. נניח שלכל משוואה דיופנטית, היה אפשר למצוא הוכחה ב-ZFC לאי-פתירותה (אם היא לא פתירה) או לפתירותה (אם היא כן). אם כך, הרי לנו אלגוריתם לבעייה העשירית: נייצר, במקביל, הוכחות ב-ZFC ו-m-יות של מספרים; נבדוק אם ההוכחה היא (במקרה) הוכחה לאי-פתירות המשוואה, ואם המספרים מהווים פתרון; אם לא, נמשיך. תחת ההנחה ממנה התחלנו, זהו אלגוריתם תקין. כיוון שאין כזה, ההנחה שגויה: ישנן משוואות ספציפיות שאי-פתירותן אינה משפט של ZFC. 2. "באיזה מובן בדיוק, אגב?" - אני חושב שזו שאלה אליך יותר מאשר אלי. אצלי יש מובן אחד לנכונות: משפט הוא נכון אם מה שהוא אומר אכן מתקיים בטבעיים. אם הוא אומר שאין מספר-גדל של הוכחה ב-ZFC ש-0 שווה ל-1, אז באמת אין מספר כזה. 3. לא "במובן האמוני": יש לה ערך-אמת ממש, והוא "נכון". מדוע זה דורש יותר אמונה מעצם ההנחה שהאקסיומות של ZFC נכונות? 4. "למה להסיק מזה ש*לכל* הטענות מטיפוס מסויים מוכרח להיות ערך אמת?" - ודאי שאני לא מסיק זאת מזה שיש טענות כאלה. אני הולך בכיוון ההפוך: אני סבור שההנחה הטבעית (סליחה) יותר היא זו שלכל טענה כזו יש ערך-אמת, ומי שחושב אחרת, צריך לנמק. הטיעון "יש משפטים ש-ZFC לא מכריעה" נשמע לי חלש, מפני שהדגמנו שזה קורה גם במצבים בהם *ברור* שלמשפט יש בכל זאת ערך אמת. "אם יש מודל 'טבעי', מה מפריע לו לכסות גם טענות על קבוצות של מספרים וקבוצות של קבוצות..." - אני חושב שזו טעות של האינטואיציה, הנובעת מנסיוננו עם קבוצות סופיות, להניח שכשיש קבוצה, אז מקבלים במתנה גם את "כל" הקבוצות החלקיות שלה. למשל, את כל הטבעיים אפשר בקלות לייצר אחד אחרי השני ב-PA או ב-ZFC, אבל אי-אפשר בשום אופן לייצר את כל הקבוצות החלקיות שלהם. כל ניסיון אקסיומטי "לכסות" את כולן, למשל במובן של לייצר אותן רקורסיבית, נדון (כמובן) לכשלון. זה מה שמפריע למודל הטבעי לכסות גם טענות מורכבות: הוא לא כולל באמתחתו את האובייקטים עליהם אתה מדבר. אתה יכול לדבר על "המספרים הטבעיים, וכל הקבוצות ה-r.e. שלהם"; אתה יכול לדבר על "המספרים הטבעיים, וכל הקבוצות השרירותיות שלהם"; בשני המקרים אלו אותם מספרים טבעיים בדיוק, רק עם אוסף אחר של קבוצות חלקיות. אם כך, להשערת הרצף אין בהכרח ערך-אמת - תלוי במושג שלך של "קבוצה של טבעיים". |
 |
 |
 |
|
|
|
||
|
||||
|
1. תהי f משוואה שהפתירות שלה לא כריעה ב- ZFC. לו היה לה פתרון, היה אפשר לתת הוכחה ב-ZFC לכך שיש לה פתרון. אבל אין הוכחת-ZFC כזו, ולכן אין לה פתרון. זוהי הוכחה שאין ל- f פתרון. באיזו שפה ההוכחה הזו? |
|
|
|
|
|
|
||
|
||||
|
בשפה הפסיכולוגית שדיברת עליה קודם. אם הוכחה שהפתירות שלה לא כריעה זה אומר שיש מודל ל-ZFC בו יש מספר טבעי (בהכרח לא "סטנדרטי") שמהוה פתרון. מצד שני, יש מודל אחר בו אין פתרון. פסיכולוגית, אני (אתה.אנחנו) לא אוהבים טבעיים לא סטנדרטים ומעדיפים להניח שאין כאלה. |
|
|
|
|
|
|
||
|
||||
|
זו דוגמא שצריכה להיות מוכרת יותר. חשבתי שכל ההוכחות המתמטיות מתנסחות ב- ZFC בהנתן מספיק סבלנות. | |
|
|
|
|
|
||
|
||||
|
רגע אחד. "תהי f משוואה שהפתירות שלה לא כריעה ב- ZFC" זו הנחה הגוררת גם ש-ZFC עקבית, והייתי צריך להדגיש זאת קודם. כלומר, אם אתה רוצה לראות בהוכחה שלך הוכחה פורמלית באיזושהי מערכת (עם איזושהי שפה), אתה צריך להניח שאותה מערכת מוכיחה גם את עקביות ZFC. זה לא שונה בהרבה מההוכחה של השערת גולדבך מתוך ההוכחה שההשערה אינה תלויה ב-PA. את הטיעון שלך אפשר, לדעתי, בהחלט *לנסח* בשפה של ZFC; כדי שהוא יהיה באמת הוכחה (כלומר, נובע מהאקסיומות של איזושהי מערכת), צריך להסכים על המערכת, ולשים לב שהיא גם מוכיחה מהצד את עקביות ZFC. |
|
|
|
|
|
|
||
|
||||
|
אז ההוכחה שלי היא *כן* הוכחה פורמלית ב- ZFC לטענה "אם ZFC עקבית וגם הפתירות של f לא כריעה אז אין ל- f פתרון". בדיוק כמו שהמשפט של מטיישביץ', בהקשר הזה, אומר "אם ZFC עקבית אז יש משוואות לא כריעות". הרבה יותר טוב. |
|
|
|
|
|
|
||
|
||||
|
אני קצת מבולבל. הרבה יותר טוב ממה...? את הטענה "אם ZFC עקבית וגם הפתירות של f לא כריעה אז אין ל- f פתרון" אפשר לפשט למקרה הפרטי "אם ZFC לא מוכיחה של-f יש פתרון, אז ל-f אין פתרון". לא צריך את עקביות ZFC, אלא רק את העובדה שאם למשוואה דיופנטית יש פתרון אז ZFC מוכיחה זאת; זה נכון גם ל-PA, ובאותה מידה אפשר להוכיח ב-PA "אם PA לא מוכיחה ש-f פתירה, אז f אינה פתירה". (סייג כללי: אאל"ט). אולי נחזור אחורה: התחלנו מהאבחנה שיש טענות אריתמטיות חוץ מעקביות ZFC שהן לא כריעות ב-ZFC; יש אפילו משוואות דיופנטיות כאלה - וקיומן הוא, נדמה לי, יותר מעניין מהוכחה מסוג זה למשוואה ספציפית. בעקבות זאת אני ניסיתי לטעון שהזיהוי של "יכיח-ב-ZFC" עם "נכון" הוא ממילא לא סביר, והוא נשאר לא סביר גם כשנזכרים שיש גם טענות יותר מורכבות (לא פאי-1-0) שאינן יכיחות. לגבי אלה, גם אני מודה שאנחנו נשארים די תקועים לגבי בירור המצב לאשורו; אבל אני בכל-זאת סבור שיש כזה מצב לאשורו, ואני מנסה להבין מדוע אתה סבור(?) שאין כזה. |
|
|
|
|
|
|
||
|
||||
|
"אם ZFC עקבית וגם הפתירות של f לא כריעה אז אין ל- f פתרון". זו לא סתירה? |
|
|
|
|
|
|
||
|
||||
|
למה סתירה? (עקבית = המערכת לא מוכיחה ששה דברים בלתי אפשריים לפני ארוחת הבוקר. שלמה = המערכת מצליחה להחליט לגבי כל טענה. אנחנו מאמינים ש- ZFC עקבית, ויודעים שהיא לא שלמה). |
|
|
|
|
|
|
||
|
||||
|
זה מזכיר את הדיאלוג המעצבן שהיה לי עם אלון לפני כמה ימים: אם הגעת למסקנה שאין ל- f פתרון, איך אתה יכול להגיד באותה נשימה שהפתירות של f אינה כריעה? הרי הכרעת. | |
|
|
|
|
|
||
|
||||
|
הבעיה נפתרת אם מדברים במשפטים שלמים. אם מניחים ש- ZFC עקבית, אז הפתירות של f אינה כריעה במסגרת ZFC (כלומר, אין הוכחה ב- ZFC לפתירות של f וגם לא לאי-הפתירות). מכאן אני מסיק ש*אם מניחים ש- ZFC עקבית*, אז f אינה פתירה. לטענה *הזו*, יש הוכחה במסגרת ZFC (אלון מציע ניסוח אחר, אבל הם שקולים). לטענה "f אינה פתירה" אין הוכחה ב- ZFC (כמו שאין הוכחה לכך ש- ZFC עקבית). | |
|
|
|
|
|
||
|
||||
|
כן, [אני חושב ש]את זה הבנתי אחרי מאמציו הבלתי נלאים של אלון, רק הסברתי את שאלתה של האלמונית לגבי הסתירה כביכול. | |
|
|
|
|
|
||
|
||||
|
ראה תגובה 320138 | |
|
|
|
|
|
||
|
||||
|
זו הוכחה ב-ZFC, אבל חסרה כאן רישא: "אם ZFC היא אומגה-קונסיסטנטית, אז...". אומגה-קונסיסטנטיות פירושה: לא מתקיים מצב שבו המערכת מוכיחה משפט מהסוג "קיים מספר טבעי n כך שמתקיים P(n)", אבל גם לכל מספר טבעי n היא מוכיחה "לא P(n)". כמובן אי אפשר להוכיח ב-ZFC ש-ZFC היא אומגה-קונסיסטנטית. |
|
|
|
|
|
|
||
|
||||
|
אני מגיב דווקא להודעה הזו באופן חצי-שרירותי1, ונראה שקצת מאוחר מידי. אבל לא נורא, ממילא יש לי פחד קהל. בכל הדיון שלכם למעלה (וככל שהרחקתי לראות, גם למטה), נראה שאתם מתייחסים רק לדרך אחת בה אפשר לתת ערכים סמנטיים לשפה2: באמצעות אקסיומות. אבל יש דרך טבעית יותר לעשות זאת: באמצעות מבנה3. "מבנה", עד כמה שהוא מושג מתמטי-פורמלי, הוא למיטב הבנתי גם מושג *שקודם* למתמטיקה וללוגיקה. למשל, מן הסתם יש לכולנו מושג מאד ברור לגבי "מהם המספרים הטבעיים", והמושג המנטלי הזה הוא בדיוק *מבנה*, שעליו אפשר לדבר, בין השאר, בשפת תה"י מסדר ראשון. זה, יחד עם העובדה שכל תורה עקבית היא שלמה אם ורק אם יש לה מודל (=מבנה בו היא אמיתית), נראה (לי) כמו הצדקה לא רעה בכלל לגישה הפלוטנסטית הרכה שאתה מציג כאן, לפיה תורת המספרים היא שלמה. זו כמעט4 הוכחה. בכלל, נראה לי שבד"כ הרעיון של הגישה האקסיומטית, הוא לנסות להוכיח משפטים לא טריוויאלים על מבנים שבאופן עקרוני נתונים אפריורית. הגישה הזו, אם מצטמצמים לסדר ראשון5, מבטיחה שהתורה אינה קטגורית ואינה אקסיומטית, כלומר יש לה אינסוף מודלים (חוץ מהמודל שאיתו התחלנו) שאינם איזומורפיים (אבל הם כולם שקולים אלמנטרית), והמשפטים בתורה אינם ניתנים למנייה רקורסיבית. אבל למי זה מפריע? כל עוד יש גישה בלתי אמצעית למבנה (המנטלי, שהוא המושא לחקירה מלכתחילה) אפשר לבחור קבוצה שונה של אקסיומות (מתוך המשפטים אותם בקלות מזהים כנכונים במבנה), ולבדוק מה אפשר להסיק מהם6. אולי יהיו הרבה משפטים שלא נדע אם הם נכונים או לא, אבל כך או כך, The truth is out there. (בעצם לא בדיוק. כשאינטואציוניסט מתווכח עם... אהם... אנשים שפויים, הוויכוח עקר לפי התפיסה הזו, כי למעשה שניהם מדברים על עולמות אחרים, שקיימים (ממש) במידה שווה. האם יש הבדל בין לומר את זה, לבין לומר "שאין משמעות לשאלה הקיום שלהם במידה שווה"? לי נראה שכן, אבל אם תאמר אחרת - לא אתווכח - זה וויכוח עקר :)). 1 גם "חצי" כאן הוא חצי-שרירותי, ויכול היה להיות, נאמר, אחת-חלקי-פאי-שרירותי. 2 שהיא תה"י, וכאן, בד"כ, מסדר ראשון. 3 מן הסתם אתה יודע, אבל למען השלמות: מבנה הוא קבוצה עליה מדברים המכונה "עולם", עם יחסים עליה, ופונקציה המתאימה לכל קבוע בשפה, ערך בעולם, לכל יחס בשפה, יחס בעולם וכו'. 4 הדבר הטוב הבא, אחרי הוכחה.... 5 ואם לא, "אוכלים אותה" מכיוונים אחרים. 6 בזכות משפט-השלמות אפשר באמת לומר "להסיק" בהקשר הזה... |
|
|
|
|
|
|
||
|
||||
|
>בכל הדיון שלכם למעלה (וככל שהרחקתי לראות, גם למטה), נראה שאתם מתייחסים רק לדרך אחת בה אפשר לתת ערכים סמנטיים לשפה2: באמצעות אקסיומות. אבל יש דרך טבעית יותר לעשות זאת: באמצעות מבנה3. מתוך תגובתו של אלון: "אצלי יש מובן אחד לנכונות: משפט הוא נכון אם מה שהוא אומר אכן מתקיים בטבעיים." מה זה אם לא נכונות במבנה? >"מבנה", עד כמה שהוא מושג מתמטי-פורמלי, הוא למיטב הבנתי גם מושג *שקודם* למתמטיקה וללוגיקה. במובן הלא פורמלי, אתה צודק. במובן הפורמלי תורת המודלים פותחה בד בבד עם הלוגיקה. > למשל, מן הסתם יש לכולנו מושג מאד ברור לגבי "מהם המספרים הטבעיים", והמושג המנטלי הזה הוא בדיוק *מבנה*, שעליו אפשר לדבר, בין השאר, בשפת תה"י מסדר ראשון. על זה כל הדיון. אלון חושב שהמושג שלנו של מספרים טבעיים כל כך חזק עד שכל התכונות מסדר ראשון נקבעות. אני (וגם עוזי, כמדומני) לא מסכימים. >בכלל, נראה לי שבד"כ הרעיון של הגישה האקסיומטית, הוא לנסות להוכיח משפטים לא טריוויאלים על מבנים שבאופן עקרוני נתונים אפריורית. גם זה לא נראה לי נכון. הרבה פעמים מנסחים בעזרת אקסיומות את התכונות הרלוונטיות של איזשהו מבנה ואח"כ מסתכלים על איזה מבנים אחרים יש המקיימים את האקסיומות. >אבל למי זה מפריע? כל עוד יש גישה בלתי אמצעית למבנה (המנטלי, שהוא המושא לחקירה מלכתחילה) אפשר לבחור קבוצה שונה של אקסיומות (מתוך המשפטים אותם בקלות מזהים כנכונים במבנה), ולבדוק מה אפשר להסיק מהם6. אולי יהיו הרבה משפטים שלא נדע אם הם נכונים או לא, אבל כך או כך, The truth is out there. שוב, על זה כל הדיון. אם נרחיב קצת את התחום מהמספרים הטבעיים לתורת הקבוצות, נניח: האם The truth is out there גם לגבי השערת הרצף? |
|
|
|
|
|
|
||
|
||||
|
טוב, לא באמת חשבתי שאני מחדש משהו משמעותי, בסה"כ ניסיתי להציג זווית קצת אחרת להנמקת הגישה עליה אלון הגן. בניגוד לאופן בו אתה רואה את הדברים, אני לא משוכנע שהוא בעצמו היה מסכים איתי (אחרת הוא לא היה כותב "אני לא חושב על הטבעיים כמודל של כלום, אלא כמשהו שקודם למושגים "מודל" ו"הוכחה"') אתה אומר שמושג שלנו למספרים הטבעיים לא חזק מספיק. למה אתה חושב כך? כדי שהמבנה יהיה מספיק, עליו בסה"כ לפרש את הקבועים אישים ואת היחסים עליהם. לפחות לגבי חיבור וכפל אני די משוכנע שהמושג שלנו מספיק טוב, וכך גם לגבי יחסים אחרים (שאפשר להגדירם באמצעות הקודמים, ואפשר שלא) כמו חילוק, חזקה, שקילות-מודולו או היחס המודלי "להיות ראשוני". בסופו של דבר, הדרישות שמעמידים על המבנה מאד צנועות. הניסיון לנסח עבורו מערכת אקסיומות (מסדר ראשון) הוא זה שמעט יומרני, אם כבר. מה שכתבת על הגישה האקסיומטית מאד נכון, אבל אני חושב שהוא קשור יותר לפרקטיקה המתמטית מאשר לעקרונות הלוגיים. אבל לפני זה, כדי שתוכל לדבר על "מבנים אחרים שמקיימים את האקסיומות" מערכת האקסיומות לא יכולה להית קטגורית, וזה כבר מספיק כדי להבדיל בין "המבנה המנטלי" שהנחה את מנסח האקסיומות בניסוחן לבין התורה שהוא יצר (כלומר מראש "הם לא אותו הדבר", וקיום המבנה המנטלי הזה הופך את התורה לשלמה, ובכך יש "סוג של" הצדקה לפלוטוניזם). באשר להשערת הרצף - אני כבר הרבה פחות משוכנע* שאני יכול להציע אלטרנטיבה לגישת ה-"ריבוי האונטולוגי". זה אולי קצת כמו מוסר: כל אחד יכול להכריע אם זה נכון או לא, אבל אין שום דרך, מלבד השפעה "רגשית", לשכנע בנכונות ההכרעה הזו אנשים אחרים. * ומראש בכלל לא הייתי. |
|
|
|
|
|
|
||
|
||||
|
ובכן, יש רק מודל יחיד לאקסיומות פיאנו המנוסחות בשפה של לוגיקה מסדר שני (או משהו כזה), ונראה לי שזה המודל של הטבעיים שכולנו חושבים עליו. | |
|
|
|
|
|
||
|
||||
|
4 הדבר השני-הכי-טוב (ואני מקווה שיש דרך עוד יותר רהוטה לומר זאת בעברית) | |
|
|
|
|
|
||
|
||||
|
הדבר השני בטיבו? | |
|
|
|
|
|
||
|
||||
|
ברוך השב | |
|
|
|
|
|
||
|
||||
|
או ''הדבר השני הטוב ביותר'', או ''האפשרות השנייה בדרגה''. | |
|
|
|
|
|
||
|
||||
|
''בינונית שבעידית'' (טוב כשיש בדיוק תשע אפשרויות). | |
|
|
|
|
|
||
|
||||
|
''כל תורה עקבית היא שלמה אם ורק אם יש לה מודל'' נדמה לי שהמשפט הזה מוטעה. לכל תורה עקבית (המנוסחת באמצעות תחשיב היחסים) יש מודל, בלי קשר לשלמותה. למשל, למערכת אקסיומות פיאנו יש מודל (המספרים הטבעיים) על אף שאיננה שלמה. |
|
|
|
|
|
|
||
|
||||
|
מנבכי זכרוני הרעוע עולה טענה בסגנון "אם יש לתורה שני מודלים לא איזומורפיים היא לא שלמה". אני מניח שהיא שגויה אבל הרעיון הבסיסי הוא שאי-שלמות של תורה לא צריכה להתבטא בכך שאין לה מודל, אלא בכך שיכולים להיות לה כמה מודלים שונים מהותית - כשהשוני בא לידי ביטוי, למשל, באותם משפטים שאינם כריעים: במודל אחד הם יהיו נכונים ובמודל השני שקריים. | |
|
|
|
|
|
||
|
||||
|
הטענה ''אם יש לתורה שני מודלים לא איזומורפיים היא לא שלמה'' היא לא נכונה, כמובן. המונח שאתה מחפש הוא ''שקולים אלמנטרית'' שפשוט אומר שהמודלים מקיימים את אותן טענות מסדר ראשון. הטענה ''יש לתורה שני מודלים לא שקולים אלמנטרית אם ורק אם היא לא שלמה'' היא טאוטולוגיה קלה במיוחד, בהנתן משפט השלמות. | |
|
|
|
|
|
||
|
||||
|
המממ, אני הייתי בטוח שהיה איזשהו מושג יותר טריוויאלי מ''שקולים אלמנטרית'' שגורר את זה, אבל כאמור היינו ילדים וזה היה מזמן. | |
|
|
|
|
|
||
|
||||
|
"היינו ילדים וזה היה מזמן" מתייחס לירושלמים בלבד! | |
|
|
|
|
|
||
|
||||
|
אני לא בטוח שהבנתי את ההקשר של התגובה הזאת. היא מופנית אלי או אל עומר (תגובה 436354)? | |
|
|
|
|
|
||
|
||||
|
לשניכם, לא? | |
|
|
|
|
|
||
|
||||
|
כן, ברור שהמשפט שציטטת אינו מדוייק. ראשית, מכיוון שצריך להוסיף הסתייגות לגבי כך שמדובר בתורות מסדר ראשון (וכל תורה שכוללת את אקסיומות פיאנו אינה כזו), ושנית, מכיוון ש-''יש לה מודל'' צריך היה להיות ''יש מבנה שהיא התורה שלו'' (שזה דומה, אבל לא אותו הדבר). | |
|
|
|
|
|
||
|
||||
|
ניתן לראות את אקסיומות פיאנו כתורה מסדר ראשון (כאשר "אקסיומת האינדוקציה" היא סכמת אקסיומות). ועדיין, המספרים הטבעיים הם מבנה שמקיים את התורה, אך היא איננה שלמה. חוץ מזה, מה שגדי אמר (תגובה 437402). בנוגע להערה השנייה, אני לא יודע מה ההבדל בין "יש לה מודל" ובין "יש מבנה שהיא התורה שלו". תוכל להסביר? |
|
|
|
|
|
|
||
|
||||
|
כאשר מדברים על אריתמטיקת פיאנו אז כמו שכתבת, מדברים על תורה מסדר ראשון. כאשר מדברים על אקסיומות פיאנו מן הסתם מדברים על תורה מסדר שני, שהיא דווקא כן שלמה (אבל אין לה מערכת היסק שלמה). ההסבר לכך שלאריתמטיקת פיאנו יש מודל, אך היא איננה שלמה, היא בדיוק בניואנס שבמשפט האחרון שלך: ב-"יש מבנה שהיא התורה שלו" הכוונה היא לכך שיש מבנה, שהתורה שלו (כלומר כל המשפטים מסדר ראשון שנכונים בו), היא התורה שעל הפרק (למשל: תורת המספרים). משפט אי-השלמות אומר שהתורה מסדר ראשון של כל מבנה "שמכיל" בתוכו את המספרים הטבעיים עם חיבור וכפל (תורה כזו, על סמך מה שנאמר קודם, היא בהכרח שלמה), אינה אקסיומטית. לכן התורה של אקסיומות פיאנו (שהיא מן הסתם אקסיומטית) אינה שלמה. אני לא יודע מה הקשר למה שגדי אמר. |
|
|
|
|
|
|
||
|
||||
|
אבל המשפטים הם הפוכים: משפט השלמות של גדל (המקשר בין מודל לתורה) הוא על תורות מסדר ראשון, ומשפט אי השלמות הוא על תורות בכלל, לאו דווקא מסדר ראשון. | |
|
|
| חזרה לעמוד הראשי |  |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |