בתשובה לאלון עמית, 12/04/04 12:47
הצבעה על ''פסוק גדל'' מעניין 263734
אני אמנם מגיב על משהו פרה-היסטורי, אבל הדיון מרתק אותי ואני לא מבין משהו מאוד מאוד חשוב בשקפים: הטענה הייתה(בשקף 16 אם אני לא טועה) שמשפט גודסטין הוא "פסוק גדל", במובן שהוא פסוק לא יכיח מאקסיומות PA, אבל בניגוד לפסוק העמום שגדל מוכיח את קיומו (אך לא מבהיר מהו), זהו פסוק מעניין ונהיר על תורת המספרים. אם אכן זה כך, זהו צעד משמעותי בהכנסת הלוגיקה למרכז הדיון המתמטי, שכן עד כה כולם חשבו שהדיונים האלה הם דיונים גבוהים במטהמתמטיקה (או בפילוסופיה של המתמטיקה) שלא מענינים את חיי היומיום המתמטיים.
עד כאן, ציונות. וכעת למה שלא הבנתי: מאיפה הוא הסיק (טענה ראשונה בשקף 16) שנכונות משפט גוסטין שקולה לכך שניתן לבצע אינדוקציה טרנספיניטית עד אומגה אפס במסגרת PA? האם מהעובדה שאפשר להוכיח את משפט גודסטין באמצעות סודרים גבוהים מPA, נובעת הטענה שלא ניתן להוכיח זאת מבלי להשתמש בסודרים גבוהים כל כך?
אולי אלי צודק בעקרון (לא בפיתוח ההוכחה) ואכן ניתן להוכיח את משפט גודסטין באמצעים פשוטים תחת ההנחות של PA?

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

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

PA היא מערכת חלשה למדי. בעיקר מסיבה זו, אני לא בטוח שאני מסכים לטענה שמשפט גודסטין משנה משהו מהותי בנקודת המגע שבין לוגיקה למתמטיקה "יומיומית". טענה "טבעית" בתורת המספרים שהיא בלתי-תלויה ב-ZFC היתה, אולי, מחוללת מהומה רבה יותר. אנשי תורת המספרים אינם נוטים להגביל עצמם ל-PA, ואני חושב שרק מיעוטם מתעניין באמת בשאלה האם משפטים מסויימים יכיחים ב-PA או לא. ככל הידוע לי, אפילו שיטות בסיסיות כמו contour integrals אינן ניתנות לניסוח ב-PA, ולאף אחד זה לא מפריע. אם אתה מתעניין, יש ספר של Stephen Simpson הדן בגבולות היכולת של מערכות פורמליות שונות.

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

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

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

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

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

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

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

2) יכול להיות שהתכוונת לתגובה 164381. במקרה זה, ודאי שנרצה לאמץ את השערת גולדבך כאקסיומה, אם פשוטה היא ואם סבוכה.
הצבעה על ''פסוק גדל'' מעניין 264025
לא הבנתי שום דבר ממה שאמרת, אז אני מרשה לעצמי לנדנד בצורה לא מבוקרת. כתבת:
"[....]טען שהפסוקים הלשוניים שהאנושות מסוגלת לייצר היא מסיבוכיות של אומגה אפס."

ואני קצת מתפלא: האם יש פסוק לשוני שאינו מורכב מאותיות? האם יש לנו בעיה למנות את כל הספרים האפשריים בעלי ...1,2,3, אותיות? הייתכן שסיבוכיות של פסוק הוא יותר ממספר האותיות שבו?
הצבעה על ''פסוק גדל'' מעניין 264218
תגובה יפה, אם כי איני בטוח שאני מסכים, או מבין את כולה.
אגב, במשפט "יותר טבעי לנו לחשוב באופן מקוון" האם התכוונת לnested (מקונן)?
הצבעה על ''פסוק גדל'' מעניין 263985
רק הערה קטנה: PA אולי מערכת חלשה למדי, אבל עד כמדומני שעד 1977 (פאריס-הארינגטון) לא ידעו שהיא יותר חלשה מZFC.

וניטפוק: אפסילון אפס ולא אומגה אפס.

