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

הסיפור מתחיל בהשערת קולאץ. קחו מספר שלם חיובי, לא משנה איזה. אם הוא זוגי תחלקו ב-2. אם הוא אי זוגי תכפלו ב3 ותוסיפו 1. תסתכלו על המספר החדש שקיבלתם. אם הוא זוגי תחלקו ב-2, אחרת תכפלו ב-3 ותוסיפו 1. הבנתם את הפרינציפ… תחזרו על הצעדים האלה שוב ושוב…. השערת קולאץ טוענת שלא משנה מאיזה מספר התחלתם, תמיד תגיעו ל 1. למשל אם התחלתם מ-3, הבא בתור יהיה 10, הבא בתור יהיה 5, אחריו 16 אחריו 8, 4, 2 ו-1. שימו לב שאחרי 1 היה אמור להגיע 4 ואחריו 2 ואחריו שוב 1, כלומר יש כאן לולאה.

השערת קולאץ היא לחלוטין לא טריוויאלית – הרי אולי תיתכן סדרת מספרים שהולכת וגדלה, הולכת וגדלה, ואף פעם לא מגיעה ל-1. ואולי יש עוד לולאה חוץ מ 4-2-1 שאפשר להיתקע בה וכך לא להגיע ל-1. כאמור, השערת קולאץ טוענת שזה לא יכול להיות. תמיד תגיעו ל-1. אבל זו רק השערה. כבר די הרבה שנים אף אחד לא הצליח להוכיח שזה באמת ככה. למרות פשטות הניסוח, למרות שמדובר רק במספרים טבעיים, רק בפעולות פשוטות של כפל ב 3, חילוק ב 2 והוספת 1 (לא בהכרח בסדר הזה). למרות כל אלה אף אחד לא הצליח להוכיח את זה או למצוא דוגמא נגדית. בינתיים, יש להוסיף.

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

ואז למדתי את משפט הקומפקטיות בקורס בלוגיקה.

אפשר לקרוא יותר על המשפט הזה בבלוג של גדי. בקיצור, נניח שיש לכם אוסף של נוסחאות. כל נוסחא אפשר להציב בה מספרים מסויימים ואז או שהיא תהייה נכונה או שלא. למשל, אם הנוסחא שלכם היא x-y=z, אז הצבה של x=2, y=1, z=0 יוצרת טענה לא נכונה. אפשר כמובן למצוא הצבות שמובילות אותנו לטענה אמיתית. לפעמים, כשיש כמה נוסחאות יחד, אפשר למצוא הצבה שתהפוך את כל הנוסחאות לטענות אמיתיות בו זמנית. למשל, אם שתי הנוסחאות הן: x+y=5 ו x-y=1, אזי ניתן להציב x=3,y=2, ושתי הנוסחאות הופכות לטענות אמיתיות. אם נוסיף נוסחא נוספת, למשל x+6*y=30, לא ניתן יהיה למצוא הצבות למשתנים כך שכל שלוש הטענות תהיינה נכונות (למרות שלכל זוג, אפשר למצוא הצבות מתאימות).

כאמור, יש לכם אוסף של נוסחאות. אוסף אינסופי של נוסחאות ליתר דיוק. ונניח שלכל תת קבוצה סופית של האוסף הזה אפשר למצוא הצבה מתאימה. בהחלט ייתכן שלכל קבוצה כזו תצטרכו הצבות אחרות. למשל בדוגמא שנתתי, כדי לספק את שתי המשוואות הראשונות הייתם צריכים x=3,y=2. כדי לספק את המשוואה הראשונה והשלישית, צריך להציב x=0, y=5. מנקודת ראותו של משפט הקומפקטיות זה מצויין, כל מה שהוא מבקש זה שלכל קבוצה סופית של נוסחאות מתוך האוסף שלכם תוכלו למצוא הצבה מספקת. אם תצליחו לעשות את זה, משפט הקומפקטיות מבטיח לכם שיש הצבה אחת (לפחות) שמספקת בבת אחת את כל אינסוף הנוסחאות שלכם. וזה דבר כביר. זו קפיצת הדרך. אנחנו בני האדם עוסקים בדברים סופיים ולכן כל מה שאנחנו מתבקשים לעשות זה לתת פתרונות מספקים לבעיות סופיות. משפט הקומפקטיות, אולי על תקן אלוהים, כבר ידאג לאינסוף.
נו טוב… זה לא היה ממש בקיצור, וזה מתחיל לגלוש לפרטים טכניים מדי… אז נחזור לסיפור, כי יש משהו שאני מחזיק בבטן כבר הרבה זמן ורוצה להשתחרר ממנו:

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

