האלכסון – אסון

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

הגודל כן קובע

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

איזה גודל (?)

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

צ’ומפ צ’ומפ

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

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

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