בתשובה לאלון עמית, 15/08/03 18:42
 |
|
 |
||
|
||||
 |
אקסיומות פאנו (Peano) מקובלות למדי, ובהחלט מספיקות כדי לנסח את השערת גולדבך. האקסיומות, בשפה לא-פורמלית, הן בערך כדלהלן (המושגים היסודיים כאן הם "מספר" ו-"עוקב"): 1. אפס הוא מספר 2. לכל מספר יש עוקב, שהוא גם מספר 3. אפס איננו עוקב של שום מספר 4. שני מספרים שעוקביהם שווים, שווים בעצמם 5. אם S קבוצה של מספרים המכילה את 0 וכן מכילה את העוקב של כל מספר שנמצא בה, אז S מכילה את כל המספרים. בפרשנות הטבעית של אקסיומות אלו המושג "מספר" הוא כמובן מה שאנחנו קוראים "מספר טבעי (כולל אפס)", וה-"עוקב" של מספר הוא המספר ועוד אחד. אקסיומה 5 היא כמובן אינדוקציה. לא מאוד קשה להגדיר על-סמך אקסיומות אלה סוגים אחרים של מספרים (שליליים, רציונליים) וכן פעולות חשבון כמו חיבור וכפל. חיפוש "אקסיומות פאנו" בגוגל יניב עוד הרבה מידע. האפשרות שהשערת גולדבך איננה יכיחה במסגרת אקסיומות אלה בהחלט קיימת, ויש כבר טענות אחרות שידוע שהן במצב המוזר הזה. |
 |
 |
 |
|
|
|
||
|
||||
|
כדאי לציין כי לו יתברר מחר שהשערת גולדבך אינה תלויה באקסיומות פאנו (כלומר לא ניתן להוכיחה או להפריכה) הרי שמיד היינו מקבלים ''הוכחה'' שההשערה נכונה. זאת מכיון שאין לה דוגמא נגדית במודל הסטנדרטי של המספרים הטבעיים ולכן ברור שנרצה לאמץ אותה כאקסיומה נוספת. מבלבל, אבל נכון. יתר על כן, משהו דומה כבר קרה עם משפט ידוע הרבה פחות בתורת רמזי. אם יהיה ביקוש אכתוב על כך. |
|
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
בוא ונראה, משפט רמזי אומר כי לכל n,k קיים m כך שלכל צביעה ב-k צבעים של קשתות הגרף המלא על m קודקודים (K_m), יש תת-קבוצה של הקודקודים בגודל n לפחות כך שכל הקשתות ביניהם צבועות באותו הצבע. עכשיו בוא נניח שכשאנחנו מסתכלים על K_m הקודקודים ממוספרים מ-1 עד m. נקרא לתת-קבוצה של הקודקודים מהוללת אם גודל הקבוצה גדול ממספרו של הקטן בקודקודיה. משפט פריס-הרינגטון (Paris-Harrington) אומר כי לכל n,k קיים m כך שלכל צביעה ב-k צבעים של קשתות הגרף המלא (והממוספר) על m קודקודים (K_m), יש תת-קבוצה מהוללה של הקודקודים בגודל n לפחות כך שכל הקשתות ביניהם צבועות באותו הצבע. המשפט הזה הוא נכון (אולי אתן תמצית ההוכחה אח"כ) אבל אינו יכיח מאקסיומות פאנו, כי הוא גורר את עקביותן. |
|
|
|
|
|
|
||
|
||||
|
משפט פריס-הרינגטון אינו, כמובן, המשפט דלעיל, אלא הוא אומר שהכללת משפט רמזי הנ''ל נכונה אבל לא יכיחה מאקסיומות פאנו. |
|
|
|
|
|
|
||
|
||||
|
חשבתי לכתוב באריכות על הסיפור המופלא והלא-ייאמן של סדרות-גודסטין, אך החלטתי שאלף יהיה לי קשה לרשום בצורה קריאה את ההגדרה בטקסט-אדיטור הזה, ובית שהכל מוסבר כל-כך יפה בלינק למטה, אז למה להתאמץ? טיזר: גודסטין מגדיר פעולת "בעיטה" על מספרים טבעיים שלכאורה מגדילה אותם בצורה שקשה לתאר. אח"כ הוא מוכיח שאם מתחילים ממספר נתון, בועטים בו, מורידים 1, בועטים שוב, מורידים 1, וכן הלאה, תמיד מגיעים בסוף ל-0. אחרי שרואים את ההגדרה של בעיטה, פשוט אי אפשר להאמין לזה. ואז מגיע שוק מספר שתיים: לא רק שזה המצב, אלא שזה לא יכיח באקסיומות פאנו. מדובר בעובדה (לכאורה) פשוטה להחריד, אך מסתבר שצריך אורדינלים קצת יותר גדולים מאומגה בשביל להוכיח אותה. הנה הלינק, ואפילו שזו מין מצגת, אפשר בקלות לעקוב ולהבין. ולא צריך להכיר אורדינלים. באמת כיף: |
|
|
|
|
|
|
||
|
||||
|
הבנתי הכל, עד שקף 12 באמצע: למה הוא אומר שזו סידרה סופית של סודרים? |
|
|
|
|
|
|
||
|
||||
|
כל סדרה יורדת של סודרים היא סופית! (אחרת, התבונן בסודר הקטן ביותר שממנו מתחילה סדרה יורדת אינסופית; מן הסודר השני בסדרה יכולה להתחיל רק סדרה סופית). | |
|
|
|
|
|
||
|
||||
|
אני לא הבנתי משהו אחר: בשקף http://www2.maths.bris.ac.uk/~maadb/research/seminar... , בו הוא מציג את האקסיומות, למה צריך את אקסיומה 5 (הכפל באפס)? הרי מאקסיומה 3 אני מכפיל את שני האגפים באיקס (מותר לי, מאקסיומה 6), מצמצם משניהם איקס בריבוע, ומקבל את 5. או שאסור לי לצמצם? מה אני מפספס? (את שאר הטיעונים שלו, אבל לא חשוב כרגע). | |
|
|
|
|
|
||
|
||||
|
איך 6 מאפשרת להכפיל ב-x את אגפי 3? | |
|
|
|
|
|
||
|
||||
|
אני חושב שאתה צודק, ולא טוענים שאוסף האקסיומות הזה הוא מינימלי. כדי לעשות את מה שאתה מציע צריך ראשית להוכיח כמה דברים באינדוקציה (למשל את חוק הפילוג, ואת היכולת לצמצם, כלומר שמ-A+C = B+C אפשר להסיק ש-A=B). אם אני לא מחמיץ משהו, אפשר לעשות את זה, אבל זה לא משנה במיוחד. אילו משאר הטיעונים שם אתה מפספס? |
|
|
|
|
|
|
||
|
||||
|
לא הבנתי. אתה לא טוען פה טיעון מעגלי? אתה אומר לי: 1. נניח בשלילה שיש סדרת סודרים יורדת אינסופית. 2. אם מסתכלים על הסידרה מאיברה השני מקבלים סידרת סודרים יורדת. 3. הסדרה ב-2 חייבת להיות סופית. על סמך מה אתה אומר את 3? |
|
|
|
|
|
|
||
|
||||
|
הסדרה (החל מן האיבר השני) חייבת להיות סופית, מכיוון שהאיבר הראשון שלה קטן מכדי להתחיל סדרה אינסופית (כך הרי בחרנו את האיבר הראשון בסדרה שלנו - זהו הסודר *הקטן ביותר* שיכול לפתוח סדרה יורדת אינסופית; האיבר השני בסדרה קטן ממנו, ולכן אינו יכול לפתוח סדרה כזו). | |
|
|
|
|
|
||
|
||||
|
ומה אם כל הסודרים בסדרה מייצגים קבוצות אינסופיות? אה - כיוון שכל קבוצת סודרים סדורה היטב, יש איבר קטן ביתר איפה שהוא בסדרה, והאיבר שמופיע אחריו בסדרה חייב לייצג קבוצה סופית. תודה. |
|
|
|
|
|
|
||
|
||||
|
למעשה, אתה מציע הוכחה קצרה יותר: בכל קבוצת סודרים יש איבר מינימלי, ולכן היא אינה יכולה להיות סדרה יורדת (הנקודה היא לא שהסודר "הבא" מייצג קבוצה סופית (אז מה?) אלא שלא יכול להיות סודר אחרי הקטן ביותר). | |
|
|
|
|
|
||
|
||||
|
למה קבוצה אינסופית של סודרים בעלת איבר מינימלי איננה יכולה להוות סדרה יורדת? במידה ויש כזו סידרה ללא איבר מינימלי, תמיד אפשר להוסיף לה איבר ולהגדירו קטן מכולם. | |
|
|
|
|
|
||
|
||||
|
כלומר, ברור לי שאין סדרה אינסופית יורדת, אבל דווקא ההוכחה שנתת היא הנכונה. אי אפשר לפסול את היותה של קבוצה בת-מניה של סודרים סדרה יורדת רק משום שיש לה איבר מינימלי (W+1 זו סדרה אינסופית עולה עם איבר מקסימלי, ועם סדר טוב "הפוך" היינו מקבלים אותו דבר רק עם מינימלי.) | |
|
|
|
|
|
||
|
||||
|
ההוכחה של יוני בסדר גמור. נזכיר שאנחנו רוצים להוכיח שאין סדרה אינסופית יורדת של סודרים (וכאן הסדר כבר מוגדר - אי אפשר להפוך אותו סתם כך; ממילא הסדר ההפוך אינו סדר טוב - כי יש קבוצות של סודרים בלי איבר מקסימלי). הוכחה: לסדרה אינסופית יורדת אין מינימום (שהרי אחרי כל איבר בא איבר קטן ממנו), מש"ל. (כלומר - ההנחה שקיימת סדרה אינסופית יורדת, סותרת את העובדה הידועה שלכל קבוצה של סודרים יש איבר מינימלי). |
|
|
|
|
|
|
||
|
||||
|
אני גם לא מבין את ההוכחה הקצרצרונת. איך מ-"סדרה אינסופית יורדת" אתה מסיק "אחרי כל איבר בא איבר קטן ממנו"? אין ספק שסדרת סודרים לא יכולה להיראות כמו 1 > 1/2 > 1/3 > 1/4 > ... > 0 אך אני לא רואה איך הנימוק החדש מראה זאת (לעומת הנימוק המקורי, שכן הראה).
|
|
|
|
|
|
|
||
|
||||
|
כי הסדרה *יורדת*? (ההוכחה קצרה, אבל אולי צריך לנסח באריכות את הטענה. על הסודרים מוגדר סדר טוב; הטענה היא שכל סדרה יורדת של סודרים, כלומר a_1 > a_2 > a_3 > ... > a_n > ... מוכרחה להסתיים.)
|
|
|
|
|
|
|
||
|
||||
|
כשהיה ההוגה שלי בשנה א' באוניברסיטה ולמד במסגרת קורס בפיזיקה קלאסית את חוק יד ימין, המרצה הסביר שמעכשיו, בגלל שהחליט ללמוד פיזיקה, הוא יצטרך לשחק הרבה עם הידיים. מספר שעות מאוחר יותר, בחוג התעמלות קרקע בריאותית מעורב ניגשה אליו סטודנטית מצודדת ופתחה בשיחה קולחת ומרתקת בנושא במבחר חוגי הספורט הפתוחים בפני סטודנטים במינים שונים. כשבמהלך השיחה הזכיר ההוגה כדרך אגב שהוא לומד פיזיקה מדעי המחשב (בתקוה שהיא תתרשם מכך, דבר ידוע הוא שסטודנטיות מתות על גברים עם נטיה מדעית ונגיעה בתחום המחשבים) היא מיהרה לסיים את השיחה בשל פגישה עם החבר המתאגרף שלה. רק אז הבין הוגי את המשמעות האמיתית של אותה אמירה שהוזכרה בתחילת התגובה. למה אני מספר לכם את זה? כי מאז שהלכתי לעולמי מתקשה הוגי בדיכוי הצד האינפנטילי של אישיותו. והצד הזה דורש ממנו להתייחס לאיברים המסודרים לפי גדלם והסדרות היורדות החוזרים ומופיעים בדיון זה. ההקשר של ביטויים המוצאים מהקשרם וגורמים לסטודנטים אינפנטיליים לצחקק במבוכה ניראה לי מתאים. עם המערכת סליחה. קחו את רשותי להסיר תגובה זו עם הופעתה (כיוון שהזכרתי הסרת תגובה הפתיל הלא מתאים, אף סיפקתי לכם את התירוץ המושלם לעשות זאת). |
|
|
|
|
|
|
||
|
||||
|
אוי ווי. היה מאוחר, הייתי עייף, אכלו לי שתו לי. אני (וכנראה גם אלון) בלבלתי בין "קבוצה אינסופית" אשר בהחלט יכולה להיות סדורה ליניארית ובעלת איבר מינימלי, לבין סדרה אינסופית (אלון: בסדרה אינסופית לאיבר 0 חייב להיות אינדקס.) יורדת, כך שאכן זו הוכחה לגיטימית למהדרין. רק נותר לקוות שגיטיק לא קורא את האייל. |
|
|
|
|
|
|
||
|
||||
|
מה אני אגיד... אני פשוט טמבל. אני יכול להיכנס להסבר ארוך על מה היה לי בראש, אך בוודאי עדיף שפשוט אצטנף בפינה. | |
|
|
|
|
|
||
|
||||
|
חבר'ס מה קרה לכם עם הסדרות היורדות של סודרים. הנה הוכחה מדוייקת שאין כאלו אינסופיות יורדות: קחו את הסודר הראשון בסדרה. אז כל השאר מהווים תת-קבוצה שלו (כי קטן בסודרים פירושו שייך, וסודרים הם טרנזיטיביים ביחס לשייכות). וכיון שסודר *בהגדרה* הוא קבוצה סדורה היטב ע"י קטן (כלומר שייכות), יש בקבוצה הנתונה, ולכן בסדרה כולה, איבר קטן ביותר. למי שיש חורים בהשכלה (כמוני) מומלץ לקרוא את "החלום של קנטור" מהאתר של בועז מבר-אילן ( http://www.cs.biu.ac.il/~tsaban ). אגב סדירות היטב שקולה להנחה שאין סדרה אינסופית יורדת אם מניחים את אקסיומת הבחירה (או גירסה מוחלשת שלה שמאפשרת בדיוק לבנות את הסידרה האינסופית היורדת, שנקראת "בחירה מותנית"). שמע מינה. |
|
|
|
|
|
|
||
|
||||
|
לא ברור לי עד כמה היו נחוצים הכותרת והפתיחה השחצניים שבחרת. במעלה הפתיל ניתנו שתי הוכחות מצויינות לטענה (שרשרת יורדת של סודרים חייבת להסתיים), וההוכחה שלך (השלישית) אינה נבדלת מהן במיוחד בפשטות או הדיוק שלה. | |
|
|
|
|
|
||
|
||||
|
למרות שתגובתי באה באיחור רב של כמה חודשים...נראה לי שניתן להוכיח בפשטות יחסית את התכנסותן של סדרות גודסייו בקבוצת הטבעיים N.... כי פעולת החיסור של 1 כל הזמן "מכרסמת בספרת האחדות שעליה לא חלה ה"בעיטה" כלפי מעלה...ואז כשנגמרת ספרת האחדות ... החיסור של 1 פועל על החזקה הבאה ומין הסתם מוריד את החזקה הזאת ב 1...ולכן באינדוקציה פשוטה בתוך הטבעיים אפשר להראות שכל הסדרות אכן מתכנסות ל 0. אינני אומר שההוכחה שהבאת חסרת ערך חלילא מאחר והיא מדברת על התכנסות גם בסודרים שאינם סופיים...ובכל זאת את התדהמה אפשר להסביר באמצעים הרבה יותר טריביאליים | |
|
|
|
|
|
||
|
||||
|
ההוכחה שהבאת איננה מוצלחת, חוששני. ראשית היא לא ברורה (מה זה "פועל על החזקה הבאה", מה זה "מוריד את החזקה הזאת ב 1", ומהי האינדוקציה הפשוטה?). כמו כן, כל העוקץ כאן הוא ש*הוכיחו* שלא ניתן להוכיח שהסדרות מתכנסות לאפס באינדוקציה פשוטה על הטבעיים, כלומר במסגרת אקסיומות פאנו. ההוכחה עם הסודרים לא מובאת כדי להראות משהו יותר חזק, היא מובאת על-מנת להוכיח את המשפט על הטבעיים עצמם - הסודרים ממש נחוצים בשביל זה. לכן את התדהמה לא ניתן להסביר באמצעים כל-כך טריוויאליים. |
|
|
|
|
|
|
||
|
||||
|
אתה צודק! אני רק התרשמתי אינטואיטיבית שזו הסיבה להתכנסות הסדרות...ייתכן מאד שלא ניתן להשתמש באינדוקציה פשוטה...תוך כדי לקיחת הסיכון המחושב שאצטרף לקבוצת הטרחנים.. :-) .אנסה לנסח את טענתי באופן יותר מסודר....מה שהבאתי איננו הוכחה בשום אופן...רק כיוון כללי להוכחה וגם זה בספק...אשר לשאלתך....בייצוג של בסיס b למספר n ... בקצה הימני מופיע הגורם שאני קורא לו ספרת האחדות...בהנחה שהייצוג מסודר כשהחזקה הגבוהה ביותר של b היא הגורם השמאלי ביותר ... אז מייד משמאל לספרת האחדות נמצאית "החזקה הבאה" או ספרת "העשרות" אם ספרת העשרות איננה 0 במקרה....אז נכון שכל איטרציה מגדילה את המספרים בחזקות לגדלים מדהימים...אבל היא לא פועלת בכלל על ספרת האחדות...וכך ספרת האחדות נשחקת ל 0 ואז החיסור של אחד גורע מספרת "העשרות" ושוב נשארת לנו ספרת אחדות גדולה מאד...אבל גם היא תישחק בעוד מספר סופי של צעדים...וכו' וכו'...ובסופו של דבר הכירסום הזה מסתבר יותר חזק מהבעיטה המרשימה... אם תנסה את הסדרה עבור nים קטנים תראה בדיוק למה אני מתכוון. בדרך כלל כאשר הרציונאל ברור לנו לחלוטין כמו במקרה הזה...הדרך להוכחה באמצעים פשוטים היא קרובה...זה לא המקרה של גולדבאך או אפילו של פרמה שהן בעיות שבהם האינטואיציה שלנו לא מבינה למה זה ככה...כאן זה נשמע לי הגיוני מאד. |
|
|
|
|
|
|
||
|
||||
|
כשהייתי בודק תרגילים, הייתי מקיף את המלה הזו בעיגול וכותב (באדום) שזה בדיוק מה שהיה צריך להוכיח. | |
|
|
|
|
|
||
|
||||
|
אני צריך לזכור את זה. (דובי, שכנראה יהיה מתרגל בשנה הבאה, ואתמול בדק עבודה (במסגרת ''בדיקת עמיתים'' באחד הקורסים) והזדעזע עד עמקי נשמתו השטחית) |
|
|
|
|
|
|
||
|
||||
|
וכשאני הייתי מתורגל, הקיף לי מתרגל את הביטוי "ומכאן קל להראות" והוסיף "אז תראה!". | |
|
|
|
|
|
||
|
||||
|
וכשאני כתבתי על משהו ''ברור ש-'', הקיף לי המתרגל את המילים, ולידם כתב דוגמא נגדית. רק כדי לתקן את רושם ה-''המתרגלים פלצים'' שעלול להתקבל מכל הדוגמאות האלה. הכל מוצדק. |
|
|
|
|
|
|
||
|
||||
|
התלמיד כותב את הנתון, כותב אותו שוב תוך שינוי מינורי, מוסיף "ומכאן נובע ש.." ומסיים במה שהיה צריך להוכיח. בדרך כלל יבואו אחרי טקסט כזה: א. הסבר מילולי ומבובלבל למה זה נכון ב. ציטוט כמה משפטים לא-רלוונטיים מהספר ג. דוגמא שמראה שהטענה נכונה עבור n=3 ד. כל השלושה. |
|
|
|
|
|
|
||
|
||||
|
נו, ספר, אתה הרי רוצה לספר. ממה הזדעזעת? | |
|
|
|
|
|
||
|
||||
|
עזוב, לא נכנס לזה. (דובי, שכבר לא זוכר) |
|
|
|
|
|
|
||
|
||||
|
בעסה איתך. | |
|
|
|
|
|
||
|
||||
|
טוב הנה משהו שעושה עוד צעד לכיוון של הוכחה פורמלית וסדורה... נניח שסדרת גודסטיין מתכנסת ל 0 לכל מספר טבעי הקטן או שווה ל n ונתבונן במקרה ה n+1 ...וזאת לאחר שהראנו כי סדרת גודסטיין של n=2 ו של n=3 ולמהדרין גם n=4 אכן מתכנסת ל 0. (אינדוקציה פשוטה) האיבר הראשון של סדרת גודסטיין של n+1 הוא הייצוג של n+1 בבסיס 2 האיבר השני הוא מספר בבסיס 3 שבו החלפנו כל מופע של 2 ב 3 וכך האלה והלאה. לצורך הפשטות והבהירות...נסדר את כל הייצוגים כך שהחזקה הגדולה ביותר של הבסיס התורן נמצאית בצד שמאל, ואחריה כל החזקות בסדר יורד עד שבצד הימני ביותר נמצאית חזקת 0 של הבסיס הלא היא ספרת האחדות. אני אכנה ברשותכם את האיבר שמייד משמאל לספרת האחדות בשם "ספרת העשרות". אינני מניח שאיבר הראשון חייב להיות הייצוג של n+1 בבסיס 2 דווקא...ייתכן שהתחלנו בבסיס שרירותי b כלשהו....בכל אופן בייצוג זה, ספרת האחדות היא מספר טבעי וסופי בהחלט, ומאחר ובכל צעד של בעיטה לגבהים מסחררים, הבעיטה איננה פועלת על ספרת האחדות, הרי שבהחסירנו אחד ממנה, ברור שלאחר מספר סופי! של צעדים תתאפס ספרת האחדות...ואז יהיה עלינו להחסיר אחד ממה שכניניתי ספרת העשרות. נסמן כאן את מספר הצעדים שביצענו עד כה ב k . בהגיענו לשלב מכריע זה נצטרך להזכר במה שלמדנו בכיתה ב' לגבי חיסור...אם נניח כי בשלב זה יש בידנו מספר המיוצג בבסיס שנסמן אותו b' הרי שספרת העשרות שלנו היא איבר שנראה כך: ספרה בבסיס b' שנסמן אותה C (המקדם) מוכפלת בחזקה של b' נסמן את החזקה הזאת ב j. כלומר האיבר שלנו נראה כך: C כפול b' בחזקת j וכמו שלימדה אותה המורה שרה ביסודי....עלינו לחסר 1 מ C ועכשיו להוסיף "תשיעיות" לכל החזקות שמ j-1 ועד חזקת 0 מין הסתם במילה "תשיעיה" אני בעצם מתכוון לספרה הגדולה ביותר בבסיס b' הלא היא b'-1 אם כן בשלב הזה אני יכול בעצם לחלק את המספר שלי לשני חלקים....השמאלי שהוא כל החזקות הגדולות מ j כולל חזקת j והימני שהוא כל האיברים שהם מקדמים עם חזקות של b' עד החזקה j-1. שני החלקים האלה בייצוג הגודסטייני שלהם ניתנים לרגרסיה של K צעדים....כאשר כל מופע של b' אני אחליף במופע של הבסיס הראשון בסדרת גודסטיין .... ולקבל מהם ייצוג בבסיס b של מספרים הקטנים בעליל מ n+1 .... כלומר החל מנקודה זו ואילך סידרת גודסטיין של n+1 בחלקה הימני זהה לסדרת גודסטיין של מספר קטן מ n+1 ובחלקה השמאלי גם כן זהה לסדרת גודסטיין של מספר אחר אבל שגם הוא קטן מ n+1...ולגבי שני אלה יש לנו את הנחת האינדוקציה שהם מתכנסים ל אפס.....וסכום שתי סדרות המתכנסות לאפס יוצא די קרוב לאפס לא ? |
|
|
|
|
|
|
||
|
||||
|
בהנחה לא לגמרי מבוססת שהבנתי את כל היתר, למה שהחלק השמאלי יהיה קטן מ-n+1? בזמן שאתה מחכה שספרת האחדות תדעך, החלק השמאלי גדל מאוד. גם את החלוקה לחלק ימני ושמאלי לא לגמרי הבנתי. האם היא נקבעת במספר הראשון, או משתנה כל הזמן? (הרי ספרות חדשות נוצרות בכל פעם שיש "underflow" בחיסור, כלומר כשנוספים 9-ים). |
|
|
|
|
|
|
||
|
||||
|
אני עוצר כבר ב underflow הראשון שקורה אחרי k צעדים...ואני אומר שכל החלק השמאלי שעדיין לא "נפגע" מהכרסום הוא ניתן לרגרסיה אחורה של k צעדים פשוט נחליף כל מופע של b' במופע של b...ואז הוא זהה לחלק השמאלי של הייצוג בבסיס b שהוא הבסיס הראשון שלנו....מאחר ויש לי רק חלק מהאיברים שהיו לי כשייצגתי את n+1 בבסיס b אזי אני מתבונן בייצוג לפי בסיס b של מספר הקטן בהכרח מ n+1 ועליו חלה הנחת האינדוקציה |
|
|
|
|
|
|
||
|
||||
|
נניח, כמו שאמרת, שכבר הוכחנו שסדרות גודסטין המתחילות ב-2, 3 ו-4 מתכנסות ל-0. הבה ננסה להפעיל את ההוכחה שלך על הסדרה שמתחילה ב-5. האיבר הראשון הוא base 2: 5 = 2^2 + 1 באיבר השני ספרת היחידות נעלמת:base 3: 3^3 (= 27) ועכשיו מתרחש ה-underflow:base 4: 3*4^3 + 3*4^2 + 3*4 + 3 (= 255) איפה ואיך אתה מנסה להיעזר בהנחת האינדוקציה? איזה מספר אתה "מסיג לאחור" וטוען שעבורו כבר הוכחת? שים לב ש-3^3 *איננו* חלק מסדרת גודסטין של 4, אז אינני רואה איך תוכל לטעון שאתה כבר יודע לגביו משהו. נכון שאם אתה מחליף בו כל 3 חזרה ל-2 אתה מקבל 4, אבל... אז מה? איך אתה מסיק (בהנחה שאתה יודע שהסדרה ל-4 מתכנסת) שהסדרה ל-27 מתכנסת?אם אתה מסתכל *אחרי* ה-underflow, כלומר על המספר האחרון, החלק השמאלי שלו גדול מ-4 גם אם אתה מחזיר בו את הבסיס מ-4 ל-2. |
|
|
|
|
|
|
||
|
||||
|
אתה צודק את החלק הימני של הביטוי אין לי למה להשוות... המקרה שבו מתחילים בבסיס 2 הוא קצת מצחיק...כי בבסיס 2 ספרת האחדות היא מאופסת או שהיא 1 ... ואז ה underflow הראשון מתרחש בצעד הראשון או בצעד השני...וגם במקרה ש n=5 לא נשאר שום "חלק שמאלי" כי החזקה הגבוהה ביותר מתכרסמת ואין על מה להפעיל את הרגרסיה...במקרה של n=5 נשאר רק חלק ימני...והוא הרבה יותר מסובך כי אין למה להשוות אותו....למרות שאינטואיטיבית הוא החלק היותר קטן ... מאחר ואינני טרחן כפייתי ולפחות אני משתדל שלא להיות...אפנה אליך רק כשתהייה לי הוכחה סדורה כהלכה...אלא אם כן תאמר לי שבוודאות חבל על הזמן שלי ... ואין שום סיכוי לזה...חשבתי אולי לנסות להוכיח זאת על ידי בניית סדרות גודסטיין "מעוכבות" שבהן אנחנו מתחילים לחסר אחד רק החל מהצעד ה b ... כדי שתהיה זהות גבוהה יותר בין האברים...בכל אופן תודה על הבקורת עד עכשיו. |
|
|
|
|
|
|
||
|
||||
|
אחת הדרכים המוצלחות ללמוד משהו לעומק היא לנסות להתמודד עם דברים שנראים לך אחרת ממה שמספרים. אני אומר לך בוודאות שאין הוכחה פשוטה (כלומר, במספרים הטבעיים ללא סודרים, עם או בלי אינדוקציה) לטענה שאנו דנים בה, אך ייתכן מאוד שתצליח להבין את התנהגות סדרות גודסטין טוב יותר אם תנסה לבנות את ההוכחה שאתה מדבר עליה ולנסות להבין בדיוק איפה היא נופלת. רק שים לב שהמקרה בו מתחילים בבסיס 2, מצחיק או לא, הוא בדיוק המקרה בו מדובר, ע"פ ההגדרה של סדרות גודסטין. כמו כן, אינני בטוח שתוכל להרוויח משהו מהסדרות ה"מעוכבות" שהזכרת - אולי תוכיח משהו לגביהן, אך אלו אינן הסדרות שגודסטין הגדיר. בהצלחה, ותרגיש חופשי להמשיך לשאול. |
|
|
|
|
|
|
||
|
||||
|
אני אמנם מגיב על משהו פרה-היסטורי, אבל הדיון מרתק אותי ואני לא מבין משהו מאוד מאוד חשוב בשקפים: הטענה הייתה(בשקף 16 אם אני לא טועה) שמשפט גודסטין הוא "פסוק גדל", במובן שהוא פסוק לא יכיח מאקסיומות PA, אבל בניגוד לפסוק העמום שגדל מוכיח את קיומו (אך לא מבהיר מהו), זהו פסוק מעניין ונהיר על תורת המספרים. אם אכן זה כך, זהו צעד משמעותי בהכנסת הלוגיקה למרכז הדיון המתמטי, שכן עד כה כולם חשבו שהדיונים האלה הם דיונים גבוהים במטהמתמטיקה (או בפילוסופיה של המתמטיקה) שלא מענינים את חיי היומיום המתמטיים. עד כאן, ציונות. וכעת למה שלא הבנתי: מאיפה הוא הסיק (טענה ראשונה בשקף 16) שנכונות משפט גוסטין שקולה לכך שניתן לבצע אינדוקציה טרנספיניטית עד אומגה אפס במסגרת PA? האם מהעובדה שאפשר להוכיח את משפט גודסטין באמצעות סודרים גבוהים מPA, נובעת הטענה שלא ניתן להוכיח זאת מבלי להשתמש בסודרים גבוהים כל כך? אולי אלי צודק בעקרון (לא בפיתוח ההוכחה) ואכן ניתן להוכיח את משפט גודסטין באמצעים פשוטים תחת ההנחות של PA? אנא, אם יש משהו שמבהיר את המסקנה הזאת - שסתם ככה כתובה בשקף ללא הסבר - אז מאוד אשמח לקבל את ההבהרה הזאת. כמו שאמרתי למעלה, לדעתי זוהי התקדמות בהבנת משמעות המשבר של משפטי גדל ושילובו בתוכניות מתמטיות רחבות היקף. |
|
|
|
|
|
|
||
|
||||
|
גיגול קצר מצא את התוצאה הבאה: לא קראתי, ואני לא בטוח שאני כבר מסוגל לקרוא, אבל תן לזה בדיקה. |
|
|
|
|
|
|
||
|
||||
|
כמה הערות: ראשית, הפסוק המופיע במשפט גדל איננו "עמום", אלא מפורש לגמרי. למעשה זה לא פסוק אחד, אלא מתכון לרקיחת פסוק מתאים בכל מערכת פורמלית חזקה מספיק. אתה צודק בהחלט שהפסוק של גודסטין הוא הרבה יותר קונקרטי, רק שים לב שהוא מתאים ל-PA בלבד. PA היא מערכת חלשה למדי. בעיקר מסיבה זו, אני לא בטוח שאני מסכים לטענה שמשפט גודסטין משנה משהו מהותי בנקודת המגע שבין לוגיקה למתמטיקה "יומיומית". טענה "טבעית" בתורת המספרים שהיא בלתי-תלויה ב-ZFC היתה, אולי, מחוללת מהומה רבה יותר. אנשי תורת המספרים אינם נוטים להגביל עצמם ל-PA, ואני חושב שרק מיעוטם מתעניין באמת בשאלה האם משפטים מסויימים יכיחים ב-PA או לא. ככל הידוע לי, אפילו שיטות בסיסיות כמו contour integrals אינן ניתנות לניסוח ב-PA, ולאף אחד זה לא מפריע. אם אתה מתעניין, יש ספר של Stephen Simpson הדן בגבולות היכולת של מערכות פורמליות שונות. לשאלתך: הטענה שאינדוקציה עד אומגה אפס *הכרחית* כדי להוכיח את משפט גודסטין אכן איננה מוכחת בשקפים. זה משפט מסובך יותר, שאפשר ללמוד עליו (למשל) בקישור שנתן גדי. אבל - זה משפט, לא ניחוש שמסתמך רק על העובדה שאפשר להוכיח את הטענה *עם* שימוש בסודרים (ברור שזה לא נימוק). על כן, אלי מחפש דבר שאינו בנמצא. אין הוכחה למשפט גודסטין ב-PA, ואותו דבר נכון גם ל"משחק ההידרה" הנדון באותם שקפים. הערה אחרונה: שים לב ש*יש* טענה "על מספרים טבעיים" שאינה תלויה ב-PA ואף לא ב-ZFC ואף לא במערכות חזקות עוד יותר (אקסיומות "קרדינלים גדולים" לסוגיהן). זו, כמובן, השערת הרצף. כיוון שהיא אינה עוסקת ישירות במספרים הטבעיים, אלא בתת-קבוצות של הטבעיים (למעשה, במשפחות של תתי-קבוצות כאלה), גם היא אינה מדירה שינה מעיניהם של "מתמטיקאים יומיומיים". למידע נוסף, אתה מוזמן בשמחה לכתוב לי. |
|
|
|
|
|
|
||
|
||||
|
תודה על התגובות. בעיני, הנקודות האלה הן מהותיות, אולי לא למתמטיקאיים "יומיומיים" (המושג הזה עוד יהפוך למטבע לשון...), אלא יותר לפילוסופים של המתמטיקה. קצת על הרקע שלי - אני בוגר תואר ראשון במתמטיקה ופילוסופיה ב"עברית" והתמקדתי בשנתי האחרונה בפילוסופיה של הלשון, של הלוגיקה ושל המתמטיקה מחד, וביסודות המתמטיקה מאידך. למדתי קורסים בפילוסופיה של המתמטיקה, במשמעות הפילוסופית של משפטי גדל, בתורת החישוביות (אצל פרופ' שלח) ובמשמעות הפילוסופית של החישוביות, בתורת הקבוצות האקסיומטית (אצל פרופ' מגידור, שם גם הוכחנו באופן פורמלי את משפט גודסטין בעזרת סודרים גבוהים עד אומגה אפס). כך שהנושאים האלה לא זרים לי, ואף מרתקים אותי. כשלמדתי על תוכנית הילברט ו"מפלתה" אחרי משפטי גדל, וכשעשיתי על התוכנית סמינריון קצרצר, לא יכולתי להמנע מהמחשבה שהתוכנית היומרנית שמוצגת, יכולה בקלות להפוך לתוכנית עבודה בגבולות המחשבה האנושית. היו פילוסופים שניסו "להציל" את תוכנית הילברט על ידי בניית מערכת אקסיומות קונסטרוקטיבית שנבנית על סמך הקודמות בשיטת בניית פסוק גדל. הצרה שהמערכות שלהם חייבות להיות אינסופיות. לעומת זאת, מערכות כאלה הן בנות מנייה, או לכל היותר עד אומגה אפס. היה פילוסוף נוסף (לא זוכר את שמו; פרופ' מרק שטיינר סיפר לי עליו בקורס על משפטי גדל), שטען שהפסוקים הלשוניים שהאנושות מסוגלת לייצר היא מסיבוכיות של אומגה אפס. זהו סודר שמייצג את הקינון עד לאינסוף של פסוק בתוך פסוק בשפה האנושית. זה מעיד גם על רמת המורכבות והסיבוכיות של המחשבה האנושית בכלל וגם על כך שזה יותר טבעי לנו לחשוב באופן מקוון מאשר באופן ליניארי. בסך הכל אנו מנסחים את מחשבתנו עם פסוקי "ש..." שמקוננים בתוך פסוקים עיקריים. במילים אחרות שפת היומיום שלנו דומה לשפת מחשב מאוכוונת אובייקטים, שבה מדברים בפסוק הראשי על אובייקטים, שכל אחד מהם מפנה למחשבה יותר עמוקה ומורכבת ומקוננת. אני חושב שיש משהו מאוד מדוייק בהשלכת סודר אומגה אפס על מבנה השפה (והמחשבה?...) האנושית. מסקנה זאת חוזקה אצלי גם מתוך קריאה של הפילוסופיה של נועם חומסקי. הוא מנסה לנתח את מבנה השפה המקונן ומגיע למסקנה שיש לנו ידע שפה מולד (באופן פשטני "כי זה מבנה מסובך לאין ערוך ממבנה ליניארי, ואין סיכוי שנלמד להשתמש במבנה כזה באופן כל כך טבעי"). אני הסקתי מכך שמבנה המחשבה שלנו הוא אובייקטאלי, וזה דווקא יותר טבעי לנו ללמוד שפה שהיא מקוננת ולא ליניארית (החזרתי לחומסקי את חובת ההוכחה לגבי הידע המולד). הקיצר, אני לא טוען שחקירת לוגיקה פורמלית תביא אותנו לכתיבת המערכת הפורמלית האולטימטיבית שבעזרתה ניתן יהיה לייצג את כל הפסוקים האפשריים או להבין את כלל המחשבה האנושית. לא נוכל לסיים את תפקידינו במתמטיקה על ידי ניסוח מערכת אקסיומות מסויימת. נדמה לי שטרסקי (בעקבות גדל) ניסח את הטענה שלא ניתן בשפה פורמלית "לדבר" על ערך האמת של פסוקים בשפה זו, אלא ניתן לעשות זאת רק בשפה מסדר גבוה יותר. אבל אני אומר שני דברים: א. ניתן להבין יותר טוב את מהות המחשבה האנושית והמחשבה המתמטית על ידי חקירה של הנושאים הללו. זה מקביל בעיני למה שעשה טיורינג כשיצר את מדעי המחשב. הוא בעצם חקר באופן מדוקדק ופשטני איך אדם עושה חישוב מתמטי על הנייר (נייר משבצות) ווהעמיד את כל הפעולות על מספר סופי של פעולות פשוטות של כתיבה, מחיקה ומעבר משבצת. וזה כל הסוד של מדעי המחשב - החיקוי של הפעולה האנושית הפשוטה של החישוב. ב. במובן המתמטי ה"יומיומי" החקירה הזאת תוביל אותנו לדרכים ל"ייצור" של מערכות אקסיומטיות גבוהות ומורכבות שבעזרתן ניתן יהיה להגיע לתוצאות מתמטיות חשובות. הרי מה שעושים במתמטיקה ברמות הגבוהות הוא למצוא מהן האקסיומות הדרושות להוכחת משפטים "מענינים" במתמטיקה ושאותן נוכל לקבל להיכל הכבוד של האקסיומות המתמטיות. דוגמא טובה לכך הן אקסיומות החבורות של גלואה שאיפשרו לו לקבל תוצאות במשוואות פשוטות (הוא לא ממש ניסח את האקסיומות, אבל חקר את התנאים ההכרחיים לצורך ההרחבות של השדות). כתבתי בזמנו באחד מהדיונים כאן על הצעה שלי לשיטה ל"הוכחת" השערת גולדבך (אם היא נכונה). השיטה היא לנסות למצוא באיזה מערכת אקסיומות היא יכיחה ומאיזו היא בלתי תלויה. אם נצליח להוכיח למשל שהיא בלתי תלויה במערכת מצומצת הכלולה בתוך PA (אך לא מכילה אותה), אזי נצליח אולי להבין איך כן ניתן להוכיחה בתוך PA. ואותו דבר גם אם היא לא יכיחה בתוך PA - אז אולי נוכל למצוא את האקסיומה שתאפשר לנו להוכיחה במערכת שמכילה את PA. (אגב, מישהו בתגובה הציע שנוסיף אותה כאקסיומה, ואני התנגדתי, שכן אין להשערת גולדבך את התכונות שנרצה לייחס לאקסיומה. זהו פסוק שאינו מספיק טריויאלי). בכל אופן, שיטה כזאת היא בפירוש רלוונטית למתמטיקאיים יומיומיים, דווקא מתוך חקירה של מערכות פורמליות. |
|
|
|
|
|
|
||
|
||||
|
1) יש פער גדול בין האקסיומות של תורת החבורות לאלו של תורת הקבוצות. בראשונה יש תורה שאומרת שאם יש לנו עצמים בעלי תכונות אלו ואחרות אזי הם מקיימים משפטים מסוימים. בשניה יש לנו תורה שבאה לשמש בסיס פורמלי לכל המתמטיקה ה"יומיומית" כולה, והאקסיומות בה טוענות לנכונות באיזשהו מובן אבסולוטי. 2) יכול להיות שהתכוונת לתגובה 164381. במקרה זה, ודאי שנרצה לאמץ את השערת גולדבך כאקסיומה, אם פשוטה היא ואם סבוכה. |
|
|
|
|
|
|
||
|
||||
|
לא הבנתי שום דבר ממה שאמרת, אז אני מרשה לעצמי לנדנד בצורה לא מבוקרת. כתבת: "[....]טען שהפסוקים הלשוניים שהאנושות מסוגלת לייצר היא מסיבוכיות של אומגה אפס." ואני קצת מתפלא: האם יש פסוק לשוני שאינו מורכב מאותיות? האם יש לנו בעיה למנות את כל הספרים האפשריים בעלי ...1,2,3, אותיות? הייתכן שסיבוכיות של פסוק הוא יותר ממספר האותיות שבו? |
|
|
|
|
|
|
||
|
||||
|
תגובה יפה, אם כי איני בטוח שאני מסכים, או מבין את כולה. אגב, במשפט "יותר טבעי לנו לחשוב באופן מקוון" האם התכוונת לnested (מקונן)? |
|
|
|
|
|
|
||
|
||||
|
רק הערה קטנה: PA אולי מערכת חלשה למדי, אבל עד כמדומני שעד 1977 (פאריס-הארינגטון) לא ידעו שהיא יותר חלשה מZFC. וניטפוק: אפסילון אפס ולא אומגה אפס. ותהיה: יומיומיות היא שבח או עלבון למתמטיקאי? |
|
|
|
|
|
|
||
|
||||
|
שבח למתמטיקאי יום יומי, וגנאי למתמטיקאי שאינו יום יומי. | |
|
|
|
|
|
||
|
||||
|
ובקצרה (משהו שיתאים לתלמידי שנה שניה), מה זה אפסילון/אומגה אפס? | |
|
|
|
|
|
||
|
||||
|
תגובות: אורי (תגובה ראשונה שלך): 1. אני לא רואה הבדל בין אקסיומות של תורת הקבוצות לבין אקסיומות של תורת החבורות. גם בתורת הקבוצות מניחים את קיומם של עצמים - שנקרא להם קבוצות - ומנסחים חוקים ותכונות של העצמים - אלה הן האקסיומות של הקבוצות - ועל פי חוקים אלה מנסים להוכיח קיום תופעות בקבוצות - משפטים מתמטיים. ההבדל הוא במוטיבציה בלבד ולא בשיטות החקירה המתמטית. בתורת הקבוצות אנו מנסים "להציל את התופעות" המתמטיות ולבססן על חוקים לוגיים שאנו יכולים לחיות איתם, ואילו בתורת החבורות אנו מנסים להגיע לתוצאות חדשות באמצעות אקסיומות יעילות יותר. אם כי גם מוטיבציות אלו השתנו עם הזמן וגם בתורת הקבוצות מנסים כיום להגיע לתוצאות חדשות (ומשפט גודסטין הוא דוגמא טובה לכך). דרך אגב, הפילוסופיה של גדל עצמו הייתה שכל (בדגש ובבולד) המתמטיקה עוסקת בעצמים קיימים ובמשפטים נכונים אבסולוטית. הוא היה האפלטוניסט בהא הידיעה של המתמטיקה המודרנית. כך שאני לא בטוח בכך שרק תורת הקבוצות מתיימרת לתאר אמת אבסולוטית. לדעתי זה עניין של אופנה: בתקופת ניוטון ולייבניץ, יצרו את האינפיניטסימל בכדי לתאר את המציאות האבסולוטית של תנועה, ויירשטראס עיגן את זה בתורה מסודרת בכדי שלא תהיינה סתירות (כדי להצדיק את התופעות ולהביא לבסיס איתן של המתמטיקה). אחריו דדקינד ייצר את החתכים שלו כדי לייצר בסיס איתן למספרים הממשיים; אחר כך פיאנו יצר את האקסיומות שלו כדי לייצר בסיס איתן למספרים הטבעיים; קנטור יצר את התורה שלו כדי לאפשר לדבר על אינסופים, פרגה הלך עם זה רחוק מידי, ואילו ראסל וויטהד ניסו לעגן זאת בתיאוריה יומרנית בכדי לברוח מהסתירות של פרגה. בסוף הגיעו צרמלו, פרנקל ושות' בכדי לעדגן את תורת קנטור באקסיומות מסודרות יותר. מה מתוך זה הוא יסודות מתמטיקה ומה נחשב כמתמטיקה יומיומית? עוד חמישים שנה ינסחו תיאוריה הרבה יותר יסודית וחזקה שתהפוך להיות יסודות המתמטיקה ומתיימרת לעסוק אמת האבסולוטית ואילו ZFC תיחשב כעוסקת בעצמים מסוימים שניתן שיהיו גם אחרת. 2. אני חולק עליך. מבחינה מתמטית ניתן למצוא פסוקים רבים שאינם תלויים במערכת האקסיומות של PA, אך לא את כולם נרצה לקבל כאקסיומות. הם פשוט לא אינטואיטיביים מספיק. אנו רוצים לקבל כאקסיומה פסוק שאותו לא נצטרך להצדיק - פסוק שנראה כאילו הוא תופס את מהות העצם אותו אנו חוקרים ושעליו יש לנו "מודל טבעי" או יכולת להצביע עליו (מספר בPA או קבוצה בZFC). משפט שמכיל יותר מזה נרצה להחליף במשפט שקול לו (או במערכת משפטים שקולים) שהם כן נראים ומרגישים כמו אקסיומות. אין מה לעשות - במתמטיקה נכנסים שיקולים שהם לא רק מתמטיים או לוגיים. ראובן: כמובן שפסוק הינו סופי ולכן הסיבוכיות שלו היא סופית. הטענה היא שניתן "ליצוק" את כל הפסוקים האפשריים שהאנושות יכולה ליצור בתוך מבנה סיבוכיות של סודר אפסילון אפס, כלומר יש פוטנציאל קינון אינסופי בפסוקים האנושיים. אדב, תקרא קצת משפטים מתורגמים מגרמנית ותבין על רמת הקינון שאני מדבר - או לא תבין כלום (הייתי מציע להתחיל ב"ביקורת התבונה הטהורה" של קאנט) אפופידס: התכוונתי למקונן, ונדמה לי שכך גם כתבתי... אולי פיספסתי במקום אחד. אורי2: א. אכן אפסילון אפס ולא אומגה. טעות שלי... ב. יומיומית זה לא עלבון ולא שבח (אפשר לראות זאת כשבח, אך בודאי שאין הכוונה לעלבון). הכוונה הייתה פשוט להבדיל את המתמטיקאים העוסקים במתמטיקה לעומת אלה שעוסקים ביסודות המתימטיקה, בלוגיקה ובתורת הקבוצות (ואולי גם יחד עם העוסקים בפילוסופיה של המתמטיקה ושל הלוגיקה). אתה בעצמך הבדלת לעיל בין תורת החבורות לתורת הקבוצות. |
|
|
|
|
|
|
||
|
||||
|
ולסיום להיום: אני חושב שיש מעמד מיוחד לPA על ZFC. אקסיומות PA מנסות לתאר את התכונות של המספרים הטבעיים, ואילו ZFC עוסקת בעצמים הרבה יותר כלליים ומופשטים. מי אמר שיש קבוצות אינסופיות? די בטוח שיש מספרים סופיים, אך קבוצת כל המספרים הסופיים? תצביעו לי עליה בבקשה. אני יודע שאני נשמע כמו אינטואיציוניסט, ואין לי ממש בעיה עם זה. אבל אין הכוונה שלי לתת נאום בעד האינטואיציוניזם, אלא להמחיש את ההבדל במעמד שבין אובייקטים מתמטיים מוצקים כמו המספרים הטבעיים, יחד עם המודל הטבעי שלהם, לעומת אובייקטים מתמטים מופשטים כמו סודרים אינסופיים וכדומה. אפילו מספרים ממשיים הם לא ממש טבעיים לנו (כפל לשון) ואנו נזקקים למודל של קו ישר גיאומטרי ולמילוי החורים בו כדי לתפוס על מה מדובר. המשפט המפורסם: "אלוהים יצר את המספרים הטבעיים, כל השאר הם מעשה ידי האדם" מדבר אלי מאוד. אני חושב שמספרים טבעיים שונים מכל עצם מתמטי אחר בכך שכל מודל מתמטי חילופי לו הוא חילופי לטבעיים ובמעמד אחר ממנו. לעומת זאת, קבוצות אינסופיות שמקיימות או לו מקיימות את השערת הרצף - האם באמת אנו יכולים להעדיף אינטואיטיבית מודל זה או אחר? יש כמובן שיקולים של יעילות ויופי מתמטי וכדומה, אבל אני לא חושב שיש ממש העדפה בסיסית של מודלים המרחיבים את המספרים הטבעיים. מסיבות אלה, אני מעדיף להרחיב את אקסיומות פיאנו כדי לתפוס עוד ועוד תכונות של הטבסעיים, מאשר להרחיב את ZFC או אפילו מאשר להוכיח תכונות בZFC שלא ניתנות להוכחה ב PA. |
|
|
|
|
|
|
||
|
||||
|
אבל PA ו- ZFC לא מתחרות בכלל על אותה גומחה אקולוגית. | |
|
|
|
|
|
||
|
||||
|
לגבי המשפט האחרון שלך: מבחינה פילוסופית נטו, למה הוכחות ב ZFC (ללא הרחבות חזקות יותר) "נחשבות" פחות? הרי כמעט כל המתמטיקה המודרנית תלויה בהן, לא? בפרט דברים מאוד "פיזיקליים" ואינטואיטיביים כמו חלקים גדולים מהאנליזה והגאומטריה. אנחנו משתמשים באקסיומות הללו בשביל כל הדברים החשובים, ודי "סומכים" עליהן. למה לא לסמוך עליהן גם בקשר לטבעיים (בהתעלם משיקולי אלגנטיות)? | |
|
|
|
|
|
||
|
||||
|
גם לעוזי וגם לגיל: אני כתבתי על העדפתי האישית "לפרמל" את המודל הטבעי של הטבעיים באופן שמרני ששומר על רוח PA, ולא מפליג למחוזות האינסופים הגדולים והמטורפים של ZFC. הסיבה שכתבתי זאת היא כי היו תגובות שאי תלות של פסוקים בPA זה לא חוכמה ואילו אי תלות ב ZFC זה כבר דברים מענינים יותר. בתכל'ס - הוכחות בתוך ZFC מאוד נחשבות בעיני וגם נותנות מהוות כלים כדי להרחיב באופן שמרני את PA. במילים אחרות, ZFC (או אולי מערכת חלשה יותר כמו ZF)היא מסגרת למתמטיקה ולחוקי כתיבת הוכחות (במקביל לכך שפרינקיפיה מתמטיקה ותחשיב הפרדיקטים מסדרים גבוהים מהווים מסגרת לדיון מתמטי). חקירה של ZFC היא חיונית כדי לדעת את גבולות החקירה המתמטית של המספרים הטבעיים (כמו גם תחומים אחרים). אך אני רואה כמטרה עליונה למצוא את ההרחבות ה"צנועות" של PA (או למצוא מערכת אקסיומות צנועה אחרת של הטבעיים) כדי להוסיף ידע על פסוקים במספרים הטבעיים. לדוגמה: ייתכן שגולדבך הוא כזה שלא ניתן היום להוכיח מPA וכן ניתן להוכיח בZFC (זה משהו שניתן להוכיח בZFC). במקרה כזה הייתי רוצה למצוא מערכת הרבה יותר חלשה מZFC שבה ניתן יהיה להוכיח את גולדבך. אני אומר כל זאת לא מתוך זלזול או הבעת ספק בZFC ובתורת הקבוצות האקסיומטית. להיפך, מתוך העמדה שלי שזו מסגרת לגיטימית להוכחת תלות ואי-תלות במערכות חלשות יותר, אני מנסה למצוא את ההרחבות המתאימות. זוהי לגעתי המשמעות האמיתית של "תוכנית הילברט" לאחר ההתפכחות שהביאו עלינו משפטי גדל. |
|
|
|
|
|
|
||
|
||||
|
מה דעתך על ZF (בלי C)? גם היא גדולה ומטורפת? למה? | |
|
|
|
|
|
||
|
||||
|
תצטרך להתאמץ הרבה יותר כדי להתקבל למועדון. | |
|
|
|
|
|
||
|
||||
|
מצטער על שאני מעלה באוב פתילים ישנים. אני מוכרח לציין שהעובדה שזה לא יכיח ב- PA היא אחד הדברים לראש קשה מאד לקלוט ולהאמין בהם. שאלה שאולי תשובה אליה תחזיר לי את האמון באינטואיציה המתמטית שלי (אני כנראה צפוי להתאכזב). איך אני מגדיר "בעיטה" בשפה של אקסיומות פיאנו ? |
|
|
|
|
|
|
||
|
||||
|
מה כל כך מיוחד ב-PA שכל המתמטיקה צריכה לנבוע ממנה? PA זו בסה"כ אסופת הדברים הפשוטים שנראים נכונים שאפשר להגיד על המספרים הטבעיים. לא יכיח ב-ZFC, לעומת זאת, זה כבר משהו אחר... |
|
|
|
|
|
|
||
|
||||
|
אתה ממש רוצה שנרשום את פעולת ה"בעיטה" כנוסחה ב-PA? זה נראה לי תענוג מצומצם מאוד, אבל אפשר לנסות. עם זאת, איני רואה איך נוסחה כזו יכולה לעזור לאינטואיציה שלך. אולי אתה שואל *האם* ניתן לעשות זאת? האם נדמה לך שלא? | |
|
|
|
|
|
||
|
||||
|
זה באמת מפתיע מאוד. שאלה: אם ה"בעיטה" לא היתה מוגדרת רקורסיווית, כלומר, היינו מחליפים מ k ל k+1 רק את הבסיסים שלמטה (ולא בתוך החזקות), או אפילו היינו עושים דבר יותר פשוט, ורק מחליפים מ k ל k+1 בחזקה הגדולה ביותר - כלומר אם n=k^x+y כאשר y<k^x ,אז Bk(n) = (k+1)^x+y האם אז עדיין הסדרה מתכנסת לאפס? האם יותר קל במקרה הזה להוכיח זאת?
|
|
|
|
|
|
|
||
|
||||
|
לדעתי התשובות הן "כן" ו-"כן", לפחות בהגדרה הפשוטה יותר שלך. יש לפחות שתי דרכים לפרש אותה: נניח ש-k=3 ואנחנו ב-3^3, נבעטנו ל-3^4 וחיסור 1 מביא ל...מה? 47 + 2^4 או 15 + 2^4*3? האפשרות השנייה דומה יותר לפיתוח לפי בסיס (החזקה הגבוהה בלבד), אך האפשרות הראשונה מתאימה לנוסחאות שהצגת. בשתי האפשרויות לא קשה לראות שמגיעים ל-0. אני מוכן להמר שוריאציות פשוטות כאלה על הנושא יובילו או למקרים בהם הטענה לא נכונה, או למקרים בהם היא נכונה וקלה. היופי בהגדרה של גודסטין הוא שזה שואף ל-0 אבל ממש, ממש, ממש בקושי... |
|
|
|
|
|
|
||
|
||||
|
אני מאוד מתפעל ממאפיין "גרפולוגי" חביב בכתב ידו של כותב המצגת: אם מילה מכילה את האות i, תופיע כנדרש נקודה מעל המילה; אבל הנקודה אצלו מופיעה מעל מקום אקראי כלשהו בין ה-i לבין סוף המילה. דוגמה נאה: המילה given בשקף 3. (תשובה: 'מה אתה רוצה, יש מיפוי חח"ע בין הכתיב הזה לבין הכתיב המקובל, עם הנקודה מעל ה-i.') |
|
|
|
|
|
|
||
|
||||
|
במילה "positive" בשקף השני, הנקודה של ה-i הראשון מופיעה מעל ה-s. אז יכול להיות שצריך להיות סייג למיפוי החח"ע. | |
|
|
|
|
|
||
|
||||
|
חד עין! משעשע מאוד. מה זה אומר? איפה המומחה לגרפולוגיה? יובל, יובל! | |
|
|
|
|
|
||
|
||||
|
אה, זה מקרה פשוט. ההזחה של נקודת ה- i ימינה (בז'רגון המקצועי: אילפרוניפיקציה מזרחית) מגלה לנו כי הכותב הוא אדם אנליטי, חריף, ובעל יכולת הפשטה. טוב יעשה אם יפנה את מרצו למחקר מתמטי. | |
|
|
|
|
|
||
|
||||
|
טוב תעשה אם תפנה מרצך למחקר גרפולוגי. | |
|
|
|
|
|
||
|
||||
|
יובל כבר עשה זאת, בעקיפין, במאמרו "גרפולוגיה: מדע או אחיזת עיניים?": דיון 1421 | |
|
|
|
|
|
||
|
||||
|
וזו, כמובן, הסיבה שפניתי אליו מלכתחילה תגובה 167826 :-) | |
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
הלינק שבור, הלכתי לויקיפדיה האנגלית והבנתי את ההגדרות ואת קצב הגידול הענקי, נתקעתי כשהם התחילו בהוכחה מחוץ לPA עם אורדינלים במקום להראות לי למה זה לא יכיח או פריך(?) בPA. | |
|
|
|
|
|
||
|
||||
|
נתקעת כי ההסבר לא היה ברור או כי חיפשת את ההוכחה שזה לא כריע ב-PA? ההוכחה עם האורדינלים היא לא קשה ואפשר לעבור עליה כאן. ההוכחה שזה לא כריע ב-PA היא לא קלה בכלל ואני לא מתפלא שאין אותה בויקיפדיה. | |
|
|
|
|
|
||
|
||||
|
למה שדווקא השערת גולדבך תהיה בלתי-תלויה באקסיומות הסטנדרטיות? זה נראה לי לגמרי לא סביר. ואם כן, למה ("ברור") שנרצה לצרף אותה כאקסיומה? |
|
|
|
|
|
|
||
|
||||
|
דומני שאורי לא הניח שסביר שדווקא השערת גולדבך תהיה לא תלויה. בעיני היא לא מועמדת מוצלחת במיוחד, אבל זה עדיין ייתכן. ובאשר לצירופה כאקסיומה - אני חושב שהכוונה היתה שאם השערת גולדבך אכן מוכחת באורח-פלא כלא-תלויה, בפרט לא ניתן להצביע על דוגמה נגדית כלשהי, ולכן יותר "טבעי" להניח שהיא נכונה. אם, למשל, השערת הראשוניים התאומים מוכחת כלא-תלויה, המצב הוא ממש אחר: לא הטענה ולא שלילתה ניתנות לסתירה ע"י דוגמה, ולכן אין מועמד טבעי להיבחר כאקסיומה. |
|
|
|
|
|
|
||
|
||||
|
אני חושב שהבנתי אותך. מבחינת המודל הטבעי - זה יהיה נכון, כיוון שאם יש דוגמא נגדית להשערת גולדבך במודל הטבעי, אז היא תהיה בכל מודל, ולכן שלילתה יכיחה מאקסיומות פיאנו. נכון? | |
|
|
|
|
|
||
|
||||
|
אני חייתי תחת האשליה הנבאיבית על פיה טענה כללית היא נכונה אם ורק אם היא מתקיימת עבור כל מקרה פרטי. איך השערת גולבך יכולה להיות לא תלויה? היכן הטעות בטענות להלן: * אם אפשר למצוא דוגמא נגדית - היא אינה נכונה. * אם אפשר להוכיח שלא קיימת דוגמא נגדית - היא נכונה. * אם לא ניתן להוכיח שלא קיימת דוגמא נגדית - לא ניתן להוכיח שהיא בלתי תלויה (כי אם היא בלתי תלויה, לא קיימת דוגמא נגדית). ? |
|
|
|
|
|
|
||
|
||||
|
אם מוכיחים שלא ניתן להפריך את השערת גולדבך במסגרת אקסיומות פאנו, אז בפרט לא ניתן להצביע על מספר שאינו סכום של שני ראשוניים. אם כך, ההשערה נכונה. (לכן השערת גולדבך אינה יכולה להיות בלתי תלויה באקסיומות פאנו). |
|
|
|
|
|
|
||
|
||||
|
כנראה שלא ירדתי לסוף דעתך. אם לא ניתן להצביע על מספר כזה, אז הוא לא קיים (כי לכל מספר טבעי ניתן להגיע, ולו ע''י מעבר סדרתי על כל הטבעיים עד אליו). |
|
|
|
|
|
|
||
|
||||
|
withdrawn
|
|
|
|
|
|
|
||
|
||||
|
נדמה לי שאני לא מסכים לטענה בסוגריים. האם לא ייתכן מצב שבו לא ניתן לגזור מ-PA את GC וגם לא את GC~? למה? מנין ל-PA הכוח הזה? קח את המשוואה הדיופנטית של מאטייסביץ'. קיום פתרון למשוואה זו הוא לא כריע, ולכן בפרט אין לה פתרון (באותו מובן שאין לגולדבך דוגמה נגדית), כי אילו היה לה, היה קל לוודא אותו. למרות זאת, אין הוכחה שאין פתרון כזה. לפי הנימוק שלך, משוואה כזו לא תיתכן. |
|
|
|
|
|
|
||
|
||||
|
איזה יופי, גם מתמטיקאים לא-טרחנים לא תמיד ומיד מסכימים זה עם טענותיו של זה :-) | |
|
|
|
|
|
||
|
||||
|
כן, אבל כשזה קורה הם לפחות מודים (אחד מהם, לפחות, וזה לא עוזי) שהם מדברים על דברים שהם לא מבינים בהם. חוץ מזה, חכה, גג שבוע ואנחנו נסכים. | |
|
|
|
|
|
||
|
||||
|
כן, התכוונתי להגיד שאני בטוח שתגיעו להסכמה ואני מתכוון לחכות בסבלנות. | |
|
|
|
|
|
||
|
||||
|
כנראה שחוסר ההסכמה נובע מאי-בהירות בטענה המקורית. כשמדברים על השערת גולדבך, זו יכולה להיות ההשערה ה"מתמטית", הסטנדרטית (שעוסקת רק במערכת הטבעיים המוכרת), או ההשערה ה"לוגית", זו שאומרת אותו הדבר, אבל מנוסחת כטענה מסדר ראשון על מערכת פאנו שבו היא מופיעה (אפשר להגדיר "כפל", "ראשוני" ו"ניתן לכתיבה כסכום שני ראשוניים" בשפה מסדר ראשון מעל מערכת פאנו). ההשערה הלוגית היא רחבה יותר, משום שבמערכת פאנו לא סטנדרטית היא מתייחסת גם לאברים ה"לא טבעיים". ההבדל המהותי הוא, כמובן, שבהשערה המתמטית כל דוגמא נגדית אפשר לבדוק בזמן סופי (אלא ש"אפשר לבדוק בזמן סופי" נמצא מחוץ למסגרת האקסיומות מסדר ראשון). אי-בהירות נוספת: אי-תלות "סתם", שבה ההשערה הנוספת נראית כאילו היא בלתי תלויה במערכת האקסיומות, לעומת אי-תלות "מוכחת" שבה, באמצעים שמחוץ-למערכת *מוכיחים* את אי-התלות (כמעט תמיד - על-ידי בניית מודל). כעת אנסה לנסח ולהוכיח את הטענה שלי מחדש. לא יתכן ש*נוכיח* (מחוץ למסגרת מערכת פאנו) שהשערת גולדבך (המתמטית!) אינה תלויה במערכת פאנו - או אפילו שעקבי להניח את השלילה שלה, משום שאז לא תתכן דוגמא נגדית "סופית" (ממערכת פאנו הסטנדרטית), ובכך הוכחנו את ההשערה כמשפט. אני מודה שזו טענה קצת מוזרה, כי בדרך כלל כשמדובר על אי-תלות, צריך להיות ניסוח של ההשערה בכלים של אותה מערכת (פאנו, במקרה שלנו), ואני לא טוען שום דבר על השערת גולדבך ה"לוגית", המנוסחת בשפה מסדר ראשון. בנוסף, הנימוק שלי עובד רק כשיש *הוכחה* לאי-התלות. אין לי שום דבר נגד מי ש*מאמין* באי-התלות, כל עוד הוא לא מתיימר לספק הוכחות (ובכך אני מתחיל לגלוש אל מחוץ לשטח השיפוט שלי). |
|
|
|
|
|
|
||
|
||||
|
1. אני לא מבין איך יכול להיות מודל של פאנו שבו ההשערה "הלוגית" לא נכונה, אבל אין לשלילתה הוכחה סופית. (הרי את הדוגמה הנגדית אפשר להרכיב ע"י סדרה סופית של פעולות successor מאפס). 2. אני מתאר לעצמי שבעיקרון, אפשר להוכיח את אי התלות גם בלי לספק מודל (למשל, אני חושב שמשפט גדל הוא כזה). האם הטיעון שלך תופס למקרה כזה? |
|
|
|
|
|
|
||
|
||||
|
1. אשמח אם תרחיב (המושג "ניתן להגיע אחרי סדרה סופית" אינו מסדר ראשון). 2. הטיעון שלי אינו דורש מודל, אלא הוכחה (מתמטית). |
|
|
|
|
|
|
||
|
||||
|
1. א. אני לא לחלוטין מבין במה שאני מדבר כאן. ב. לא טענתי שהמושג "ניתן להגיע אחרי סדרה סופית" הוא מסדר ראשון. התהייה שלי הייתה איך ייתכן שיש מודל שבו ההשערה לא נכונה, אבל שאין לעובדה זו הוכחה. זאת מאחר ונראה שאם ההשערה לא נכונה, אז יש לה דוגמא נגדית, ואם יש לה דוגמא נגדית, אז הדוגמה הזו בעצם מהווה הוכחה בתוך אקסיומות פאנו. 2. האם לא ייתכן ש: א. השערת גולדבך נכונה. ב. לעובדה הזו אין הוכחה בפאנו. |
|
|
|
|
|
|
||
|
||||
|
1. אני לא בקיא במודלים לא סטנדרטיים למערכות פאנו, ולכן צמצמתי את הטענה ל"השערת גולדבך המתמטית". יתכן שאת הדוגמא הנגדית (שאולי קיימת במערכת פאנו לא סטנדרטית) אי-אפשר לבדוק, שהרי במערכת לא סטנדרטית לא כל מספר הוא סופי (דהיינו, שרשרת סופית של פעולות עוקב על האיבר הראשון). 2. כנראה שזה המצב. אקסיומות פאנו הן חלשות מכדי שאפשר יהיה להוכיח בהן משהו מעין השערת גולדבך. |
|
|
|
|
|
|
||
|
||||
|
1. אני גם לא בקי אבל חשבתי שבכל מודל למערכת פאנו לא ייתכן מספר שלא ניתן להגיע אליו בשרשרת סופית של פעולות עוקב. (זאת מאחר שאם נגדיר את הקבוצה S כמכילה את 0 + כל המספרים שאפשר להגיע אליהם במספר סופי של פעולות עוקב מ0, אז לפי אקסיומת האינדוקציה* S יכיל את כל המספרים). * אקסיומה מס' 5 ב: |
|
|
|
|
|
|
||
|
||||
|
הוא אשר אמרתי: "אפשר להגיע במספר סופי של פעולות עוקב מ- 0" זה לא משפט בשפה מסדר ראשון, ולכן אקסיומת האינדוקציה לא חלה עליו. (וכל מערכות פאנו מסדר שני איזומורפיות זו לזו). |
|
|
|
|
|
|
||
|
||||
|
לא, זה בדיוק לא המצב. האקסיומה שציטטת היא מסדר שני, ובהקשר זה באמת אין מודלים לא-סטנדרטיים והבעייה נמוגה. בסדר ראשון, אי-אפשר לנסח את הטענה שלך ב-1. | |
|
|
|
|
|
||
|
||||
|
או, אז אם כך באמת אין לנו ויכוח, ותודה על ההבהרה. התיאור שלך גם מצדיק, לדעתי, את מה שאורי אמר בהתחלה על הוספת גולדבך כאקסיומה: אם מוכיחים את אי-תלות גולדבך הלוגית, זה אומר שהגירסה המתמטית נכונה (מה שאורי קרא "אין דוגמה נגדית במספרים רגילים"), ולכן סביר שנניח אותה כאקסיומה בנוסף לפאנו. מיץ, ראית? פחות משבוע!! :-) |
|
|
|
|
|
|
||
|
||||
|
אוקי, ועכשיו הגיע הזמן למידע נוסף: האם אתם מכירים ספרים או מאמרים טובים ללימוד-עצמי (אפילו לא מעמיק במיוחד) בנושאים שהוזכרו כאן (תורת המודלים, חשבון מונים, כריעות וכיוצא באלה), אם אפשר שיתאימו לבעלי קצת ידע מתמטי? |
|
|
|
|
|
|
||
|
||||
|
אני לא ממש מכיר ספציפית ספרים בלוגיקה, אני מוכרח להודות, אבל נראה לי ש-"A Mathematical Introduction to Logic" של Enderton מכסה לא רע את הנושאים שעלו כאן. אם אתה מעוניין בדיון ארוך, משעשע ולא מעמיק, תמיד יש את GEB של Hofstadter שכבר הוזכר כמה פעמים בתגובות. ברשת, יש לפחות ספר אחד שנראה יסודי (די מעמיק ומדוייק): הזכרת גם "חשבון מונים", שזה נושא אחר קצת, ונדון בספרים לרוב עם הכותרת "תורת הקבוצות". יש ספר חמוד של Kamke, ואני חייב להזכיר גם את On Numbers and Games המופלא של Conway, שהוא מאוד לא אורתודוקסי אבל בעצם... מי צריך חשבון מונים אחר? אם תהית פעם כמה זה באמת אפסילון (כלומר, אחד חלקי אומגה), זה הספר בשבילך. |
|
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
זו בדיוק הייתה כוונתי, אלא שאני חושש שאתה טועה במסקנתך, כלומר, פורמלית יתכן שהשערת גולדבך בלתי תלויה באקסיומות פאנו. במקרה זה, ניתן לבנות מודל עם דוגמא נגדית, אלא שהדוגמא הנגדית הנ''ל לא תוכל להיות במספרים ''רגילים'', אלו המשמשים אתנו לספור. מכיוון שאלו בדיוק המספרים שאותם אנו מנסים למדל ע''י אקסיומות פאנו, טבעי שנרצה להוסיף את השערת גולדבך לאקסיומות. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |