איזה גודל (?)

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

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

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

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

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

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

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

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

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

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

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

1. עוצמת הקבוצה הריקה היא 0.
2. אם X היא קבוצה לא ריקה, עוצמתה היא כעוצמת X לאחר שהוסר ממנה איבר כלשהו באופן שרירותי, ועוד 1.

כך קבוצות בעלות איבר בודד יהיו מעוצמה 1 (כי אחרי שמוסר האיבר הזה קיבלנו את הקבוצה הריקה) וכן הלאה.

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

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

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

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