לא ממש. משפט הקומפקטיות נכון רק לסוג מסויים של לוגיקה, מה שנקרא תחשיב היחסים מסדר ראשון, ומה שהוכחתי, אם לא טעיתי, הוא שאפשר למצוא מודל של תורת המספרים מסדר ראשון שבו יש סדרת קולאץ שאינה מגיעה ל-1. יש כמובן גם תחשיב יחסים מסדר שני, חזק יותר, ותורת מספרים מסדר שני. לא ניכנס לזה כאן, זה מעבר לכוחותינו. אבל מה שאולי הוכחתי הוא, שאם השערת קולאץ נכונה, אזי היא תכונה “מסדר שני” של המספרים. אז מה הביג דיל?

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

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

אבל עד היום לא הבנתי איפה טעיתי אז, ועד היום אני חי בתחושה שיש לי הוכחה משמעותית שתקדם את פתרון בעיית קולאץ. האם יש שגיאה בהוכחה שלי? או שמא ההוכחה שלי נכונה, אבל לא ניתן להסיק ממני את החשיבות שאני מייחס לה (שהרי אם באמת לא ניתן להוכיח את קולאץ בטכניקות של “סדר ראשון”, תוסיפו לזה את העובדה שאין המון דברים “מסדר שני” – זה נותן כיוון די טוב איפה לחפש הוכחה להשערת קולאץ.)

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

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

הוכחה:
א. תנאי קולאץ ניתן לביטוי בנוסחא מסדר ראשון:
\kappa(x_1,x_2) \equiv (\exists{z}((x_1=z + z) \wedge x_2=z)) \vee  (\neg \exists{z}((x_1=z+z)) \wedge x_2=3*x_1 + 1)
ב. נגדיר את הפסוק:
\psi{_0} \equiv x_0 \ne 1
ג. לכל i טבעי (כלומר 1,2,3 וכן הלאה) נגדיר:
\psi{_i} \equiv \kappa(x_{i-1},x_{i}) \wedge (x_i \ne 1)
ד. תהא P קבוצת אקסיומות פיאנו.
ה. נגדיר:
Q = P \bigcup \{\psi{_i}\}_{i=1,2,3,...}
זו היא קבוצה אינסופית של נוסחאות מסדר ראשון.
ו. כל תת קבוצה סופית S של Q ספיקה על ידי המספרים הטבעיים וההצבה:

x_i = 2^{(n+1-i)}
כאשר n הוא האינדקס המקסימלי של פסוקים מאלה שהוספנו בסעיפים ב,ג שנמצאים בתת קבוצה S.
ז. לכן, לפי משפט הקומפקטיות, יש מודל, שמקיים את P כל הנוסחאות של Q, ובפרט הוא מקיים את כל אקסיומות פיאנו P (ולכן הוא מודל, אולי לא סטנדרטי, של תורת המספרים מסדר ראשון), ויש בו סדרה בת מניה של קבועים שאף אחד מהם איננו שווה 1 ואשר מהווים סדרת קולאץ.

מ.ש.ל.

הערה: ניתן לדאוג שכל איברי הסדרה יהיו שונים זה מזה, על ידי הוספת פסוקים נוספים מהצורה x_i \ne x_j.
שוב, כל תת קבוצה סופית שלה ספיקה בלי בעיות. ולפי משפט הקומפקטיות יש מודל שמספק גם את כולה.

מסקנה: אם השערת קולאץ נכונה, אזי היא לא ניתנת להוכחה באמצעות תחשיב היחסים מסדר ראשון בהתבסס על אקסיומות פיאנו.



