בתשובה לאלון עמית, 18/07/05 0:46
עוד זווית 317570
2. השערת הרצף? מן הסתם התכוונת ל"טענה אריתמטית".
עוד זווית 317578
נכון.
עוד זווית 317580
אפשר לנשום שוב.
אי הסכמה בין המתמטיקאים האמיתיים בדיון גרמה לי לחצים לא בריאים בחזה.
עוד זווית 317662
עקבתי אחרי הדיון בעיון רב. המון זמן לא קראתי משהו כלכך מעניין במתימטיקה. קראתי גם את ההגדרות של עוזי למטה (שמישהו שמבין במחשבים ייתן להם קישור פה!) שמאוד עזרו לי להבין את הדיון הזה. תודה.

לעיניינינו:
אלון - הדוגמה שנתת לי לפני שנים (אתמול) על הTwin-Pairs היא לא כלכך רלוונטית לויכוח - כי מה שהראת זה שיש פסוק שנורא קשה להוכיח אותו, וגם את שלילתו. זה נכון גם אם הוא *אמת על פי האקסיומות* וגם עם הוא *אמת אבסולוטית שנובע מהטבעיים*.
(לנו מספיק שהיית מניח שהשערת גולדבך נכונה. היה מספיק קשה להוכיח את זה). זה לא מכריע בין השניים.

אני רוצה לסכם איך אני מבין את הויכוח, כדי להיות ברור:

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

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

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

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

דברים שאני עדיין לא מבין:

קשה לי להבין מה זה "נכון אבסולוטית" במתימטיקה. אם תהיה מערכת אקסיומות עקבית שבה 2=34, אז 2=34 יהיה נכון, במערכת האקסיומות הזו. מה הבעייה בזה?

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

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

זהו. ארוך אבל מייגע :)
עוד זווית 318283
(כדי להבטיח שתגובה כזו תגיע אלי, ונראה שהיא היתה מופנית אלי, הכי טוב לשלוח אותה כתשובה לתגובה שלי).

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

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

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

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

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

"עוזי מאמין שZFC היא למשל מערכת אקסיומות שנקייה מדברים כאלו. כל פסוק בZFC כנראה שניתן להוכיח או אותו או את שלילתו"

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

"קשה לי להבין מה זה "נכון אבסולוטית" במתימטיקה"

אתה מאמין, למשל, ש*אם* מניחים את אקסיומות פאנו, *אז* יוצא ש-‏2+3=5? זה נכון אבסולוטית, או שגם בשביל זה צריך עוד אקסיומות?

"מכאן יוצא שכל קבוצת אברים המקיימים את PA מקיימים את כל התכונות של המספרים הטבעיים."

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

אפילו הפורמליסטים הכי קשוחים לא טוענים שהמספרים הטבעיים = מה שמקיים את PA. PA היא מערכת מאוד, מאוד חלשה בהקשר הזה.
עוד זווית 318355
אני יודע (ולא רק מאמין) ש- ZFC (מערכת האקסיומות של צרמלו-פרנקל, בתוספת אקסיומת הבחירה) אינה שלמה.

הדוגמא הידועה ביותר היא השערת הרצף, וזו הזדמנות נאה להסביר איך יתכן שהשערה כל-כך פשוטה תהיה לא כריעה, בתורה חזקה כמו ZFC.

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

