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

טוב, אז יש לנו פסוק לוגי שמורכב מ-$latex n$ פסוקיות, שבכל אחת שלושה מופעים של משתנים (או שלילתם). אנחנו רוצים להוכיח שקיימת השמה למשתנים שמספקת לפחות $latex \frac{7}{8}$ מהפסוקיות. מה עושים? ראשית, מגדירים את מרחב ההסתברות שלנו. המרחב מוגדר על ידי אוסף של אירועים "בסיסיים" וזרים זה לזה, שלכל אחד הסתברות מסויימת. כאן מה שנעשה …

הקיים הנעלם – הדוגמה ההסתברותית – מבוא לוגי

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

הקיים הנעלם – הדוגמה הרמאית

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

הקיים הנעלם – מבוא

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

אם תרצו, אין זה דמיון

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

ללא חסם

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

ללא גבולות

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

מטרנסצנדנטלי יוצא אלגברי?

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

על משוואות בלי פתרון, ולמה זה לא רציונלי

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