ותהיה: יומיומיות היא שבח או עלבון למתמטיקאי?
הצבעה על ''פסוק גדל'' מעניין 264027
שבח למתמטיקאי יום יומי, וגנאי למתמטיקאי שאינו יום יומי.
הצבעה על ''פסוק גדל'' מעניין 264164
ובקצרה (משהו שיתאים לתלמידי שנה שניה), מה זה אפסילון/אומגה אפס?
הצבעה על ''פסוק גדל'' מעניין 264951
תגובות:
אורי (תגובה ראשונה שלך):
1. אני לא רואה הבדל בין אקסיומות של תורת הקבוצות לבין אקסיומות של תורת החבורות. גם בתורת הקבוצות מניחים את קיומם של עצמים - שנקרא להם קבוצות - ומנסחים חוקים ותכונות של העצמים - אלה הן האקסיומות של הקבוצות - ועל פי חוקים אלה מנסים להוכיח קיום תופעות בקבוצות - משפטים מתמטיים. ההבדל הוא במוטיבציה בלבד ולא בשיטות החקירה המתמטית. בתורת הקבוצות אנו מנסים "להציל את התופעות" המתמטיות ולבססן על חוקים לוגיים שאנו יכולים לחיות איתם, ואילו בתורת החבורות אנו מנסים להגיע לתוצאות חדשות באמצעות אקסיומות יעילות יותר. אם כי גם מוטיבציות אלו השתנו עם הזמן וגם בתורת הקבוצות מנסים כיום להגיע לתוצאות חדשות (ומשפט גודסטין הוא דוגמא טובה לכך).
דרך אגב, הפילוסופיה של גדל עצמו הייתה שכל (בדגש ובבולד) המתמטיקה עוסקת בעצמים קיימים ובמשפטים נכונים אבסולוטית. הוא היה האפלטוניסט בהא הידיעה של המתמטיקה המודרנית. כך שאני לא בטוח בכך שרק תורת הקבוצות מתיימרת לתאר אמת אבסולוטית. לדעתי זה עניין של אופנה: בתקופת ניוטון ולייבניץ, יצרו את האינפיניטסימל בכדי לתאר את המציאות האבסולוטית של תנועה, ויירשטראס עיגן את זה בתורה מסודרת בכדי שלא תהיינה סתירות (כדי להצדיק את התופעות ולהביא לבסיס איתן של המתמטיקה). אחריו דדקינד ייצר את החתכים שלו כדי לייצר בסיס איתן למספרים הממשיים; אחר כך פיאנו יצר את האקסיומות שלו כדי לייצר בסיס איתן למספרים הטבעיים; קנטור יצר את התורה שלו כדי לאפשר לדבר על אינסופים, פרגה הלך עם זה רחוק מידי, ואילו ראסל וויטהד ניסו לעגן זאת בתיאוריה יומרנית בכדי לברוח מהסתירות של פרגה. בסוף הגיעו צרמלו, פרנקל ושות' בכדי לעדגן את תורת קנטור באקסיומות מסודרות יותר. מה מתוך זה הוא יסודות מתמטיקה ומה נחשב כמתמטיקה יומיומית? עוד חמישים שנה ינסחו תיאוריה הרבה יותר יסודית וחזקה שתהפוך להיות יסודות המתמטיקה ומתיימרת לעסוק אמת האבסולוטית ואילו ZFC תיחשב כעוסקת בעצמים מסוימים שניתן שיהיו גם אחרת.
2. אני חולק עליך. מבחינה מתמטית ניתן למצוא פסוקים רבים שאינם תלויים במערכת האקסיומות של PA, אך לא את כולם נרצה לקבל כאקסיומות. הם פשוט לא אינטואיטיביים מספיק. אנו רוצים לקבל כאקסיומה פסוק שאותו לא נצטרך להצדיק - פסוק שנראה כאילו הוא תופס את מהות העצם אותו אנו חוקרים ושעליו יש לנו "מודל טבעי" או יכולת להצביע עליו (מספר בPA או קבוצה בZFC). משפט שמכיל יותר מזה נרצה להחליף במשפט שקול לו (או במערכת משפטים שקולים) שהם כן נראים ומרגישים כמו אקסיומות.
אין מה לעשות - במתמטיקה נכנסים שיקולים שהם לא רק מתמטיים או לוגיים.

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

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

