הוכחה לא קונסטרוקטיבית לכך שרציונלי זה טרנסצנדנטי (טוב, לא בדיוק…)

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

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

למי שלא בקיא במושגים – מספר רציונלי הוא מספר שניתן להציג כמנה של שני שלמים – למשל, 3 הוא מספר רציונלי ($latex \frac{3}{1}$), וגם $latex \frac{3}{7}$ הוא רציונלי וכן הלאה. לעומתו, $latex \sqrt{2}$ איננו רציונלי – לא ניתן להציג אותו כמנת שני שלמים בשום צורה שהיא, והוכחתי זאת בעבר בבלוג. ולא, $latex \frac{\sqrt{2}}{1}$ אינה הצגה לגיטימית כי $latex \sqrt{2}$ אינו שלם. מי שמתחכם בקטע הזה הוא לא מתמטיקאי ואל תתנו ל-SMBC לעבוד עליכם.


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

המספר הראשון הוא $latex \sqrt{2}^{\sqrt{2}}$. שורש 2 בחזקת שורש 2. מכיוון ש-$latex \sqrt{2}$ הוא אי רציונלי, יש לנו כאן מספר מהצורה "אי רציונלי בחזקת אי רציונלי". אז אם $latex \sqrt{2}^{\sqrt{2}}$ הוא מספר רציונלי, סיימנו. אחרת…

אחרת, בואו נביט שניה על המספר $latex \left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}$. כלומר, המספר $latex \sqrt{2}^{\sqrt{2}}$ שעליו דיברנו לפני שניה, בחזקת המספר $latex \sqrt{2}$. המספר הזה הוא רציונלי בודאות, כי אם נשתעשע איתו על פי חוקי החזקות הרגילים נקבל:

$latex \left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}=\left(\sqrt{2}\right)^{\sqrt{2}\cdot\sqrt{2}}=\left(\sqrt{2}\right)^{2}=2$

כלומר, $latex \left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}$ זו פשוט דרך מפוצצת לרשום את המספר הרציונלי 2. אבל מה יש לנו כאן? אם $latex \sqrt{2}^{\sqrt{2}}$ היה אי רציונלי, אז מצאנו זוג מספרים אי רציונליים ($latex \sqrt{2}^{\sqrt{2}}$ ו-$latex \sqrt{2}$) שכאשר מעלים את האחד בחזקת השני, מקבלים מספר רציונלי. ואילו אם $latex \sqrt{2}^{\sqrt{2}}$ לא היה אי רציונלי, אז כאמור – זה אומר שהוא רציונלי ולכן מצאנו זוג מספרים אי רציונליים ($latex \sqrt{2}$ ו-$latex \sqrt{2}$) שכאשר מעלים את האחד בחזקת השני, מקבלים מספר רציונלי. אז הראינו כי בודאות קיים זוג מהסוג שאנו מחפשים, אבל אין לנו מושג איזה משני הזוגות הוא הנכון! סוף ההוכחה.

בהערת אגב מתמטית אפשר לומר שלמעשה, אנחנו כן יודעים מי משתי האפשרויות נכונה, אבל לשם כך צריך מתמטיקה יותר מתוחכמת מזו שהצגנו כאן. למעשה, יש משפט כללי וחזק למדי שמטפל בסיטואציות של "אי רציונלי בחזקת אי רציונלי". משפט גלפונד-שניידר אומר כי אם $latex b$ הוא אי רציונלי ו-$latex a$ הוא מספר כלשהו שונה מ-0 או 1, ושניהם אלגבריים, אז $latex a^{b}$ הוא טרנסצנדנטי. "מספר אלגברי" הוא מספר שהוא פתרון של משוואה כלשהי במקדמים רציונליים (למשל, $latex \sqrt{2}$ הוא כזה כי הוא פתרון של $latex x^{2}-2=0$) ואילו $latex \pi$ אינו כזה, אם כי ההוכחה לכך אינה פשוטה (וכרגיל, המתחכמים שיגידו ש-$latex x-\pi=0$ היא משוואה מתאימה יתעלמו מכך ש-$latex \pi$ שאינו רציונלי מופיע במשוואה הזו כמקדם של $latex x^{0}$). "מספר טרנסצנדנטי" הוא פשוט מספר שאינו אלגברי, ו-$latex \pi$ הוא דוגמה קלאסית יחסית למספר שכזה (אם כי לא הראשון שהוכיחו עליו שהוא כזה וודאי שלא זה שהכי קל להוכיח זאת עבורו).

