 |
|
 |
||
|
||||
 |
לטובת מי שחושב שיש פה משהו מסובך, הנה מילון מונחים ללוגיקה מתמטית. אני מקווה שלא שתלתי טעויות בהיסח הדעת (בפעם האחרונה עסקתי בזה לפני יותר מעשר שנים, מה שמראה עד כמה התחום הזה חיוני בעבודה היום-יומית של סתם מתמטיקאי מהשורה). יש כמה 'טעויות' שעשיתי בכוונה (כדי להמנע מסרבול יתר), אני מקווה שבלי לשנות שום דבר חשוב. לוגיקה פסוקית: השפה שבה מטפלים בפסוקים לוגיים 'חסרי תוכן', הכוללים רק מספר סופי של משתנים ואת הקשרים היסודיים (וגם, או, לא, אם-אז; אפשר להסתדר עם פחות מזה). לדוגמא, "אם a וגם b אז a"; "אם a אז לא a"; "אם (אם a אז b) וגם (אם b אז c) אז (אם a אז c)". פסוקים כאלה יכולים להיות נכונים (ואז הם נקראים "טאוטולוגיות"), או שקריים. בכל מקרה אפשר לבדוק כל פסוק בזמן סופי בהנתן ערימה גבוהה מספיק של ניירות (האלגוריתם לביצוע המשימה הוא "טבלאות אמת"). שפה מסדר ראשון: כל שפה שבה אנחנו מצויידים במשתנים (לצורך השיחה), בתוספת קבועים, פונקציות ויחסים. בנוסף לזה, מותר להגיד "לכל" ו"קיים". דוגמאות: בשפה של גאומטריית המישור אנחנו מכירים ביחס השייכות, ואז אפשר להגיד דברים כמו "לכל a, אם קיים x כך ש- x שייך ל- a, אז לכל b כך ש- b אינה שייכת ל- a, קיים c כך ש((קיים e כך ש- e שייך ל- c), אבל לא קיים d כך ש- (d שייכת ל- a וגם d שייכת ל- c))" (זו כמובן אקסיומת המקבילים). כדי לחסוך בזמן, אפשר להגדיר בשפה הזו ש"a הוא קו ישר אם קיים x כך ש- x שייך ל- a", ו"x היא נקודה אם קיים a כך ש- x שייך ל- a". מעכשיו המונחים "קו" ו"נקודה" הם חלק מהשפה, פשוט בגלל שאפשר לפרוש אותם לפסוקים מפורשים. בשפה של האריתמטיקה מכירים ב"אפס", בפונקצית ה"עוקב", וביחס השוויון, ואז אפשר להגיד דברים כמו "העוקב של העוקב של העוקב של אפס שווה לאפס" (זה לא חייב להיות נכון). בשפה של תורת הקבוצות יש רק יחס אחד, שייכות. אפשר להגיד שם: "קיים x כך שלכל y ,y לא שייך ל- x" (זה כמו להגיד "x היא הקבוצה הריקה"). אפשר להגיד גם "z שייך ל- x אם ורק אם z שייך ל- y", או לחסוך בזמן ולהגיד "x שווה ל- y". כך *מגדירים* את יחס השוויון בשפה של תורת הקבוצות. פסוק: מה שאפשר להגיד בשפה הרלוונטית. רצף של דברים כמו "לכל x", "וגם", "או" וכו', עם מספיק סוגריים כדי שאפשר יהיה לקרוא את הפסוק באופן חד משמעי. לפסוק יכולים להיות 'משתנים חופשיים', כמו למשל x בפסוק "קיים y כך ש- x<y". אקסיומות: פסוקים בשפה מסדר ראשון שאין להם משתנים חופשיים. שימו לב כמה ההגדרה קצרה. תורה: שפה מסדר ראשון, יחד עם קבוצה של אקסיומות שאפשר באופן אפקטיבי להחליט האם פסוק מסויים שייך אליה או לא. למשל, התורה של הגאומטריה האוקלידית כוללת את יחס השייכות כפי שצוין קודם, יחד עם מספר סופי של אקסיומות. כך למשל, "תורת החבורות" מיוסדת על שפה שבה יש קבוע אחד ("1") ופעולה בינארית אחת ("כפל") ויחס השוויון, ולכן אפשר להגיד בה פסוקים כמו "לכל x, x*1=x וגם x=1*x", "לכל x קיים y כך ש- x*y=1 וגם y*x=1", או "לכל x ולכל y ולכל z, קיים u וקיים v כך ש- x*y=u וגם y*z=v וגם x*v=u*z". אלו הן שלוש האקסיומות של תורת החבורות. בדרך כלל מוסיפים לכל תורה גם את כל הטאוטולוגיות של הלוגיקה הפסוקית. הוכחה: מתייחס לתורה מסויימת, שכוללת כאמור שפה ורשימת אקסיומות. הוכחה היא רשימה סופית של פסוקים, שעונים על הכללים הפשוטים הבאים: כל פסוק הוא או אקסיומה, או שהוא פסוק f, בתנאי שאפשר למצוא מוקדם יותר ברשימה פסוק g ופסוק "אם g אז f". אפשר לומר שהרשימה הזו מהווה הוכחה של הפסוק האחרון ברשימה. משפט: בתורה מסויימת, כל דבר שיושב בקצה של הוכחה. במלים אחרות - פסוק שאפשר להוכיח (מן האקסיומות, כמובן. אין למלה "להוכיח" שום משמעות אחרת). תורה עקבית: תורה שאי-אפשר להוכיח בה פסוק מהצורה "f וגם לא f", כאשר f הוא פסוק כלשהו. תורות לא עקביות הן משעממות מאד משום שאפשר להוכיח בהן כל דבר. PA או "אריתמטיקת פאנו": זוהי תורה מסויימת, המדברת על מספרים. בשפה שלה יש רק קבוע אחד (אפס), פונקציה אחת, "עוקב", יחס השוויון, וכמה אקסיומות פשוטות. אפשר להגדיר בה (במאמץ לא קטן) חיבור וכפל, ואז לנסח די הרבה טענות על אריתמטיקה. ZF או "אקסיומות צרמלו-פרנקל": תורה אחרת, המאפשרת לנסח טענות בתורת הקבוצות. כוללת מספר לא גדול של אקסיומות. ZFC: אקסיומות צרמלו-פרנקל, בתוספת אקסיומת הבחירה שנחשבת לפחות מובנת מאליה ביחס לשאר האקסיומות. בתורת הקבוצות יש מחקר פעיל של אלטרנטיבות לאקסיומה הנוספת; ZFC היא נקודת המוצא לכל שאר המתמטיקה. (זה היה מילון סינטקטי בלבד, בלי ה"חיבור לעולם". לא הזכרתי את המלים "אמת", "מודל", "נאותות" או "שלמות"). |
 |
 |
 |
