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

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

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

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

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

“אף פעם” הסכים השד מהשביעית.

“אף פעם!” הסכים קהל הסטודנטים באושר.

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

הרשיתי לעצמי להתעלל קצת בגיבורי “השד מהשביעית” (המומלץ מאוד, במיוחד אם אתם רוצים לראות מה התרחש בעימות האמיתי בין השד ובין פרופסור גונוסבסקי) כדי להציג פרדוקס שממבט ראשון נראה לי תמים ואפילו טיפשי, אבל לשמחתי גיליתי שטעיתי והוא הרבה יותר מגניב משחשבתי - פרדוקס בוחן הפתע. כמו בכל פרדוקס, הוא מתאר סיטואציה שבה נראה לנו שקיימת סתירה כלשהי ולא מובן מאליו במבט ראשון מה גורם לה; זה מכריח אותנו לנסות ולבחון את ההנחות ואופני ההסקה שלנו באופן יסודי, ובצורה הזו אנחנו מגלים עליהם דברים מעניינים למדי.

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

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

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

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

מה משותף לשני הניסוחים של הפרדוקס? לדעתי, באופן ברור, זהו מושג הידיעה. מה פירוש הדבר שבוחן הוא מפתיע? זה אומר שביום שבו הוא ניתן, התלמידים אינם יכולים להיות בטוחים שהוא יינתן ביום זה. הם אולי חושדים שהוא ייתנן, או חושבים שיש סיכוי של 54 אחוז, או כל דבר דומה - אבל אין להם ביטחון מוחלט בכך שהוא יינתן. אותו הדבר בדיוק תקף עבור השלט בגב. השוו זאת עם חידת העיניים הכחולות שבה אדם עוזב את האי רק כשהוא בטוח שיש לו עיניים כחולות. מה בכל זאת שונה? בחידת העיניים הכחולות, המידע הנוסף שנותנים לאנשים והם מסיקים ממנו מסקנות הוא שקיים מישהו עם עיניים כחולות; כאן לעומת זאת המידע הנוסף שניתן לתלמידים הוא הרבה יותר מורכב באופיו. ראשית, אומרים להם שיש למישהו שלט על הגב/שיהיה מבחן בשבוע הבא. טוב ויפה, ומכך באמת אי אפשר להסיק למי יש את השלט על הגב (אלא אם אתם התלמיד האחרון בשורה) או באיזה יום יינתן הבוחן (אלא אם הגיע יום חמישי), אבל אז מוסיפים עוד אינפורמציה: שהתלמיד שיש לו שלט על הגב לא יכול לדעת את זה/שהבוחן יהיה “מפתיע”. זה המידע הנוסף שממנו התלמידים מתחילים להסיק מסקנות עד שהם מגיעים לתוצאה שקרית.

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

אז המקרה של תלמיד אחד הוא מנוון במידה מסויימת. מה קורה אם יש שני תלמידים בשורה? נאמר, אריק ובנץ, כשאריק עומד מאחורי בנץ. אם גוסונובסקי אומר להם “יש לאחד מכם שלט על הגב והוא לא יכול לדעת את זה!” אפשר לפרוט את האמירה הזו לפרוטות. מה שגוסונובסקי בעצם אומר הוא “או שלאריק יש שלט על הגב והוא לא יכול לדעת את זה, או שלבנץ יש שלט על הגב והוא לא יכול לדעת את זה”. עכשיו, שימו לב: אם לאריק יש שלט על הגב, יש לנו כאן את אותו כשל בדיוק כמו במקרה הראשון, בלי קשר לבנץ; בכך שגוסונובסקי אומר שלאחד משניהם יש שלט על הגב, ומכיוון שאריק רואה את הגב של בנץ, האמירה הזו שקולה לכך שגוסונובסקי יגיד לאריק “יש לך שלט על הגב ואתה לא יכול לדעת את זה!”. אחר כך, בגלל הכשל הזה, גם אצל בנץ יש כשל דומה. זה לב הפרדוקס.

