סודרים – התיאור הפורמלי

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

סודרים – מה זה בכלל? (הסבר אינטואיטיבי תוך כדי משחק)

בפוסט הקודם דיברתי על האופן שבו קנטור "המציא" את הסודרים, אך כפי שיתברר בפוסט הזה, כנראה שהמילה "תגלית" יותר הולמת. קנטור הגיע אל הסודרים על ידי כך שהוא הגדיר סדרת קבוצות $latex P^{\left(1\right)},P^{\left(2\right)},\dots$ ושם לב שיש משמעות גם לקבוצה $latex P^{\left(\infty\right)}$ שמתקבלת כמעין "גבול" של הקבוצות עד אליה, ושאחרי שיש לנו אותה, יש משמעות גם …

איך קנטור המציא את הסודרים?

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

משפט רייס – הגרסה המלאה

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

IP=PSPACE – ההוכחה (חלק ב')

בפוסט הקודם שעסק בהוכחה ש-$latex \mbox{IP}=\mbox{PSPACE}$ הראיתי מערכת הוכחה אינטראקטיבית עבור השפה $latex \overline{3\mbox{SAT}}$. זו הייתה הדוגמה הראשונה למערכת הוכחה "רצינית", כזו שמשתמשת בכל הכוח של האינטראקטיביות; במערכות האחרות שהראיתי תוך סיבוב או שניים המשחק נגמר, ואילו כאן ההוכחה הייתה דיאלוג ארוך ומתמשך, שבו לאט לאט המוכיח והמוודא התקרבו אל עצם העניין. הרעיון, כזכור, היה …

מדוע "הקנון המדעי" לא כולל מתמטיקה?

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

IP=PSPACE – ההוכחה (חלק א')

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

מה האסוציאציה שלכם ל-?=(1+2)2÷6?

מהומה בפייסבוק. מישהו פתח סקר עם השאלה הפשוטה: $latex 6\div 2(1+2)=? $ ושתי תשובות אפשריות – 1 ו-9. התוצאה? כרגע יש בסביבות ה-1,300,000 מצביעים עבור 1, 1,700,000 מצביעים עבור 9 ודיון בן למעלה מ-100,000 תגובות. מה לעזאזל? חשבתי להתעלם מזה ולהטיף לאנשים להתעסק במתמטיקה רצינית במקום זה. למעשה, זה עדיין מה שאני מציע לעשות; אבל …