בתשובה לאלון עמית, 19/07/05 1:52
 |
|
 |
||
|
||||
 |
באמת רציתי לשאול, מה המקום של הכמת "לכל" באינדוקציה באמצעות PA. האם ניתן להוכיח ב-PA ש"אם טענה נכונה עבור x=0, וגם קיומה עבור x=n גורר את קיומה קיומה עבור x=n+1, אזי הטענה נכונה לכל x"? |  |
 |
 |
|
|
|
||
|
||||
|
כן, אבל רק בשל הסיבה הבאנאלית שהענקנו ל-PA את כל אחד ואחד מהמשפטים הללו כאקסיומות, אחד עבור כל טענה מסדר ראשון בשפה. אי-אפשר להוכיח ב-PA את המשפט "לכל טענה, אם היא נכונה ל-x=0, ו... אז היא נכונה לכל x". פשוט מפני שאי-אפשר אפילו *לנסח* את המשפט הזה - אפשר ב-PA לכמת על מספרים, לא על קבוצות או טענות. זה מה שהתכוונת לשאול? |
|
|
|
|
|
|
||
|
||||
|
לא. נדבר לצורך העניין על טענה מסוימת. נניח שהיא נכונה עבור x=0, ושאם היא נכונה עבור x=n היא נכונה גם עבור x=n+1. ברור שעבור כל x אנחנו יכולים להוכיח את הטענה. עבור x=1, ההוכחה תהיה בת צעד היקש אחד; עבור x=2, ההוכחה תהיה בת שני צעדי היקש; עבור x=3 ההוכחה תהיה בת שלושה צעדי היקש... השאלה שלי היא: האם ניתן לנסח ולהוכיח ב-PA את הטענה לפיה "לכל x מתקיים <הטענה שלנו>"? |
|
|
|
|
|
|
||
|
||||
|
מכיוון שאי-אפשר לנסח במסגרת השפה מסדר ראשון של האריתמטיקה טענה על "כל הנוסחאות" או על כל הקבוצות של מספרים, מניחים אקסיומה סכמטית, כלומר מתכון שממנו אפשר לגזור אינסוף אקסיומות. לכל נוסחה f שיש לה בדיוק משתנה חופשי אחד, האקסיומה הבאה כלולה ברשימה: "אם ((f(0 וגם (לכל x (אם (f(x אז (f(x+1))), אז (לכל x מתקיים (f(x)". לכן הטענה שאתה צריך להוכיח (באמצעות הוכחה סופית!) היא "לכל x (אם (f(x אז (f(x+1)". אם יש הוכחה כזו וכמובן אם מתקיים (f(0, אז האקסיומה מאפשרת לגזור את המסקנה "לכל x מתקיים (f(x". |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש והצהרת נגישות
|
© כל הזכויות שמורות |