שאלות ותשובות - מקבץ מס' 3

די בזריזות אחרי הפוסט השני הצטברו שאלות רבות, והנה התשובות:

1. "מציאת שארית ללא מחשבון" - אני מניח שהכוונה לשארית מחילוק. כדי לעשות זאת באופן כללי עבור שני מספרים אין מנוס מחילוק ארוך. בחילוק של p ב-q ארוך סדר הפעולות הוא כזה: מצא את הספרה (בין 1 ל-9) הגדולה ביותר שבה ניתן לכפול את q ועדיין לקבל משהו שכשרושמים אותו משמאל לימין מתחת למחולק הנוכחי (בהתחלה זה p), הוא עדיין קטן ממנו. אחרי זה מחסרים את שני המספרים זה מזה ומקבלים "שארית ביניים" - אם q גדול ממנה, אז גמרנו ושארית החלוקה היא בדיוק אותה שארית ביניים; אחרת מנסים לחלק גם את שארית הביניים ב-q וממשיכים הלאה. את כל זה אפשר לבצע בלי מחשבון כי זה דורש רק ידיעת כפל וחיסור, ובדיקת מספר מועט של אפשרויות בכל צעד (בודקים את כל הספרות מ-1 עד 9; לרוב כמובן לא באמת צריך לעבור על כולן כי קל לראות מה הספרה הנכונה). את זה גם ילד בבית ספר יסודי מסוגל לעשות.
2. "משפט אי השלמות של גודל" - להסביר מהו המשפט בדיוק דורש פוסט נפרד, אבל אפשר לתת כמה הערות: ראשית, גדל ולא גודל (Gödel; את ö יש לבטא יותר כ-e מאשר כ-o). שנית, יש שני משפטים (שהשני שבהם נובע מיידית מהראשון, אמנם), כך שיותר נכון לדבר על "משפטי אי השלמות של גדל" (ולמרות זאת, לעתים קרובות אני מדבר על "משפט גדל"). שלישית, הבהרה סטנדרטית כשמדברים על המשפטים, כדי שבכל זאת אגיד משהו בעל משמעות: הם לא אומרים "קיימות טענות נכונות שלא ניתן להוכיח או להפריך". אלו משפטים הרבה יותר "לוקליים", דהיינו מדברים על תורות לוגיות ספציפיות ומה שלא ניתן לעשות בתוכן.
3. "חוק הפילוג למה עוזר" - במשפט אחד: בלי חוק הפילוג (\( a(b+c)=ab+ac \))  לא היה שום קשר בין פעולות החיבור והכפל.
4. "בין כל שני אי רציונליים" - קיים מספר רציונלי. "הוכחה": להסתכל על הגדול מבין שני האי רציונליים ולעבור על כל הספרות שלו עד שמגיעים לספרה הראשונה ששונה מהספרה המקבילה לה באי רציונלי השני. כעת נגדיר מספר רציונלי שספרותיו הן הספרות שראינו בדרך, אבל "מפסיקים" את הפיתוח שלו באותה ספרה שונה, כך שהפיתוח העשרוני סופי והמספר שהתקבל רציונלי. כעת נותר להשתכנע שהוא קטן מהגדול מבין שני האי רציונליים אבל גדול מהקטן שמביניהם. אתגר: יש מקרה קצה אחד שממנו ההוכחה מתעלמת - מהו, ואיך פותרים אותו?
5. "הגדרת המספר פאי" - ההגדרה הסטנדרטית היא "היחס בין היקף המעגל לקוטרו". כמובן שבהגדרה הזו מסתתרת ההנחה (שיש להוכיח) שהיחס הזה זהה בכל המעגלים. לכן אפשר להצטמצם למעגל ספציפי - נניח, מעגל היחידה (המעגל שאורך רדיוסו 1). יש עוד הגדרות שקולות לפאי שמתבססות על כך שהוא צץ בתחומי מתמטיקה רבים; הגדרה אפשרית אחת היא בתור שטח עיגול היחידה; הגדרה יצירתית אחרת, שבה נתקלתי בספר האנליזה המרוכבת של Ahlfors, היא כדלהלן: ראשית מגדירים את פונקצית האקספוננט (בתור הפונקציה המרוכבת שמקיימת את המשוואה הדיפרנציאלית \( f^\prime(z)=f(z) \) עם תנאי ההתחלה \( f(0)=1 \)) ואחר כך מוכיחים שקיים לפונקציה הזו מחזור; את המחזור המינימלי מסמנים בתור \( 2i\pi \).
6. "דוגמה אחרת למספר אי רציונלי" - אני מניח שהכוונה לדוגמה שאיננה הדוגמאות הסטנדרטיות של שורש של מספר שאינו ריבוע, ואינה פאי, ואינה e. \( \sqrt{2}^{\sqrt{2}} \) הוא דוגמה למספר שכזה, אבל יש גם מחוכמים יותר - למשל, "קבוע ליוביל", שלא רק שאינו רציונלי, הוא גם אינו אלגברי (הוא אינו שורש של אף פולינום במקדמים רציונליים). באופן כללי, כל סדרת ספרות אינסופית שאינה מחזורית (כלומר, החל ממקום מסויים היא מורכבת מתבנית שחוזרת על עצמה שוב ושוב) נותנת מספר אי רציונלי.
7. "אופרטור העלאה בחזקה ++C". אין כזה. יש להשתמש בפונקציה pow שנמצאת בספריה math.h. פינת הפרופגנדה: בשפות שאני אוהב (רובי ופייתון) דווקא יש אופרטור העלאה בחזקה (שעובד גם למספרים לא שלמים) - **.
8. "איך מגדירים בעיה מתמטית מאתגרת" - כרגע עשית זאת, כי אין לי מושג... מה שכן, לפעמים דברים שנראים פשוטים יחסית ("כל מספר זוגי גדול מ-4 ניתן לכתיבה כסכום שני ראשוניים אי זוגיים") עשויים להתגלות כבעייה מתמטית מאתגרת.
9. "שלושה בתים מחוברים מבלי להרים את היד מהדף" - החיפוש הוביל לפוסט שלי על מסלול אוילריאני, אבל ייתכן שהכוונה הייתה לבעיה אחרת לגמרי, שגם היא עוסקת בגרפים - יש לנו שלושה בתים ושלושה "מקורות" (למשל, אספקת חשמל, מים וגז) ואנחנו רוצים לחבר כל בית לכל שלושת המקורות (באמצעות קווים) מבלי ששני קווי אספקה יחתכו זה את זה. בניסוח מתמטי השאלה היא האם הגרף הדו-צדדי עם שלושה קודקודים לכל צד (גרף שמסומן בתור \( K_{3,3} \)) הוא גרף מישורי. התשובה שלילית והיא בסיס למשפט חזק וכללי הרבה יותר; אני מקווה להרחיב על כך בפוסט נפרד.
10. "כל שפה ב-RE ניתנת לרדוקציה אל בעית העצירה" - כמובן; בהינתן מכונה עבור השפה M, בונים, לכל מילה x, קלט לבעיית העצירה באופן הבא: מכונה שפועלת כמו M, אך אם M עצרה ודחתה, נכנסת ללולאה אינסופית - ואם M עצרה וקיבלה, עוצרת ומקבלת; ואת המילה x. כעת, המילה x הייתה שייכת לשפה המקורית אם ורק אם הצמד של המכונה החדשה ושל x שייך לשפת בעיית העצירה.
11. "נוסחת אוילר, אלוהים" - ייתכן שהכוונה בכך היא לסיפור המפורסם על כך שאוילר, במהלך ויכוח תאולוגי, טען את הטענה הבאה: "\( \frac{a+b^n}{n}=x \), ולכן אלוהים קיים!" ובן שיחו המסכן שלא ידע מתמטיקה לא יכל לענות. כנראה שמדובר באגדה אורבנית. הנוסחה שבטענה של אוילר אינה נוסחת אוילר המפורסמת, אבל לפעמים מקשרים גם אותה לאגדה הזו. מה שכן, יש הטוענים שנוסחת אוילר (האמיתית) גורמת להם לאמונה באלוהים. לי זה גורם בעיקר לאמונה במתמטיקה.