תגובות

  1. גדי אלכסנדרוביץ' כותב:

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

  2. amit כותב:

    תודה גדי.

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

    אבל אסור לקוות או לפחות לפנטז שמה שאני עושה הוא מעניין וחשוב?

  3. נועה לביא כותב:

    אולי זה יעזור לך להבין… קח את אותה ההוכחה שלך, רק תוריד מהתנאי של קולאץ את החלק האי זוגי. זה עדיין יהיה ספיק סופית ע”י אותה הצבה בדיוק, נכון?

  4. amit כותב:

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

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

    אשמח אם תהיה לך סבלנות להסביר.

  5. נועה לביא כותב:

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

  6. amit כותב:

    טוב… קודם כל אני שמח שאני לא בעולם ה”אמרתי שטויות”, אלא רק בעולם ה”אמרתי דברים טריוויאליים וחסרי חשיבות”. למיטב ידיעתי אף אחד אחר לא התייחס לבעיית קולאץ במישור הזה.

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

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

  7. נועה לביא כותב:

    זה נכון שכל אקסיומות פיאנו מסדר ראשון מתקיימות בתורה השלמה. אבל הן בעצמן לא מהוות תורה שלמה – הווה אומר, יש עוד. כלומר (למיטב ידיעתי), יש תקווה שלא צריך סדר שני בשביל להוכיח את השערת קולאץ.

  8. amit כותב:

    אה…… לא נשמע משכנע.
    ראשית – ההבדל המהותי בין תחשיב היחסים מסדר ראשון לסדר שני הוא לא “כמותי”, כלומר אין הבדל באקסיומות. יש הבדל מהותי – מה אפשר להוכיח ומה אי אפשר להוכיח, מה אפשר לבטא ומה אי אפשר לבטא בכל אחד מהתחשיבים. ההבדל היחיד, למעשה בין התורה השלמה של המספרים (בתחשיב מסדר שני), לתורת המספרים הסטנדרטית (נתחשיב מסדר ראשון) הוא הניסוח (אני מדגיש: ניסוח בלבד!) של אקסיומת האינדוקציה.
    בתחשיב מסדר ראשון אנחנו נדרשים לאינסוף “מיני אקסיומות” קטנות כדי לנסח את אקסיומת האינדוקציה, וגם אז היא לא שלמה. וזאת כי אי אפשר להוסיף כמתים על קבוצות (אקסיומת האינדוקציה אומרת “לכל קבוצה (!) שמכילה את המספר 0 וכו’…”) – אז בתחשיב מסדר ראשון עוקפים את המגבלה הזו בדרך מחוכמת, אבל לא שלמה.
    בתחשיב היחסים מסדר שני – אקסיומת האינדוקציה מנוסחת כהלכה.

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

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

  9. amit כותב:

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

  10. נועה לביא כותב:

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

  11. amit כותב:

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

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

  12. גדי אלכסנדרוביץ' כותב:

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

  13. amit כותב:

    שוב תודה גדי שהלכת ובדקת. כבר מהדיון עם נועה הבנתי שהמחשבות שלי נמצאות בתחום ה”טריוויאלי ולא מעניין”, מה שמסביר למה עזבתי את המתמטיקה לטובת תחום אחר. למרות זאת שתי הערות:
    1) הפתיעה אותי הטענה שהבאת בתגובתך לגבי המספרים הראשוניים. נראה לי די פשוט להוכיח את זה מאקסיומות פיאנו, למשל: נניח שיש מספר X שמתחלק בכל הראשוניים, אזי X+1 אינו מתחלק באף אחד מהם, ולכן הוא בעצמו צריך להיות ראשוני והוא, באופן די טריוויאלי לא מחלק את X – סתירה. אני די בטוח שאפשר לפרמל את הטיעון הזה בתחשיב מסדר ראשון ולבסס אותו על אקסיומות פיאנו.
    2) מסתבר שיש טענות שלגביהן עושים עניין רב מהעובדה שהן לא יכיחות מאקסיומות פיאנו למרות שהן נכונות בעולם המספרים הטבעיים. ושני המשפטים שהבאתי בתגובה האחרונה שלי הם כאלה. הם לא פשוטים בכלל, אבל הטענה העיקרית שבהם היא: א. טענה Q נכונה עבור המספרים הטבעיים (ומביאים, או מצטטים הוכחה לאה של Q) ב. טענה Q אינה ניתנת להוכחה מאקסיומות פיאנו. הם עובדים מאד מאד קשה להוכיח את ב. ומשתמשים בטכניקות לא טריוויאליות בעליל של תורת המודלים, שאני לא מבין.

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

  14. גדי אלכסנדרוביץ' כותב:

    טוב, ייתכן שאני מבולבל, אבל מה מונע מאיתנו להשתמש בטכניקת ההוכחה שלך עבור המספר המתחלק שלי? נגדיר בתור פי_i את הפסוק שאומר “y מתחלק בראשוני ה-i”, ואז כל תת קבוצה סופית של פסוקים כאלו היא ספיקה (קח את מכפלת הראשוניים הללו) וממשפט הקומפקטיות, יש מודל לאקסיומות פיאנו ולכל הפסוקים גם יחד – הערך ש-y מקבל במודל הזה הוא המספר הקסום המבוקש.

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

  15. amit כותב:

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

  16. גדי אלכסנדרוביץ' כותב:

    אוקיי, אז מה עם התיקון שלי, של “מספר שמתחלק בכל הטבעיים”, כש”טבעי” מוגדר באינדוקציה בתור “0 טבעי; עוקב של טבעי הוא טבעי”?

  17. amit כותב:

    אתה מחפש מספר שמתחלק בכל הטבעיים. הפסוק שאתה רוצה שיהיה אמיתי הוא: קיים X כך שלכל Y המספר X מתחלק בY. מצד שני אתה מוסיף פסוקים מהצורה X_0 מתחלק בY_I עבור המון Y_I קבועים כלשהם.

    המודל שיתקבל בעקבות הפעלת משפט הקומפקטיות יכול להיות גדול יותר מאוסף הY_I שלך. כלומר המודל שמספק את כל הפסוקים עשוי להכיל מספרים שלא התייחסת אליהם בפסוקים שלך ועבורם אין לך שליטה איך הם מתנהגים. הם יכולים להיות מאד מוזרים, ובפרט יכולים לא לחלק את X_0.
    אני מניח למשל ש X_ 0 + 1 שחייב להתווסף למודל יחד עם X_0 (כדי לשמור על אקסיומות פיאנו), לא מחלק את X_0

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

  18. גדי אלכסנדרוביץ' כותב:

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

  19. amit כותב:

    זו טענה יפה – אבל אז הקרן השניה של השור תכה בך. האם אפשר לנסח את הטענה שלך בתחשיב היחסים מסדר ראשון? לדעתי אי אפשר. הביטוי “מספר סופי של צעדים” הוא הבעייתי. הדרך הסטנדרטית לייצג מספר סופי של צעדים היא לומר משהו כמו “קים N טבעי כך ש בN צעדים…”, אבל הרי במודל של הטבעיים עסקינן, ואם במודל הזה יש מספר שהוא בעיניך “לא סופי” אז גם צעדים לא סופיים יכללו בטענה הזו. קשה לי לראות את אפשר לבטא “מספר סופי של צעדים” בתחשיב יחסים בלי להסתמך על מודל קטגורי של הטבעיים (כלומר מסדר שני). יש לי השערה אפילו יותר חזקה. אם אפשר היה לבטא דבר כזה בתחשיב היחסים מסדר ראשון, אזי אפשר היה להגדיר את הטבעיים באופן קטגורי גם בתחשיב מסדר ראשון (ההגדרה היתה במקרה כזה: “החלק הסופי” של כל מודל שמקיים את אקסיומות פיאנו)

  20. mime כותב:

    היי עמית,

    (סליחה אם פספסתי משהו, אבל אני עייף מכדי לקרוא לעומק את כל התגובות, ומצד שני, לא יכולתי להתאפק שלא להגיב…)

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

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

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

    המסקנה – אקסיומות פיאנו כבודן במקומן מונח, אבל כנראה שצריך עוד משהו כדי לתאר את העולם ה”אמיתי”…

    רוביק

  21. amit כותב:

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

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

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

  22. mime כותב:

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

    אשר לדוגמה הקודמת – אז מודלים לא סטנדרטיים של הטבעיים הם במפורש לא סדורים היטב (לפי הסדר ה”טבעי”), ולכן הטיעון שלך לא רלוונטי. קח את הקבוצה שנוצרת על ידי x, x-1, x-2… כאשר x הוא טבעי לא סטנדרטי, אז הקבוצה הזו נטולת איבר מינימלי.

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

  23. amit כותב:

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

הוספת תגובה