אבל רגע, את “לאחד מכם יש שלט על הגב והוא לא יכול לדעת את זה!” אפשר לפרוט לפרוטות גם בצורה קצת שונה: “או שלאריק יש שלט על הגב, או שלבנץ יש שלט על הגב והוא לא יכול לדעת את זה”. בניסוח הזה אין פרדוקס בכלל. אם גוסונובסקי היה אומר את זה לאריק ובנץ לא הייתה שום בעיה. ואם בסיפור המקורי גוסונובסקי היה אומר לתלמידים “בשבוע הבא יהיה בוחן! ואם הוא לא יהיה בחמישי, הוא גם יפתיע אתכם!” ודאי שלא הייתה בעיה. עכשיו, אתם ודאי מרגישים שאני מרמה אתכם ושהניסוח הזה, שבו פוסלים את חמישי מלהיות מפתיע, הוא לא פרשנות “נכונה” לאמירה “בשבוע הבא יהיה בוחן פתע”, ולכן ודאי תתאכזבו לגלות שזה הפתרון של הפרדוקס שהכי משביע את הרצון שלי: אני פשוט קורא את דבריו של גוסונובסקי על בוחן פתע בתור “בשבוע הבא יהיה בוחן שיפתיע בכל יום שבו הוא יינתן אלא אם הוא יינתן בחמישי”, ואם התלמידים בוחרים לפרש את האמירה שלו בתור משהו חזק יותר, שטוען שהבוחן יהיה מפתיע בכל יום שבו הוא יינתן, הרי שזו בבירור אמירה שכוללת בתוכה חלק “סתירתי”, כי בחמישי הבוחן לא יכול להפתיע, ולכן אין פלא שהתלמידים מגיעים לסתירה בסופו של דבר.

הנה עוד נקודת מבט על העניין. נניח שכל מה שגוסונובסקי היה אומר לתלמידים הוא “בשבוע הבא יהיה בוחן”. מה האינפורמציה שהתלמידים קיבלו? שבשבוע הבא יהיה בוחן, ושהוא יפתיע בכל יום פרט לחמישי. איך הגעתי לזה? פשוט מאוד - על פי האופן שבו אני מפרש “הפתעה” בפוסט הזה בתור חוסר יכולת לדעת בודאות, זה בדיוק המצב; התלמידים לא מסוגלים להסיק ממה שגוסונובסקי אמר ומתוך היום הנוכחי בשבוע האם מחר יהיה מבחן, פרט לערב יום חמישי. אותו הדבר קורה אם התלמידים עומדים בשורה ומושג ה”הפתעה” כבר לא מפריע לנו: אם גוסונובסקי רק אומר “לאחד מכם יש שלט על הגב”, אז כפועל יוצא מכך, אלא אם השלט הוא על הגב של זה שעומד מאחורה, מי שיש לו שלט על הגב לא מסוגל לדעת את זה. מכאן שאם גוסונובסקי יגיד “לאחד מכם יש שלט על הגב ואם זה לא האחרון בשורה אז הוא גם לא יכול לדעת את זה!” הוא בסך הכל יספק מידע כפול, שהסטודנטים כבר יכולים להסיק בעצמם. אם כן, כל המידע הנוסף שגוסונובסקי נותן לתלמידים ומתחיל את התגלגלות הפרדוקס הוא מידע שהוא סתירתי באופיו: שגם אם לאחרון בשורה יש שלט על הגב הוא לא יכול לדעת את זה. עכשיו, במערכת ההוכחה הסטנדרטית שהמתמטיקאים עובדים איתה, מסתירה אפשר להסיק כל דבר (זה נובע די מייד מהאקסיומות וכללי ההיסק של הלוגיקה, אבל לא אפרט על זה כרגע). אם גוסונובסקי היה אומר לתלמידים “בשבוע הבא יהיה בוחן. אה, ו-1=2”, גם מזה התלמידים היו יכולים להסיק שלא יהיה בוחן בשבוע הבא, אבל מן הסתם לא היינו מתרשמים מזה באותה מידה. לדעתי זה לב הפרדוקס.

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

בגישה המתמטית שאני מציג כאן, המושג של “ידע” מזוהה עם “יכיחות”. לכן אני צריך איזה שהוא סימון כדי לתאר “יכיח”: אני אשתמש ב-\( \mbox{Pr}\left[\varphi\right] \) (מלשון “Provable’’) כדי לומר “הפסוק \( \varphi \) יכיח”. בנוסף, אשתמש במשתנה \( D \) כדי לתאר את היום שבו בוחן הפתע מתקיים. עם הסימונים הללו, אפשר לנסות ולתאר את מה שגוסונובסקי אומר לתלמידים כך (קראו את זה בתור “המבחן יהיה באחד מהימים \( 1,2,3,4,5 \) וגם לכל יום \( n \), אם המבחן לא התקיים עד אליו, לא ניתן להוכיח מכך שהוא יתקיים ביום \( n \)”):

\( S\equiv\left(D\in\left\{ 1,2,3,4,5\right\} \right)\wedge\bigwedge_{n=1}^{5}\left(D\ge n\to\neg\mbox{Pr}\left[D\ge n\to D=n\right]\right) \)

ה-\( S\equiv \) בהתחלה אומר שזה השם שאני נותן לפסוק שמימין ל-\( \equiv \); זה יהיה חשוב בהמשך.

האם הפסוק הזה ממדל טוב את דבריו של גוסונובסקי? לא ממש. בואו ננסה לחשוב איך התלמידים יוכיחו בעזרתו ש-\( D\ne5 \): הם יניחו בשלילה ש-\( D=5 \) (ולכן בפרט \( D\ge5 \)) ולכן כדי להגיע לסתירה די להם להראות ש-\( \mbox{Pr}\left[D\ge5\to D=5\right] \). הבעיה היא שאי אפשר להוכיח את הטענה הזו בלי ידע נוסף - במקרה הזה, ש-\( D\in\left\{ 1,2,3,4,5\right\} \).

“אבל רגע!” אולי אתם אומרים, “הרי הידע הזה הוא בדיוק מה שהיה בחלק השמאלי של הפסוק!”. זה כמובן נכון, אבל הפסוק הזה הוא לא אחת מהאקסיומות שעליהן הסימון \( \mbox{Pr}\left[D\ge n\to D=n\right] \) מדבר כשהוא מדבר על קיום הוכחה אלא אם אנחנו בוחרים להניח את זה במובלע, ואנחנו לא. האקסיומות היחידות שאנחנו מניחים במובלע הן האקסיומות הרגילות של לוגיקה מסדר ראשון. אם אנחנו רוצים עוד אקסיומות, בואו נציין אותן במפורש: נסמן ב-\( \mbox{Pr}_{A}\left[\varphi\right] \) את הטענה “\( \varphi \) יכיח מ-\( A \)”.

אם כן, מה שטבעי לעשות הוא להגדיר

\( A\equiv\left(D\in\left\{ 1,2,3,4,5\right\} \right) \)

ועכשיו להגדיר

\( S\equiv\left(D\in\left\{ 1,2,3,4,5\right\} \right)\wedge\bigwedge_{n=1}^{5}\left(D\ge n\to\neg\mbox{Pr}_{A}\left[D\ge n\to D=n\right]\right) \)

הניסוח הזה קולע לא רע למטרה. בואו נראה שהתלמידים מסוגלים להוכיח איתו ש-\( D\ne5 \). כדי לעשות את זה, התלמידים יניחו בשלילה ש-\( D=5 \), ואז יוכיחו שמתקיים \( \mbox{Pr}_{A}\left[D\ge5\to D=5\right] \) על ידי כך ש-\( A \) נותן לנו ש-\( D\le5 \) ולכן אם \( D\ge5 \) אז \( D=5 \), שזו דרך אחרת לכתוב \( D\ge5\to D=5 \).

רק שעכשיו התלמידים בברוך. השלב הבא הוא להוכיח ש-\( D\ne4 \), ואז זה הם לא יכולים לעשות מתוך \( A \). בואו ניזכר שניה איך הטיעון אמור ללכת עכשיו: התלמידים יניחו בשלילה ש-\( D=4 \). עכשיו הם רק צריכים להראות שמתקיים \( \mbox{Pr}_{A}\left[D\ge4\to D=4\right] \). ההוכחה תלך ככה: בגלל שאנחנו יודעים ש-\( D\le4 \)… רגע, רגע, רגע! מה זה “אנחנו יודעים”? מי יודע? אם כל מה שההוכחה יכולה להשתמש בו הוא \( A \), אז ההוכחה לא יודעת ש-\( D\ne5 \), ובלי הידע הזה לא ניתן להוכיח ש-\( D\le4 \) וההוכחה הולכת לכל הרוחות.