אורי2:
א. אכן אפסילון אפס ולא אומגה. טעות שלי...
ב. יומיומית זה לא עלבון ולא שבח (אפשר לראות זאת כשבח, אך בודאי שאין הכוונה לעלבון). הכוונה הייתה פשוט להבדיל את המתמטיקאים העוסקים במתמטיקה לעומת אלה שעוסקים ביסודות המתימטיקה, בלוגיקה ובתורת הקבוצות (ואולי גם יחד עם העוסקים בפילוסופיה של המתמטיקה ושל הלוגיקה). אתה בעצמך הבדלת לעיל בין תורת החבורות לתורת הקבוצות.
הצבעה על ''פסוק גדל'' מעניין 264952
ולסיום להיום:
אני חושב שיש מעמד מיוחד לPA על ZFC. אקסיומות PA מנסות לתאר את התכונות של המספרים הטבעיים, ואילו ZFC עוסקת בעצמים הרבה יותר כלליים ומופשטים. מי אמר שיש קבוצות אינסופיות? די בטוח שיש מספרים סופיים, אך קבוצת כל המספרים הסופיים? תצביעו לי עליה בבקשה.
אני יודע שאני נשמע כמו אינטואיציוניסט, ואין לי ממש בעיה עם זה. אבל אין הכוונה שלי לתת נאום בעד האינטואיציוניזם, אלא להמחיש את ההבדל במעמד שבין אובייקטים מתמטיים מוצקים כמו המספרים הטבעיים, יחד עם המודל הטבעי שלהם, לעומת אובייקטים מתמטים מופשטים כמו סודרים אינסופיים וכדומה. אפילו מספרים ממשיים הם לא ממש טבעיים לנו (כפל לשון) ואנו נזקקים למודל של קו ישר גיאומטרי ולמילוי החורים בו כדי לתפוס על מה מדובר.
המשפט המפורסם: "אלוהים יצר את המספרים הטבעיים, כל השאר הם מעשה ידי האדם" מדבר אלי מאוד. אני חושב שמספרים טבעיים שונים מכל עצם מתמטי אחר בכך שכל מודל מתמטי חילופי לו הוא חילופי לטבעיים ובמעמד אחר ממנו. לעומת זאת, קבוצות אינסופיות שמקיימות או לו מקיימות את השערת הרצף - האם באמת אנו יכולים להעדיף אינטואיטיבית מודל זה או אחר? יש כמובן שיקולים של יעילות ויופי מתמטי וכדומה, אבל אני לא חושב שיש ממש העדפה בסיסית של מודלים המרחיבים את המספרים הטבעיים.
מסיבות אלה, אני מעדיף להרחיב את אקסיומות פיאנו כדי לתפוס עוד ועוד תכונות של הטבסעיים, מאשר להרחיב את ZFC או אפילו מאשר להוכיח תכונות בZFC שלא ניתנות להוכחה ב PA.
הצבעה על ''פסוק גדל'' מעניין 264963
אבל PA ו- ZFC לא מתחרות בכלל על אותה גומחה אקולוגית.
הצבעה על ''פסוק גדל'' מעניין 265136
לגבי המשפט האחרון שלך: מבחינה פילוסופית נטו, למה הוכחות ב ZFC (ללא הרחבות חזקות יותר) "נחשבות" פחות? הרי כמעט כל המתמטיקה המודרנית תלויה בהן, לא? בפרט דברים מאוד "פיזיקליים" ואינטואיטיביים כמו חלקים גדולים מהאנליזה והגאומטריה. אנחנו משתמשים באקסיומות הללו בשביל כל הדברים החשובים, ודי "סומכים" עליהן. למה לא לסמוך עליהן גם בקשר לטבעיים (בהתעלם משיקולי אלגנטיות)?
הצבעה על ''פסוק גדל'' מעניין 265227
גם לעוזי וגם לגיל:
אני כתבתי על העדפתי האישית "לפרמל" את המודל הטבעי של הטבעיים באופן שמרני ששומר על רוח PA, ולא מפליג למחוזות האינסופים הגדולים והמטורפים של ZFC.
הסיבה שכתבתי זאת היא כי היו תגובות שאי תלות של פסוקים בPA זה לא חוכמה ואילו אי תלות ב ZFC זה כבר דברים מענינים יותר.

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

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים