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

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

הגודל כן קובע

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

איזה גודל (?)

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

צ’ומפ צ’ומפ

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

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

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