למעשה, משפט גלפונד-שניידר הוא כלי חזק למדי ב"בניה" של מספרים טרנסצנדנטיים מפורשים, ובפרט הוא מראה כי $latex \sqrt{2}^{\sqrt{2}}$ מיודענו הוא כזה. לאלו מכם שתוהים האם הוא אינו מהווה דוגמה נגדית למשפט גלפונד-שניידר, שכן אם $latex a=\sqrt{2}^{\sqrt{2}}$ ו-$latex b=\sqrt{2}$ ראינו כי $latex a^{b}=2$ והרי $latex 2$ איננו טרנסצנדנטי – שימו לב שדורשים ש-$latex a$ יהיה אלגברי, ו-$latex \sqrt{2}^{\sqrt{2}}$ איננו כזה. במילים אחרות, כדי שיתרחש הפלא של "אי רציונלי בחזקת אי רציונלי שווה לרציונלי" צריך שהבסיס (המספר שאותו מעלים בחזקה) יהיה "ממש ממש אי רציונלי", כלומר טרנסצנדנטי.

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

30 תגובות בנושא “הוכחה לא קונסטרוקטיבית לכך שרציונלי זה טרנסצנדנטי (טוב, לא בדיוק…)”

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

    1/x

    כאשר x שואף ל-0.

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

    מדען, יש שרשור פורום ייעודי לזה:

    http://gadial.net/forum/viewtopic.php?f=2&t=10

    הוא עמוס כבר עכשיו ואת רוב הנושאים שהציעו לי שם אני בקושי מכיר ולא מסוגל לכתוב עליהם, אבל הוא כבר נתן לי הרבה רעיונות.

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

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

    1. מספר הזוגות שאחד מהם הוא רציונלי אינו בן מנייה אם השני יכול להיות לא רציונלי…

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

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

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

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

  8. תיקון להערה הקודמת, לא מדובר על לוגריתם לפי בסיס 2, אלא על לוג של 2 לפי בסיס X.

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

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

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

  11. לא יודע אם זה מעניין, אבל בדניגוד ל"שורש שתיים בחזקת שורש שתיים בחזקת שורש שתיים" שבו יודעים מי משתי הדוגמאות היא הדוגמה הנכונה, כאן למיטב ידיעתי עדיין לא יודעים:

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

    אז עכשיו לעניין: עמיצור שאל (בשנות ה-50) אם נכון שאם כל איברי חוג הם נילפוטנטיים אז גם כל איברי חוג הפולינומים נילםפוטנטיים. כלומר אם חוג A הוא נילי , האם A[x]‎ נילי? אגתה סמוקטונוביץ' (לפני כ-12 שנים) הראתה דוגמה נגדית: היא בנתה חוג A שכל איבריו נילפוטנטיים כל שיש פולינום בשני משתנים בעל מקדמים באותו חוג שאינו נילפוטנטי. אם כך היא הראתה חוג נילי R כך ש-R[x]‎ אינו נילי, והחוג הזה הוא R=A או R=A[x]‎ (אבל לא ידוע איזה מהשניים. אם A[x]‎ נילי אז A הוא הדוגמה הנגדית, ואחרת A[x]‎ הוא הדוגמה הנגדית).

  12. האם יש הוכחה פורמלית למשפט גלפורד-שניידר? האם זו הדרך היחדה "להראות" ששורש 2 בחזקת שורש 2 אינו אלגברי?

  13. אם אין הוכחה, למה קוראים לו "משפט"?

    אני לא בטוח אם זו ההוכחה היחידה, ובטח שלא נראה לי שיש הוכחה לכך שזו ההוכחה היחידה.

  14. האם הוכחה לא קונסטרוקטיבית מתבססת על "חוק חוסר הסתירה" כלומר על כך שאנחנו מקבלים את P ^ ~P בתור שקר? או לחילופין את חוק השלישי מן הנמנע כלומר את כך ש P V~P זו אמת מתוקף צורתה?

    האם 3 חוקי המחשבה הם בכלל חלק מהלוגיקה המתמטית ? http://en.wikipedia.org/wiki/Three_classic_laws_of_thought#Aristotle

  15. יש עוד הוכחה בסגנון שלך לגבי טרנסצנדנטיים: בהנתן שני מספרים טרנסצנדנטיים A,B אזי אחד מהביטויים הבאים בוודאות טרנסצנדנטי AB ,A+B אבל ההוכחה לא מראה לך מי מהם

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *