פרדוקס בוחן הפתע

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

עכשיו בחנויות – "גדל, אשר, באך" בעברית!

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

משפט אי השלמות של גדל – מה הוא ממש, ממש לא

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

כלל ה-0-1 של גרפים – ההוכחה

בפעם הקודמת ניסחתי את כלל ה-0-1, ולכן עכשיו אגש להוכחה שלו בלי שהיות. הרעיון הבסיסי בהוכחה הוא פשוט מאוד, אבל גם מקסים: הבה ונתבונן בתורה $latex T$, שהפסוקים שלה הם בדיוק אותם פסוקים שמתארים תכונות $latex \mathcal{P}$ עם הסתברות 1. … להמשיך לקרוא

משפט אי השלמות הראשון של גדל – איך (בערך) מוכיחים אותו?

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

משפטי אי השלמות של גדל – מה הם כן אומרים?

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