הקיים הנעלם - מבוא

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

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

אבל מה זו בעצם “הוכחה קונסטרוקטיבית”? הרעיון (עד כמה שאני מבין אותו) הוא פשוט: אני רוצה להראות שקיים אובייקט שמקיים תכונה כלשהי - אני אומר במפורש מהו האובייקט, או לפחות מצביע על דרך שיטתית שמצליחה תמיד כדי לבנות אותו. הנה דוגמה קלאסית: המשוואה \( ax^2+bx+c \). נניח שאני רוצה לשכנע אתכם שיש פתרון למשוואה תוך שאני מצביע לכם על דרך למצוא אותו - אני אשתמש במה שמכונה “נוסחת השורשים”, ומשמשת להתעללות בתלמידי תיכון:

\( x=\frac{-b\pm\sqrt{b^2-4ac}}{2a} \)

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

כדי להשיג פתרון, בצע את הפעולות הבאות:

1. חשב את \( b^2-4ac \)
2. הוצא שורש לתוצאה.
3. הפחת את \( b \) מהתוצאה.
4. חלק את הכל ב-\( 2a \)
5. קיבלת פתרון!

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

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

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

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

אם כבר הזכרתי את העיקרון, הנה הדגמה נאה (ונפוצה מאוד) של השימוש בו, כדי להוכיח שבחיפה יש שני אנשים עם בדיוק אותו מספר שערות על הראש: ידוע שלאדם יש בממוצע 100,000 שערות על הראש (ויקיפדיה טוענת שלבלונדינים זה מגיע עד לסביבות ה-150,000), אפשר להניח די בביטחון שאין בחיפה אנשים עם יותר מ-250,000 שערות על הראש (ואם יש, מספרם זניח ביותר ואפשר להתעלם מהם). אלא שבחיפה יש יותר מ-250,00 אנשים; כעת, היונים שלנו יהיו האנשים, וה”שובכים” יהיו מספר השערות שעל הראש (למשל, יש שובך עבור “בדיוק 14,363 שערות על הראש”). נחלק את היונים לשובכים בצורה המתבקשת - כל אדם ייכנס לשובך של מספר השיערות שיש לו על הראש (וכך למשל כל הקירחים יכנסו לשובך מס’ 0). מכיוון שיש לכל היותר 250,000 שובכים ויש יותר מ-250,000 יונים, קיבלנו שיש שני אנשים עם אותו מספר שערות על הראש. מיהם? מה מספר השיערות? לא יודע, בשביל זה צריך בדיקה ישירה (אמנם, הקירחים מקלקלים את החגיגה, אבל גם אותם אפשר לגרש ולהישאר רק עם בעלי רעמה, והתוצאה עדיין תהיה נכונה).