בתשובה לקשר, 23/09/15 1:39
יציבות ואי-יציבות בלולאה 663955
הבה ונבחן את משפטי גדל, עפ"י הנאמר במאמרו של אלון עמית, ולשם כך אשתמש בקטעים שהם, לדעתי, ליבת המאמר:

"השיטה האקסיומטית

איך אפשר להוכיח דבר־מה, לדעת בוודאות גמורה שמשהו נכון? ילדים מומחים בלנהל עם מבוגרים דיאלוגים מייאשים מהסוג הבא: "אם תעזוב את הבובה, היא תיפול למים." – "למה?" – "זה נקרא כוח המשיכה. דברים נופלים." – "למה?" – "המממ... כי לכדור הארץ יש מסה...?" – "למה?" – "כי ככה אמא אומרת! די!" לוגיקה היא דרך מסודרת להוכיח דבר מתוך דבר. כיוון שכך, צריך להתחיל ממשהו, ואותו משהו נקרא הנחות־יסוד, או אקסיומות. את אלה אין אנו מוכיחים; אנו מקבלים אותן כי הן נראות סבירות, או שימושיות למטרה מסויימת. אחרי שהחלטנו על האקסיומות עלינו להסכים גם על כללי־היסק לוגיים, ואז אפשר לגזור מסקנות בצורה פשוטה: כל מסקנה היא או בעצמה אקסיומה, או שהיא נובעת ישירות ממסקנות קודמות על־ידי אחד מכללי־ההיסק.

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

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

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

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

---------------------------------

אחלץ מקטע זה את התכנים העיקריים (לדעתי):

1. הנחות-יסוד הינן מסקנות שאינן מוכחות ואנו מקבלים אותן (מבלי להוכיחן) מפני שהן נראות סבירות, או שימושיות למטרה מסויימת.

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

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

4. תורה מתמטית (נסמנה כ-T) היא אוסף של אקסיומות וכללי־היסק.

5. מושג ה"אמת" במתמטיקה הינו הגדרה פורמלית התלויה ב"מודל" (פירוש אפשרי להגדרה הפורמלית) המשמש במסגרת תורה מתמטית נתונה.

---------------------------------

...

"מה גדל כן

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

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

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

המשפט הראשון: אם T תורה אריתמטית, אפקטיבית ועקבית, אז יש נוסחה G כך ש-T אינה מוכיחה את G וגם אינה מוכיחה את שלילתה של G. מכאן ש-T איננה שלמה.

המשפט השני: אם T תורה אריתמטית ואפקטיבית, אז יש נוסחה C האומרת "T היא עקבית". אם, בנוסף, T עקבית, הנוסחה C אינה ניתנת להוכחה ב-T."

---------------------------------

אחלץ מקטע זה את התכנים העיקריים (לדעתי):

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

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

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

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

4. תורה "אריתמטית" הינה אוסף של אקסיומות וכללי היסק המאפשרים לנסח ולהוכיח בה מספר משפטים בסיסיים הקשורים במספרים.

"המשפט הראשון: אם T תורה אריתמטית, אפקטיבית ועקבית, אז יש נוסחה G כך ש-T אינה מוכיחה את G וגם אינה מוכיחה את שלילתה של G. מכאן ש-T איננה שלמה."

(בקיצור T אינה (אריתמטית, אפקטיבית ועקבית) וגם (שלמה)).

"המשפט השני: אם T תורה אריתמטית ואפקטיבית, אז יש נוסחה C האומרת "T היא עקבית". אם, בנוסף, T עקבית, הנוסחה C אינה ניתנת להוכחה ב-T."

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

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

---------------------------------

...

קטע מתוך "מה גדל לא

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

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

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

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

---------------------------------

אחלץ מקטע זה את התכנים העיקריים (לדעתי):

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

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

-------

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

טענה 1: אם T עקבית, אז "G אינה יכיחה בתורה T" הינה טענת "אמת" במסגרת תורה T.

טענה 2: אם T עקבית, אז "T היא עקבית" הינה טענת "אמת" במסגרת תורה T.

איני חושב שטענות 1 ו-‏2 שקולות זו לזו במסגרת תורה T, היות וטענה 2 הינה טענה טריוואלית מעגלית שאינה קשורה כלל למסקנות משפטי אי-השלמות של גדל, בעוד שטענה 1 קשורה אף קשורה למשפטים אלה, שעל פיהם T אינה "אריתמטית, אפקטיבית ועקבית" וגם "שלמה".
יציבות ואי-יציבות בלולאה 663981
כפי שכותב אלון עמית: "את הטענה "אם T עקבית, אז G נכונה" בהחלט אפשר להוכיח ב-T"

אך אם T עיקבית, אז הנוסחה "G אינה יכיחה בתורה T" הינה "אמת" ב-T שאינה יכיחה ב-T, ולכן T אינה תורה שלמה גם אם נוסיף לה אינסוף אקסיומות וכללי היסק.

השתמשתי במושג האורך ובביטויו אורך=0 ו-אורך>0, כך שאוסף אורכי 0 אינו מהווה אורך>0, ואורך>0 אינו ניתן לרדוקציה לאורך=0 וגם מהווה אורך>0.

הגדרתי שקילות בין אוסף אורכי 0 לאקסיומות של תורה T, ושקילות בין אורך>0 לנוסחה G בתורה T, שהינה "אמת" ב-T אך אינה יכיחה ב-T.

יש לשים לב כי G הינה נוסחת "אמת" בתורה T בתנאי ש-T עיקבית, אך לא-שלמה.

השקילות לעיקביות T עפ"י מושג האורך היא שכל אורכי 0 ממוקמים בתחום אורך>0.

השקילות לאי-שלמות T עפ"י מושג האורך היא ששום כמות (סופית או אינסופית) של אורכי 0 הממוקמים בתחום אורך>0, אינו מהווה את אורך>0.

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

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

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

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