כדי להסיק את \( D\ne5 \) בתוך ההוכחה של \( D\ge4\to D=4 \), ההוכחה הזו צריכה לקבל כאקסיומה בדיוק את הכלי שהיה לסטודנטים כשהם הוכיחו ש-\( D\ne5 \), והכלי הזה הוא הנוסחה \( S \) עצמה. זה לב העניין. אנחנו רואים שהמעגליות הזו היא קריטית עבור הטיעון של התלמידים. במילים אחרות, הניסוח הנכון של \( S \) הוא זה:

\( S\equiv\left(D\in\left\{ 1,2,3,4,5\right\} \right)\wedge\bigwedge_{n=1}^{5}\left(D\ge n\to\neg\mbox{Pr}_{S}\left[D\ge n\to D=n\right]\right) \)

כאן אפשר לעצור ולהגיד “יש מעגליות? לא משחקים!”. לגיטימי. אפשר גם לומר “אין שום דרך לכתוב פסוק \( S \) כזה בגלל שהוא מכיל את עצמו וזו סתירה” או משהו בסגנון, אבל זה כבר לא יהיה לגיטימי. אחד מהקסמים המגניבים ביותר בלוגיקה - קסם שהוא בעל תפקיד חשוב בהוכחת משפט אי השלמות של גדל - הוא שאפשר לבנות פסוקים שמתייחסים כך לעצמם, בעזרת טכניקה עקיפה ומחוכמת שלא אציג כרגע אבל בפוסט שלי על הוכחת משפט גדל היא מופיעה. לעת עתה תצטרכו לסמוך עלי - פסוק כמו \( S \) אפשר לכתוב בצורה הכי פורמלית בעולם.

בניסוח הזה של הפרדוקס אפשר להוכיח פורמלית שניתן להוכיח מתוך \( S \) את זה ש-\( D\notin\left\{ 1,2,3,4,5\right\} \), ובמילים אחרות - ש-\( S \) סותר את עצמו. זה פותר במובן מסויים את הפרדוקס; כעת ברור מה הניסוח של הטענה של גוסונובסקי שממנו התלמידים מסוגלים להסיק את המסקנה שלהם, וגם די ברור שכשגוסונובסקי אומר “יהיה בוחן פתע”, האינטואיציה הראשונה שלנו לא מבינה את דבריו בתור משהו מורכב כמו \( S \) ולכן אנחנו לא רואים כאן בעיה. גם כאן זו נקודה שאפשר לעצור בה, אבל אני רוצה להמשיך עוד קצת, למאמר חדש יחסית מ-2010 של רן רז ושירה קריצ’מן ממכון וייצמן שלוקח את הרעיון קצת יותר רחוק.

הטענה שלהם היא כזו: מכיוון ש-\( S \) סתירתי, אפשר להוכיח ממנו הכל (וכבר הזכרתי זאת בפוסט). אבל אם אפשר להוכיח ממנו הכל, אפשר להוכיח גם שהמבחן יהיה ביום חמישי וגם שהוא יהיה ביום רביעי. אם כן, האם באמת אפשר לזהות “יכיחות” עם “ידיעה” כאן? אם אני רוצה לדעת מיהו ספרטקוס, וכולם אומרים לי שהם ספרטקוס, האם זה הוסיף לי ידע? כנראה שלא. לכן אנחנו רוצים לזהות ידע כאן עם “התלמידים יכולים להוכיח שהמבחן מתקיים ביום \( n \) ולכל יום אחר הם לא יכולים להוכיח שהמבחן מתקיים ביום האחר”. באופן פורמלי \( S \) יראה כך:

\( S\equiv\left(D\in\left\{ 1,2,3,4,5\right\} \right)\wedge\bigwedge_{n=1}^{5}\left[D\ge n\to\left(\neg\mbox{Pr}_{S}\left[D\ge n\to D=n\right]\vee\bigvee_{k\ne n}\mbox{Pr}_{S}\left[D\ge n\to D=k\right]\right)\right] \)