במקום זה, צרמלו ופרנקל, בעקבות קנטור וחצי מהפילוסופים של ראשית המאה העשרים, פיתחו גישה אלטרנטיבית, הרבה יותר קונסטרוקטיבית. הם ניסחו מערכת של אקסיומות שהתוכן של כולן הוא, בקירוב, שבתנאים מסויימים קיימת קבוצה בעלת תכונות מסויימות. למשל, האקסיומה הראשונה קובעת שקיימת קבוצה שאין בה איברים בכלל ("הקבוצה הריקה").
לכל שתי קבוצות יש קבוצה שהיא האיחוד שלהן; לכל קבוצה קיימת "קבוצת החזקה", שכוללת בדיוק את כל תת-הקבוצות של הקבוצה המקורית, וכן הלאה. יש אקסיומה מיוחדת שאומרת שבהנתן קבוצה וכלל שבוחר איברים שלה, קיימת קבוצה שכוללת בדיוק את האיברים האלה. האקסיומות האלה מאפשרות לבנות גם קבוצות מסוג מיוחד שנקראות 'פונקציות'. פונקציה מקבוצה A לקבוצה B היא בסך-הכל *קבוצה* של זוגות סדורים (a,b) שבה לכל איבר a של A מתאים איבר יחיד של B. במערכת הזו (ולכן בכל המתמטיקה), כל דבר הוא קבוצה.

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

