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

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

למה אין מידה על כל הישר הממשי

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

ההוכחה הטופולוגית לקיום אינסוף ראשוניים

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

צ’ומפ צ’ומפ

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

שורש, ההוכחה (חלק ב’)

פרוטוקול הוכחת אפס-הידע שאני עומד להציג נקרא "פרוטוקול פיאט-שמיר", על שם שני ממציאיו הישראליים – עמוס פיאט ועדי שמיר (את עדי שמיר הזכרתי כבר במובלע לפחות פעמיים בפוסטים קודמים – הוא זה שהוכיח שהוכחות אינטראקטיביות שקולות למחלקה PSPACE, והוא ה-S … להמשיך לקרוא

מוכיחים את הלא נודע

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

בסיס מוצק מי ימצא

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

לבחור או לא לבחור – זו השאלה

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

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

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

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

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

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

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

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

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