החלק הפנימי אומר הפעם “אם המבחן לא התקיים עד יום \( n \), אז או שאי אפשר להוכיח שהוא יתקיים ביום \( n \), או שיש \( k\ne n \) שגם עבורו אפשר להוכיח שהמבחן יתקיים ביום \( k \)”.

כעת, נניח שהתלמידים רוצים להוכיח ש-\( D\ne5 \). הם מניחים בשלילה ש-\( D=5 \), וכמו קודם הם מוכיחים ש-\( \mbox{Pr}_{S}\left[D\ge5\to D=5\right] \). לרוע מזלם, הפעם זה לא מספיק כדי להסיק ש-\( D\ne5 \); חייבים גם להוכיח שעבור \( 1\le k\le4 \) מתקיים \( \neg\mbox{Pr}_{S}\left[D\ge5\to D=k\right] \).

“רגע אחד!” אולי אתם אומרים. “אבל מה ההגיון בטענה כמו \( D\ge5\to D=4 \)? הרי ברור שהיא לא נכונה!” זה כמובן נכון; אבל למה שזה יאמר שהתלמידים לא יהיו מסוגלים להוכיח את זה? הם יהיו מסוגלים להוכיח את זה, בתנאי שמערכת ההוכחה שלהם לא עקבית. זה מעלה את השאלה - מהי בכלל מערכת ההוכחה של התלמידים?

מהשאלה הזו נמנעתי עד כה. גרמתי לכם לחשוב שמדובר על לוגיקה מסדר ראשון ותו לא, אבל כדי לפרמל מושגים כמו \( \mbox{Pr} \) בתוך הלוגיקה עצמה חייבים להסתמך על שפה ומערכת אקסיומות שמסוגלות לבטא די הרבה דברים; וממילא אנחנו כנראה מניחים אינטואיטיבית שלתלמידים מותר להוכיח כל הוכחה שמתמטיקאי “רגיל” יכול להוכיח. במילים אחרות, אנחנו מניחים שאנחנו מעל ZF, מערכת האקסיומות הסטנדרטית של המתמטיקה. ומה שמשפט אי השלמות השני של גדל אומר הוא שאין לנו דרך להוכיח שהמערכת הזו עקבית “מתוך” המערכת.

איך זה מתקשר לבעיה של התלמידים? שהם יכולים להוכיח ש-\( D\ne5 \), מתוך ZF, רק אם הם ישללו את זה שאפשר להוכיח בה \( D\ge5\to D=4 \), כלומר רק אם הם ישללו את זה ש-ZF יכולה להוכיח סתירה, כלומר רק אם הם יכולים להוכיח ש-ZF עקבית. אבל זה בדיוק מה שמשפט אי השלמות השני של גדל מראה שאי אפשר לעשות.

הטיעון הוא למעשה קצת יותר עדין מזה. אם התלמידים מניחים ש-ZF עקבית, כמו שכל מתמטיקאי עושה, אז מההנחה הזו ינבע שאי אפשר להוכיח את \( D\ge5\to D=4 \) ולכן התלמידים יצליחו להוכיח ש-\( D\ne5 \) (בהנחה ש-ZF עקבית; אבל אם ZF לא עקבית על אחת כמה וכמה אפשר להוכיח ש-\( D\ne5 \)). הבעיה תהיה בצעד הבא: כדי להוכיח ש-\( D\ne4 \) התלמידים צריכים להוכיח ש-\( \mbox{Pr}_{S}\left[D\ge4\to D=4\right] \), אבל זה לא נכון: אי אפשר להוכיח את \( D\ge4\to D=4 \) רק מתוך \( S \) כי בשביל ההוכחה הזו צריך קודם כל להוכיח ש-\( D\ne5 \) ובשביל זה צריך להניח ש-\( \mbox{ZF} \) עקבית. במילים אחרות, צריך להחליף את \( S \) ב-\( S\wedge\mbox{CON}\left(\mbox{ZF}\right) \). אבל אם נעשה את זה, נקבל מערכת חדשה, שגם את העקביות שלה אי אפשר להוכיח… אני מקווה שאתם מבינים את העיקרון.

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