בסופו של דבר הוסיפו גם את 'אקסיומת הבחירה': בהנתן קבוצה I ופונקציה F מ- I לקבוצה כלשהי, קיימת פונקציה אחרת f מאותה קבוצה I, כך שהאיבר (f(i שייך לקבוצה (F(i. בניסוח קל יותר אומרים ש"בהנתן אוסף של קבוצות, אפשר לבחור איבר אחד מכל קבוצה" - המשמעות המדויקת של "אפשר" היא שקיימת *קבוצה* (פונקציה, במקרה הזה) שמממשת את ה"אפשרות" הזו.
זו אקסיומה פחות אינטואיבית (בין השאר אפשר להוכיח ממנה את פרדוקס בנך-טרסקי על התפוזים והשמש), אבל בכל זאת היא די מקובלת. למערכת הכוללת את אקסיומת הבחירה קוראים ZFC, ולזו שבלעדיה - ZF (על-שם צרמלו ופרנקל).

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

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

קנטור לא הצליח לבנות קבוצה אינסופית שעוצמתה תהיה מצד אחד גדולה משל N, ומצד שני קטנה משל PN. "השערת הרצף" שלו אומרת שאין כזו קבוצה. כלומר: כל קבוצה שלא ניתן לסדר, היא בהכרח גדולה מספיק כדי שאפשר יהיה לכסות באמצעותה את PN.
בניסוח מדוקדק יותר: אם A היא קבוצה כזו, שלא קיימת פונקציה מ- N המכסה את A, אז *בהכרח* קיימת פונקציה מ- A המכסה את PN.

*זו טענה על קיום של פונקציות*, כלומר על קיום של קבוצות.

מסתבר (משפטים של גדל, 1938, ופול כהן, 1963) שההשערה הזו אינה סותרת את שאר האקסיומות של תורת הקבוצות, אבל גם אינה נובעת מהן. פירושו של המשפט השני הוא שבארגז הכלים הנקרא אקסיומות ZFC, אין מספיק כלים כדי לבנות את הפונקציה מ- A על PN. לכן השערת הרצף אינה כריעה.
עוד זווית 318362
אני לא מתקדם, אבל מה ההגדרה המקובלת? קיום התאמה חח"ע ועל (ואז מה שאתה מתאר נובע ממשפט קנטור-שרדר-ברנשטיין שהוא לא מיידי, הרי קנטור לא הצליח להוכיח אותו), או משהו מתוחכם יותר?
עוד זווית 318387
כן, התאמה חח"ע ועל. כפי שציינת, השקילות בין שתי ההגדרות אינה טריוויאלית.

(למתעניינים: החידה הלא-פשוטה היא להראות שאם יש פונקציה מ-A ל-B המכסה את כל איברי B, ופונקציה אחרת מ-B ל-A המכסה את כל איברי A, אז יש עוד פונקציה (אולי) אחרת מ-A ל-B המכסה את איברי B ומתאימה לאיברים שונים מ-A איברים שונים ב-B).
תהא העוצמה איתך 318369
זאת הפעם השניה בעת האחרונה שאני נתקל בתופעה שיחס השויון מוגדר כתוצאה מהפעלת היחס "גדול שווה" בשני בכיוונים (הפעם הראשונה היתה באותו ספר של קונווי‏1), כלומר היחס היסודי יותר הוא "גדול שווה". זה עניין מקובל במתמטיקה?
__________
1- לא הבנתי הרבה, אבל את זה דוקא כן. גם את ההוכחה של המשפט האחרון בספר הצלחתי להבין.
תהא העוצמה איתך 318394
ביסודות המתמטיקה זו גישה די שכיחה (בעוצמות, במספרים-משחקים של Conway, אפילו בשוויון בין קבוצות שמוגדר לפי הכלה בשני הכיוונים). גם אחר-כך זה קורה לא מעט (כי בדרך כלל התכונה של 'להיות גדול לפחות כמו' היא יותר פשוטה מאשר 'להיות גדול בדיוק כמו'), אבל מצד שני 'איזומורפיזם' הוא מושג מאד שכיח (שפירושו שמדובר בשתי מערכות שוות), ולא נראה לי שיש העדפה פילוסופית לאחד הצדדים.

(זוהי השורה האחרונה בהודעה הזו).
תהא העוצמה איתך 318395
לתוהים: המשפט האחרון בספר של קונווי הוא:

"Theorem 100. This is the last theorem in this book.

(The proof is obvious)"
תהא העוצמה איתך 318456
הקטנתי את החלון, ולא הצלחתי להבין את המשפט האחרון שלך.
(סתם.)
תהא העוצמה איתך 318397
זה די מקובל, פשוט כי "שוויון" (או סוגים אחרים של שקילות) מבטא איזושהי תכונה סימטרית בין A ל-B, המתקיימת כאשר משהו קורה בין B ל-A וגם בין A ל-B. למשל, בתורה שעוזי דיבר עליה (ZFC), קבוצות הן שוות בדיוק כאשר יש להן אותם איברים (זו אחת האקסיומות); לכן, כשרוצים להוכיח זהות בין שתי קבוצות בהינתן מידע על האיברים שלהן, מראים שכל איבר של A הוא גם איבר של B, ואז שכל איבר של B הוא גם איבר של A - במילים אחרות, ש-A מוכלת ב-B וגם ש-B מוכלת ב-A.
עוד זווית 318375
"כל קבוצה שלא ניתן לסדר" - אתה מתכוון, כל קבוצה שלא ניתן לסדר בלי אקסיומת הבחירה, לא?
עוד זווית 318388
לא. הוא מתכוון "כל קבוצה שלא ניתן למנות", כלומר לכסות אותה ע"י פונקציה מהטבעיים N; אין הכוונה ל"לסדר סדר טוב" (שאת זה, עם אקסיומת הבחירה, אפשר תמיד לעשות, ואני מניח שמכאן השאלה).
עוד זווית 318405
אכן, תודה.
עוד זווית 318379
''הפרדוקס של ראסל הראה שזו גישה מאד לא מוצלחת'' זה ניסוח קצת גס, הרי העובדה שהשתמשו בגישה הזו כל כך הרבה שמן מראה שזאת דווקא גישה מוצלחת למדי, אולי לא מושלמת, אבל בכל זאת מוצלחת.
עוד זווית 318391
אבל לא השתמשו בגישה הזו כל כך הרבה זמן. מתמטיקאים התחילו להתייחס ברצינות למושג הכללי "קבוצה" רק ממש באותה תקופה; לפני כן דיברו רק על "מספרים" (ממשיים, מרוכבים, טבעיים) ועל קבוצות של מספרים, וכאן הבעייה אינה נוצרת כלל וכלל: יש אבחנה ברורה בין עצמים לקבוצות-של-עצמים, ובפרט אין דבר כזה בכלל שקבוצה תהווה את אחד מהעצמים שלה.

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

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