|
|
|
||
|
||||
|
רעיון נהדר. זה עשוי להיות מאוד שימושי בעתיד (שלא לדבר על כמה שימושי זה היה יכול להיות בעבר). תיקון אחד, נדמה לי: אי-אפשר להגדיר חיבור וכפל בתורה מסדר ראשון אם הם לא נמצאים בה מלכתחילה; PA כוללת אקסיומות עבורם. אריתמטיקת-פרסבורגר שנזכרה במאמר היא בקירוב גס PA ששכחו לשים בה כפל. |
|
|
|
|
|
|
||
|
||||
|
אתה צודק לגבי PA: בדרך כלל מונים באקסיומות פאנו גם את אקסיומת האינדוקציה, ואז אפשר להעזר בה כדי להגדיר את הפעולות. האקסיומה הזו נשמטה ממני כי חשבתי על הניסוח מסדר ראשון. אם רוצים להשאר במסגרת של שפה מסדר ראשון, צריך לצרף את החיבור והכפל. | |
|
|
|
|
|
||
|
||||
|
"פְרֶסבורגר" הוא שם מצוין למזללת מזון מהיר לעדה החרדית. יש לכתוב, כמובן, "פרעסבורגער". | |
|
|
|
|
|
||
|
||||
|
זה יכול להיות גם בית-דפוס בבני ברק... | |
|
|
|
|
|
||
|
||||
|
(להבהיר: פרסבורגר - הן המתמטיקאי, הן צלם הקולנוע והן המזללה החרדית הפוטנציאלית - הוא בפ"א רפה.) | |
|
|
|
|
|
||
|
||||
|
המתמטיקאי דווקא לא (סליחה שלא *הדגשתי* זאת מראש). | |
|
|
|
|
|
||
|
||||
|
מתברר שגם הצלם הוא ב-פ' דגושה, ושהוא לא צלם... (תסריטאי, מפיק, במאי, אפילו שחקן בשעת הדחק - לא יכול היה לצלם איזה סרט, שיישאר לי איזה אפסילון של קרדיט?) |
|
|
|
|
|
|
||
|
||||
|
ומדוע המזללה אמורה להיות ב-פ' רפה? (פעם אמרה לי חברה, שכשאומרים "פורנוגרפיה" ב-פ' רפה, הכוונה היא לפורנוגרפיה רכה"). |
|
|
|
|
|
|
||
|
||||
|
פרעסן (Fresen) ביידיש - לזלול. מוכר במקומותינו (חלק מהם) במלה פרעסער. (ולאלון - אוף.) |
|
|
|
|
|
|
||
|
||||
|
אבל למזון מהיר - מתאים גם ''פרס'' ב-פ' דגושה... | |
|
|
|
|
|
||
|
||||
|
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". |
|
|
|
|
|
|
||
|
||||
|
תורת הקבוצות לא כוללת גם את יחס ההכלה? | |
|
|
|
|
|
||
|
||||
|
לא כחלק מהשפה: אפשר להגדיר אותו ע"י יחס השייכות. | |
|
|
|
|
|
||
|
||||
|
בשביל מה? במקום להגיד "x מוכל ב- y", אפשר להגיד "לכל z, אם z שייך ל- x אז z שייך ל- y". | |
|
|
|
|
|
||
|
||||
|
מאוד מעניינת, הצורה שבה מתמטיקאים שונים עונים לאותה שאלה. | |
|
|
|
|
|
||
|
||||
|
זה פשוט: עוזי עדיין מרצה, אלון כבר לא (נכון?). | |
|
|
|
|
|
||
|
||||
|
צודק. סליחה על האווילות. | |
|
|
|
|
|
||
|
||||
|
אז אולי תגיד, באמת, מהם "מודל", "נאותות", או "שלמות" (אם ב"שלמות" הכוונה היא למשהו אחר ממה שהגדיר אלון במאמר)? בקיצור, למה אתה מתכוון ב"חיבור לעולם"? |
|
|
|
|
|
|
||
|
||||
|
"שלמות" היא דווקא תכונה סינטקטית, שהוגדרה במאמר: היכולת להוכיח כל משפט (בשפה) או את שלילתו. "מודל": שים לב שבהגדרה של "שפה" עוזי הזכיר קבועים, פונקציות ויחסים. סינטקטית, אלו סתם סימנים: סימן-קבוע יכול להיות סימן כמו "0", סימן-פונקציה יכול להיות "+" (פונקציה דו-מקומית, שתמיד תופיע כשלאחריה שני ארגומנטים), סימן-יחס יכול להיות הסימן ">" (גם זה יהיה מן הסתם יחס דו מקומי), וכו'. מודל הוא קבוצה כלשהי M, פלוס התאמה של אובייקטים מתאימים לכל אחד מהקבועים, הפונקציות והיחסים: לכל סימן-קבוע נתאים איבר מסויים ב-M, לכל סימן-פונקציה נתאים פונקציה על הקבוצה M, לכל סימן-יחס נתאים יחס. למשל, המודל יכול להיות הקבוצה {שמש, ירח, כוכבים}, ולסימן "0" נתאים את האיבר "שמש", ולסימן "+" נתאים איזושהי פונקציה על הקבוצה הזו (למשל שמש+ירח=כוכבים, שמש+שמש=ירח, וכו'...), ליחס ">" נתאים את היחס "מי בא קודם באלף-בית" וכו'. כפי שרואים, אין בהכרח שום "קשר" בין איך שהסימנים נראים לפירוש שלהם במודל. אם יש אקסיומות בתורה (ובד"כ יש...), המודל הנ"ל כמובן נדרש לקיים אותן, כלומר שכל הנוסחאות בתורה יצאו *נכונות* כשנפרש אותן עפ"י המודל. אם, נניח, יש אקסיומה האומרת "אין אף x כך ש-x<0", המודל שתיארנו ייכשל, כי "0" זה "שמש" ו"ירח" קטן מ"שמש" (אלפביתית). "נאותות" היא התכונה שכל משפט היכיח בתורה הוא גם נכון (במודל). |
|
|
|
|
|
|
||
|
||||
|
תודה. שכחתי רק לשאול על "אמת". והאם המושגים האלה נקראים "חיבור לעולם"? |
|
|
|
|
|
|
||
|
||||
|
"אמת" היא נכונות במודל; לפעמים יש מודל "סטנדרטי" שאז שוכחים להזכיר אותו. הביטוי "חיבור לעולם" הוא משל ספרותי; הוא לא מקובל במיוחד, נדמה לי. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |