בתשובה לעוזי ו., 18/07/05 21:19
2 הערונות 318019
אלון עמית • בתשובה לעוזי ו. יום ג', 19/7/2005, 1:52
לא. ב-PA, למשל, היינו רוצים לנסח את כלל האינדוקציה כ"לכל קבוצה X שאיננה ריקה יש איבר קטן ביותר", אבל אי-אפשר, ואנו נאלצים לעשות משהו כמו בתגובה 317102; אי-אפשר לגזור טאוטולוגית (ברוב המקרים) את האקסיומות הללו זו מזו. לכך התייחסתי במאמר כשציינתי שאפילו תורות אריתמטיות פשוטות דורשות אינסוף אקסיומות: לא קשה להראות שאין אוסף סופי של אקסיומות השקול ל-PA.

אחת ההשלכות החשובות של זה היא שאינדוקציה ב-PA "עובדת" רק עבור תכונות הניתנות להגדרה ב-PA; ל-PA אין מושג מה זה "קבוצה שרירותית של טבעיים".
2 הערונות 318020
האייל הצעיר • בתשובה לאלון עמית יום ג', 19/7/2005, 1:55
באמת רציתי לשאול, מה המקום של הכמת "לכל" באינדוקציה באמצעות PA. האם ניתן להוכיח ב-PA ש"אם טענה נכונה עבור x=0, וגם קיומה עבור x=n גורר את קיומה קיומה עבור x=n+1, אזי הטענה נכונה לכל x"?
2 הערונות 318025
אלון עמית • בתשובה להאייל הצעיר יום ג', 19/7/2005, 2:25
כן, אבל רק בשל הסיבה הבאנאלית שהענקנו ל-PA את כל אחד ואחד מהמשפטים הללו כאקסיומות, אחד עבור כל טענה מסדר ראשון בשפה. אי-אפשר להוכיח ב-PA את המשפט "לכל טענה, אם היא נכונה ל-x=0, ו... אז היא נכונה לכל x". פשוט מפני שאי-אפשר אפילו *לנסח* את המשפט הזה - אפשר ב-PA לכמת על מספרים, לא על קבוצות או טענות.

זה מה שהתכוונת לשאול?
2 הערונות 318153
האייל הצעיר • בתשובה לאלון עמית יום ג', 19/7/2005, 17:50
לא. נדבר לצורך העניין על טענה מסוימת. נניח שהיא נכונה עבור x=0, ושאם היא נכונה עבור x=n היא נכונה גם עבור x=n+1.

ברור שעבור כל x אנחנו יכולים להוכיח את הטענה. עבור x=1, ההוכחה תהיה בת צעד היקש אחד; עבור x=2, ההוכחה תהיה בת שני צעדי היקש; עבור x=3 ההוכחה תהיה בת שלושה צעדי היקש...

השאלה שלי היא: האם ניתן לנסח ולהוכיח ב-PA את הטענה לפיה "לכל x מתקיים <הטענה שלנו>"?
2 הערונות 318158
עוזי ו. • בתשובה להאייל הצעיר יום ג', 19/7/2005, 18:37
מכיוון שאי-אפשר לנסח במסגרת השפה מסדר ראשון של האריתמטיקה טענה על "כל הנוסחאות" או על כל הקבוצות של מספרים, מניחים אקסיומה סכמטית, כלומר מתכון שממנו אפשר לגזור אינסוף אקסיומות. לכל נוסחה f שיש לה בדיוק משתנה חופשי אחד, האקסיומה הבאה כלולה ברשימה:
"אם ((f(0 וגם (לכל x (אם (f(x אז (f(x+1))), אז (לכל x מתקיים (f(x)".

לכן הטענה שאתה צריך להוכיח (באמצעות הוכחה סופית!) היא "לכל x (אם (f(x אז (f(x+1)". אם יש הוכחה כזו וכמובן אם מתקיים (f(0, אז האקסיומה מאפשרת לגזור את המסקנה "לכל x מתקיים (f(x".
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות