בתשובה לעוזי ו., 18/07/05 2:19
 |
|
 |
||
|
||||
 |
1) ההגדרה שלך לתורה כבר כוללת את הנחת האפקטיביות, בניגוד למה שכתוב במאמר ולמקובל בכלל. רוב המשפטים בלוגיקה מתמטית לא דורשים שתורה תהיה אפקטיבית (משפט גדל הוא יוצא דופן). 2) אקסיומות פאנו וZF כוללים אינסוף אקסיומות אבל מספר קטן של דרכים ליצור אקסיומות (סכמות). |
 |
 |
 |
|
|
|
||
|
||||
|
2) האם הכוונה היא לאקסיומות שאפשר לגזור מטאוטולוגיות על-ידי הצבה? | |
|
|
|
|
|
||
|
||||
|
לא. ב-PA, למשל, היינו רוצים לנסח את כלל האינדוקציה כ"לכל קבוצה X שאיננה ריקה יש איבר קטן ביותר", אבל אי-אפשר, ואנו נאלצים לעשות משהו כמו בתגובה 317102; אי-אפשר לגזור טאוטולוגית (ברוב המקרים) את האקסיומות הללו זו מזו. לכך התייחסתי במאמר כשציינתי שאפילו תורות אריתמטיות פשוטות דורשות אינסוף אקסיומות: לא קשה להראות שאין אוסף סופי של אקסיומות השקול ל-PA. אחת ההשלכות החשובות של זה היא שאינדוקציה ב-PA "עובדת" רק עבור תכונות הניתנות להגדרה ב-PA; ל-PA אין מושג מה זה "קבוצה שרירותית של טבעיים". |
|
|
|
|
|
|
||
|
||||
|
באמת רציתי לשאול, מה המקום של הכמת "לכל" באינדוקציה באמצעות 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 מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |