תורת הקבוצות - לכסונים, או למה יש אינסוף אינסופים?

אז איך משווים קבוצות אינסופיות?

בפוסט הקודם בסדרת הפוסטים שלי על תורת הקבוצות הצגתי את הכלי הבסיסי שלנו להשוואת גדלים של קבוצות: אמרתי שאם קיימת פונקציה \( f:A\to B \) שהיא חד-חד-ערכית ועל אז אנחנו אומרים ש-\( A,B \) הן שוות עוצמה ומסמנים את זה ב-\( A\sim B \) או ב-\( \left|A\right|=\left|B\right| \). הגדרתי “קבוצה סופית” בתור קבוצה שמקיימת \( A\sim n \) עבור מספר טבעי \( n \) כלשהו (זכרו: \( n \), פורמלית, הוא קבוצת הטבעיים הקטנים מ-\( n \)) והגדרתי “קבוצה אינסופית” בתור קבוצה לא סופית. סיימנו בלראות שלכל קבוצה אינסופית \( A \), קיימת פונקציה \( f:\mathbb{N}\to A \) שהיא חד-חד-ערכית אבל לא בהכרח על ואמרתי שאינטואיטיבית, זה אומר ש-\( A \) גדולה לפחות כמו \( \mathbb{N} \). בואו נתחיל מלפרמל את האינטואיציה הזו.

כרגיל, שווה להתחיל מהמקרה הקונקרטי של קבוצות סופיות. אם \( A,B \) סופיות ויש \( f:A\to B \) שהיא חח”ע אבל לא על אז אפשר להוכיח ש-\( \left|A\right|<\left|B\right| \). עבור קבוצות אינסופיות זה פחות פשוט. למשל, הפונקציה \( f:\mathbb{N}^{+}\to\mathbb{N} \) שמוגדרת בתור \( f\left(n\right)=n \) היא חח”ע אבל לא על כי \( 0 \) לא שייך ל-\( \mathbb{N}^{+} \) אבל כן שייך ל-\( \mathbb{N} \). מצד שני, זה שהפונקציה הספציפית הזו היא לא על לא אומר שאי אפשר למצוא פונקציה אחרת שהיא כן: במקרה שלנו, \( g\left(n\right)=n-1 \) היא חח”ע ועל ולכן מוכיחה ש-\( \left|\mathbb{N}^{+}\right|=\left|\mathbb{N}\right| \). בקבוצות סופיות זה פשוט לא היה יכול לקרות, שיש לנו פונקציה חח”ע ולא על אבל אפשר למצוא אחת שהיא כן חח”ע ועל.

לכן אנחנו נוקטים בהגדרה הבאה: אם \( A,B \) קבוצות כך ש-\( f:A\to B \) היא פונקציה חח”ע (ולאו דווקא על; לא אוסרים עליה להיות על) אז מסמנים זאת \( \left|A\right|\le\left|B\right| \). שימוש בסימון כזה בחופשיות הוא מסוכן, כי האינטואיציה שלנו מאי-שוויונים “רגילים” היא שצריך להתקיים הדבר הבא: אם \( \left|A\right|\le\left|B\right| \) וגם \( \left|B\right|\le\left|A\right| \) אז צריך להתקיים \( \left|A\right|=\left|B\right| \). למרבה המזל, הטענה הזו נכונה: היא נקראת “משפט קנטור-שרדר-ברנשטיין”. הנה עוד ניסוח שלה, קצת יותר מפורש:

משפט קנטור-שרדר-ברנשטיין: אם קיימת פונקציה \( f:A\to B \) חח”ע ופונקציה \( g:B\to A \) חח”ע אז קיימת פונקציה \( h:A\to B \) חח”ע ועל.

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

עכשיו, משיש לנו מושג של “קטן-שווה” עבור קבוצות אינסופיות, זמן לשאול האם יש לנו גם מושג של “קטן ממש”. כלומר, האם קיימות \( A,B \) כך שיש פונקציה \( f:A\to B \) שהיא חח”ע אבל לא על, ופשוט לא קיימת פונקציה חח”ע ועל מ-\( A \) אל \( B \). כלומר, שמתקיים \( \left|A\right|\le\left|B\right| \) אבל \( \left|A\right|\ne\left|B\right| \). דבר כזה יסומן בתור \( \left|A\right|<\left|B\right| \). כאן האינטואיציה הראשונית יכולה להיות שברור שזה קיים כי למשל \( \mathbb{N}^{+} \) היא כמו \( \mathbb{N} \) רק בלי המספר 0 ולכן \( \mathbb{N}^{+} \) היא “קטנה יותר”, אבל כאמור - יש לנו פונקציה חח”ע ועל ביניהן, אז הן מאותו גודל. הבלבול שהדבר הזה גורם התבטא בפרדוקס של גלילאו, עם קבוצת הטבעיים וקבוצת הריבועים של טבעיים, שגם הן באותו גודל למרות שהתחושה היא שבקבוצת הריבועים יש “הרבה פחות” - הבלבול הזה גרם לגלילאו למשוך את ידיו מכל העיסוק בקבוצות אינסופיות.

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

האלכסון של קנטור

הדוגמא הראשונה לשתי קבוצות אינסופיות שהאחת גדולה מהשניה ניתנת באמצעות טיעון שנקרא “האלכסון של קנטור” וכבר כתבתי עליו פוסט בראשית ימי הבלוג, אבל הנה הזדמנות טובה להציג אותו שוב. הרעיון הוא להראות שעוצמת המספרים הטבעיים קטנה מעוצמת המספרים הממשיים: \( \left|\mathbb{N}\right|<\left|\mathbb{R}\right| \). ברור ש-\( \left|\mathbb{N}\right|\le\left|\mathbb{R}\right| \) כי הפונקציה \( f\left(n\right) \) מ-\( \mathbb{N} \) אל \( \mathbb{R} \) היא חח”ע; רק נשאר להוכיח שפשוט לא קיימת פונקציה חח”ע ועל מ-\( \mathbb{N} \) אל \( \mathbb{R} \).

כדי לפשט את הנימוק מספיק להראות שלא קיימת פונקציה חח”ע ועל מ-\( \mathbb{N} \) אל הקטע הפתוח \( \left(0,1\right) \) של כל המספרים הממשיים בין 0 ו-1, כי לא כזה קשה להראות (לא הפעם!) ש-\( \left(0,1\right)\sim\mathbb{R} \), אז אם היה מתקיים \( \mathbb{N}\sim\mathbb{R} \) היה נובע מכך ש-\( \mathbb{N}\sim\left(0,1\right) \). כרגע עדיין לא ברור איך לדבר על \( \left(0,1\right) \) מפשט משהו, אבל זה יגיע בקרוב - בינתיים השאלה הדוחקת יותר היא איך בכלל מרים משהו בסגנון “לא קיימת פונקציה חח”ע ועל מ-\( \mathbb{N} \) לאנשהו”. זה בעצם האתגר הגדול של המתמטיקה באופן כללי: אם משהו קיים, אז לעתים קרובות אפשר פשוט להציג אותו וזהו (זה לא תמיד המצב, כפי שמלמדת אותנו אקסיומת הבחירה, אבל זה לפעם אחרת). אבל אם משהו לא קיים, איך נראה את זה? לכאורה אנחנו צריכים לעבור על כל הפונקציות האפשריות ביקום בין \( \mathbb{N} \) ו-\( \left(0,1\right) \) ולהראות שאף אחת מהן היא לא חח”ע ועל. איך נעשה את זה? מאיפה נתחיל? זו נראית כמו משימה מפלצתית! וזה גם בדיוק מה שנעשה, וזה לא ייקח לנו יותר מכמה שורות ספורות (אם ממש רוצים, אפשר לקצר את ההוכחה לשורה אחת).

הרעיון הוא לקחת פונקציה \( f:\mathbb{N}\to\left(0,1\right) \) כלשהי, בלי להניח עליה שום הנחות, ולהוכיח שהיא לא יכולה להיות על. אמרתי לפני רגע שאם משהו קיים אז אפשר להציג אותו וזהו? זה מה שנעשה! אנחנו הולכים להציג מספר ב-\( \left(0,1\right) \) שלא שייך לתמונה של \( f \) - כלומר, שאין \( n\in\mathbb{N} \) כך ש-\( f\left(n\right) \) שווה אליו, ונעשה זאת על ידי כך שנבנה אותו בצורה מפורשת, כמובן בעזרת \( f \) עצמה.

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

\( \begin{array}{ccccccccc} f\left(0\right) & = & 0 & . & 3 & 5 & 8 & 1 & \ldots\\ f\left(1\right) & = & 0 & . & 4 & 4 & 4 & 4 & \ldots\\ f\left(2\right) & = & 0 & . & 5 & 8 & 7 & 6 & \ldots\\ f\left(3\right) & = & 0 & . & 4 & 3 & 4 & 3 & \ldots\\ & \vdots \end{array} \)

הרעיון בצורת הכתיבה הוא זה: לכל מספר טבעי \( n \), הפלט \( f\left(n\right) \) של הפונקציה \( f:\mathbb{N}\to\left(0,1\right) \) הוא איבר של \( \left(0,1\right) \). מספר כזה הוא מספר ממשי בין 0 ל-1, וככזה אפשר להציג אותו בעזרת ייצוג עשרוני שהוא מהצורה “משהו נקודה משהו משהו משהו”. מכיוון שהמספר הוא בין 0 ל-1, לא כולל 1, מה שיש משמאל לנקודה הוא תמיד 0; נשאר לנו האקשן שמתרחש מימין לנקודה, שאני כותב כמו מין מערך של ספרות. \( f\left(0\right)=0.3581\ldots \), כאשר שלוש הנקודות אומרות “ומכאן והלאה זה נמשך עד אינסוף בדרך כלשהי”. שימו לב שגם במספר כמו \( 0.5 \) שלכאורה יש לו רק מספר סופי של ספרות אחרי הנקודה העשרונית, בעצם יש אינסוף כי גם 0 היא ספרה: \( 0.5=0.5000\ldots \). אחרי ארבעת האיברים שכתבתי במפורש הוספתי שלוש נקודות אנכיות שרומזות שמה שהולך פה נמשך בצורה דומה עם הפעלה של \( f \) על כל הטבעיים.

עכשיו אני רוצה לבנות מספר \( d \) שיהיה בעל שתי תכונות:

1. \( d\in\left(0,1\right) \), כלומר \( d \) שייך לקטע ש-\( f \) אמורה לתפוס במלואו.
2. \( f \) לא תופסת את \( d \). כלומר, לכל \( n\in\mathbb{N} \), מתקיים \( f\left(n\right)\ne d \).

האופן שבו אעשה את זה יהיה לבנות את \( d \) ספרה-ספרה. יש לי אינסוף ספרות לבחור, ואני “אנצל” כל ספרה שאבחר עבור \( d \) כדי “לנטרל” את האפשרות של אחד מהמספרים הטבעיים לתפוס את \( d \). הספרה הראשונה של \( d \) תיבחר בצורה כזו שמבטיחה ש-\( f\left(0\right)\ne d \), הספרה השניה של \( d \) תיבחר בצורה כזו שמבטיח ש-\( f\left(1\right)\ne d \) וכן הלאה.

מכיוון ש-\( d\in\left(0,1\right) \) הוא מתחיל תמיד ב-\( 0. \) ואז הספרות שמימין לנקודה העשרונית, שהן מה שאני בוחר. עכשיו, \( f\left(0\right) \) מתחיל עם הספרה 3, אז אני אתחיל לבנות את \( d \) עם הספרה \( 4 \). כלומר, כרגע המצב הוא זה: \( d=0.4\ldots \), כששלוש הנקודות אומרות “עדיין לא החלטתי מה יהיה שם”. כבר במצב הזה אנחנו יודעים בודאות ש-\( f\left(0\right)\ne d \), פשוט כי הם נבדלים בספרה הראשונה, ושני מספרים ממשיים הם זהים רק אם יש להם את אותו פיתוח עשרוני (עד כדי מקרה קצה אחד שאתייחס אליו בפירוט בהמשך).

נעבור ל-\( f\left(1\right) \). הוא מתחיל גם ב-\( 0.4 \), אז עדיין ייתכן בתיאוריה ש-\( d=0.4\ldots \) יהיה שווה אליו. אבל יש לנו חופש בחירה - עוד לא בחרנו את הספרה השניה של \( d \). אז פשוט נבחר אותה להיות משהו שונה מ-4, נאמר 3. קיבלנו את \( d=0.43\ldots \) שבבירור שונה מ-\( f\left(1\right)=0.44\ldots \).

עבור \( f\left(2\right) \) נראה שאין מה לעשות - הוא מתחיל ב-\( 0.58\ldots \) ששונה מאוד מ-\( d=0.43\ldots \), אבל למה לסבך את שיטת העבודה שלי? שיטת העבודה כרגע אומרת - תבחר את הספרה הבאה שלך (במקרה שלנו, הספרה השלישית ב-\( d \)) כך שהיא שונה מהספרה באותו מקום במספר הנוכחי שאתה “תוקף”. במקרה הזה הספרה היא 7, אז נבחר… אה… 4? ונקבל \( d=0.434\ldots \). אחר כך נעבור לספרה הרביעית ב-\( f\left(3\right) \) שהיא 3 ושוב נבחר 4, ונקבל \( d=0.4344\ldots \) וכך זה יימשך עוד ועוד.

יש לנו אינסוף צעדים, ובכל צעד נפסל אחד מהמספרים הטבעיים \( n \) מלקיים \( f\left(n\right)=d \). מכיוון שזה קורה לכל הטבעיים, תכונה 2 שרצינו עבור \( d \) מתקיימת. זה מוכיח שה-\( f \) שהצגתי לא תופסת את כל הקטע \( \left(0,1\right) \) ומסיים את הסיפור מבחינה. אבל מה עם פונקציות אחרות?

ובכן, לא הצגתי את \( f \) יותר מדי לעומק, נכון? הצגתי רק כמה איברים ראשונים וזהו. אחרי ש”הבנו את הקטע” היה אפשר להמשיך בצורה דומה גם לאיבר שלא ראינו. אז את אותו טיעון אפשר להחיל על כל \( f \) שהיא. בואו ננסח עכשיו את הטיעון הפורמלי, שרק ידרוש מאיתנו עוד כמה סימונים קונקרטיים. אני אקח \( f:\mathbb{N}\to\left(0,1\right) \) כללית ואסמן את איבריה באופן הבא:

\( \begin{array}{ccccccccc} f\left(0\right) & =a_{0}= & 0 & . & a_{0}^{0} & a_{0}^{1} & a_{0}^{2} & a_{0}^{3} & \ldots\\ f\left(1\right) & =a_{1}= & 0 & . & a_{1}^{0} & a_{1}^{1} & a_{1}^{2} & a_{1}^{3} & \ldots\\ f\left(2\right) & =a_{2}= & 0 & . & a_{2}^{0} & a_{2}^{1} & a_{2}^{2} & a_{2}^{3} & \ldots\\ f\left(3\right) & =a_{3}= & 0 & . & a_{3}^{0} & a_{3}^{1} & a_{3}^{2} & a_{3}^{3} & \ldots\\ & \vdots \end{array} \)

באופן כללי: אני קורא ל-\( f\left(n\right) \) בשם \( a_{n}=f\left(n\right) \), ואז כותב את \( a_{n} \) בתור סדרה של ספרות אחרי הנקודה העשרונית: \( a_{n}=0.a_{n}^{0}a_{n}^{1}\dots \). לספרה הראשונה אחרי הנקודה העשרונית אני קורא \( a_{n}^{0} \), לספרה השניה אני קורא \( a_{n}^{1} \) וכן הלאה. זה מאפשר לי להתייחס לכל תא ב”טבלה” שלעיל בצורה מפורשת.

ועכשיו אני בונה את \( d=0.d^{0}d^{1}d^{2}\ldots \) שלי בצורה הפשוטה הבאה:

\( d^{n}=\begin{cases} 4 & a_{n}^{n}\ne4\\ 3 & a_{n}^{n}=4 \end{cases} \)

במילים אחרות, אני אומר - כדי להחליט מה תהיה הספרה ה-\( n \)-ית בתוך \( d \), אני מסתכל מה הספרה ה-\( n \)-ית במספר \( a_{n} \). אם הספרה הזו ב-\( a_{n} \) שונה מ-4, אז אני אבחר אותה ב-\( d \) להיות 4. אם היא דווקא הייתה שווה ל-4, אני אבחר אותה להיות 3, כדי שתהיה שונה מ-4. סוף הסיפור: לכל \( n\in\mathbb{N} \), \( d\ne f\left(n\right) \) כי הן נבדלות בספרה ה-\( n \)-ית.

אם נסתכל שוב על הטבלה שלמעלה, אפשר לראות שהאופן שבו אני בונה את \( d \) הוא על ידי כך שאני לוקח את האלכסון של הטבלה (שבו נמצאים \( a_{0}^{0},a_{1}^{1},a_{2}^{2} \) וכן הלאה) וסוג של “הופך” אותו. לכן השיטה הזו נקראת האלכסון של קנטור, אבל אני משתדל לא לשים יותר מדי דגש על האספקט הויזואלי הזה שלה, כי הנסיון שלי הוא שזה מקשה על הבנה של שלל ההכללות האפשריות של השיטה, שברובן כבר אין ציור נחמד של אלכסון שאפשר להשתמש בו.

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

ובכן, הבעיה הבסיסית שלא התייחסתי אליה עדיין היא ש-\( 0.999\ldots=1 \).

השוויון הזה נראה שגוי? ובכן, יש לי פוסט בנושא, גם כן מראשית ימי הבלוג. השוויון נכון לגמרי (לא “בקירוב” או “בשאיפה”), ולא רק הוא: כל מספר עשרוני שמסתיים בסדרה אינסופית של 9 ניתן בעצם לכתיבה בשתי דרכים שונות. למשל, \( 0.4999\ldots=0.5000\ldots \). הבשורות הטובות הן שזה היוצא מן הכלל היחיד - כל מספר ממשי שלא מסתיים בסדרה אינסופית של 0 או 9 ניתן לכתיבה רק בדרך אחת.

למה זה לא יוצר בעיות? ראשית, שימו לב שהמספר שאני בונה כולל רק את הספרות 3 ו-4, כך שזה לא יכול לקרות לו - יש לו ייצוג יחיד. לכן בפרט לא ייתכן שאני אבנה “בטעות” את \( 0.999\ldots \) ולכן אבנה בפועל מספר שלא שייך ל-\( \left(0,1\right) \). שנית, בהחלט ייתכן שהשטיק הזה של ה-\( 999 \) יקלקל לי את טיעון ה”שונה בספרה אחת”. למשל, אם בניתי עד כה את \( d=0.44\dots \) והמספר הבא שאני תוקף הוא \( 0.443999\ldots \), אז אני אוסיף ל-\( d \) את הספרה \( 4 \) ואקבל \( d=0.444\ldots \) שאינו שונה מ-\( 0.443999\ldots \) בספרה השלישית. כל הטיעון שלי קורס! אבל, למרות ש-\( d \) לא שונה מהמספר הזה בספרה השלישית, הוא בהכרח שונה ממנו בכל יתר הספרות כי יתר הספרות במספר ההוא הן 9, ואילו אצלי הן 3 ו-4. או במילים פשוטות יותר: מכיוון ש-\( d \) נבנה בצורה כזו שהוא בעל ייצוג יחיד, הוא אוטומטית שונה מכל המספרים שאינם בעלי ייצוג יחיד, ונשאר רק לבחון אם הוא שונה מהמספרים שהם כן בעלי ייצוג יחיד.

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

משפט קנטור על קבוצת החזקה

מה שראינו באלכסון של קנטור הוא שיש לפחות שני גדלים שונים של אינסוף: זה של \( \mathbb{N} \) וזה של \( \mathbb{R} \). עכשיו, במחי הוכחה שהיא אפילו עוד יותר קצרה, אני אוכל להראות שיש אינסוף גדלים שונים של אינסוף. הנה הטענה: אם \( A \) היא קבוצה כלשהי (סופית, לא סופית, לא משנה מה), אז \( \left|A\right|<\left|\mathcal{P}\left(A\right)\right| \) כאשר כאן \( \mathcal{P}\left(A\right)\triangleq\left\{ B\ |\ B\subseteq A\right\} \) היא קבוצת החזקה של \( A \) - אוסף כל תתי-הקבוצות של \( A \). עבור קבוצות סופיות אנחנו יודעים שזה נכון כי יש לנו את השוויון \( \left|\mathcal{P}\left(A\right)\right|=2^{\left|A\right|} \) וכמובן ש-\( n<2^{n} \) לכל מספר טבעי, כולל 0. אבל מה קורה עם קבוצות אינסופיות?

ראשית, צריך להוכיח ש-\( \left|A\right|\le\left|\mathcal{P}\left(A\right)\right| \) כלומר שיש פונקציה חח”ע מ-\( A \) אל \( \mathcal{P}\left(A\right) \). את זה קל לעשות: הפונקציה \( f\left(a\right)=\left\{ a\right\} \) עובדת. לכן כל מה שנשאר לעשות הוא להוכיח ש-\( \left|A\right|\ne\left|\mathcal{P}\left(A\right)\right| \) ואת זה הוכיח קנטור באמצעות טיעון שמאוד מזכיר את טיעון האלכסון שלו, אבל יש מצב שבמבט ראשון ייראה לא קשור בעליל.

ובכן, קנטור אומר את הדבר הבא: בואו ניקח פונקציה \( f:A\to\mathcal{P}\left(A\right) \) כלשהי, ונוכיח כי \( f \) אינה יכולה להיות על. כלומר, אנחנו רוצים לבנות איבר \( D\in\mathcal{P}\left(A\right) \) כך ש-\( f\left(a\right)\ne D \) לכל \( a\in A \). כיצד נעשה זאת? נגדיר את \( D \) בצורה קצת מחוכמת שמתבססת על \( f \): \( D\triangleq\left\{ a\in A\ |\ a\notin f\left(a\right)\right\} \). כלומר, \( D \) כוללת את כל אברי \( A \) שאינם שייכים לקבוצה שמתקבלת מההפעלה של \( f \) עליהם - האיברים שאינם שייכים לתמונה שלהם.

עכשיו, אומר קנטור, בואו נניח בשלילה לרגע שיש \( d\in A \) כך ש-\( f\left(d\right)=D \). מה קורה כעת? יש שתי אפשרויות:

1. אם \( d\in D \) אז על פי הגדרת \( D \), האיבר \( d \) צריך לקיים את קריטריון השייכות ל-\( D \), כלומר לקיים \( d\notin f\left(d\right) \). אבל \( f\left(d\right)=D \), כלומר קיבלנו \( d\notin D \) בסתירה לנקודת המוצא שלנו.
2. אם לעומת זאת \( d\notin D \) אז מכיוון ש-\( D=f\left(d\right) \) קיבלנו ש-\( d\notin f\left(d\right) \). זה אומר ש-\( d \) מקיימת את הקריטריון שמגדיר את \( D \), ולכן \( d\in D \) - שוב, בסתירה לנקודת המוצא שלנו.

מכיוון שבשני המקרים הגענו לסתירה, המסקנה היא שההנחה שלנו שבכלל קיימת \( d\in A \) כך ש-\( f\left(d\right)=D \) אינה נכונה, מה שמסיים את ההוכחה: הראינו ש-\( D \) לא שייכת לתמונה של \( f \) ולכן \( f \) אינה על, ומכיוון ש-\( f \) הייתה פונקציה כלשהי, המסקנה היא שלא קיימת פונקציה חח”ע ועל מ-\( A \) אל \( \mathcal{P}\left(A\right) \).

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

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

בואו נתחיל מ-3. משפט קנטור נותן לנו שיטה לבנות סדרה אינסופית של אינסופים: \( \left|\mathbb{N}\right|<\left|\mathcal{P}\left(\mathbb{N}\right)\right|<\left|\mathcal{P}\left(\mathcal{P}\left(\mathbb{N}\right)\right)\right|<\ldots \). יש בתורת הקבוצות סימון פורמלי לגדלים הללו: \( \left|\mathbb{N}\right|=\beth_{0} \) (כן, זו האות העברית ב’, בפונט מתמטי מוזר) ו-\( \left|\mathcal{P}\left(\mathbb{N}\right)\right|=\beth_{1} \) ו-\( \left|\mathcal{P}\left(\mathcal{P}\left(\mathbb{N}\right)\right)\right|=\beth_{2} \) וכן הלאה: קיבלנו סדרה אינסופית. מכיוון שיש לנו התאמה חח”ע ועל בין \( \mathbb{N} \) ובין קבוצת הבתים הזו, הראינו שיש אינסוף “קטן” של קבוצות אינסופיות. אבל בפועל זו מראית עין מטעה כי יש הרבה יותר קבוצות אינסופיות שעדיין לא דיברתי עליהן ולא ברור לנו איך אפשר “לבנות” בכלל. פורמלית האינסוף של “אוסף כל האינסופים” הולך להיות כל כך גדול שאוסף כל האינסופים הזה לא יוכל להיות קבוצה. אבל על זה אי אפשר לדבר פורמלית כרגע אז נעזוב את זה.

שנית, זה מזכיר בצורה חשודה את הפרדוקס של ראסל כי ככה ראסל גילה את הפרדוקס של ראסל - על ידי זה שהוא קרא את ההוכחה של קנטור וניסה לשחק איתה. אבל בניגוד לפרדוקס של ראסל, ההוכחה של קנטור לא יוצרת פרדוקס במתמטיקה כי הקבוצה \( D\triangleq\left\{ a\in A\ |\ a\notin f\left(a\right)\right\} \) הוגדרה בצורה תקינה פורמלית, על ידי לקיחת קבוצה קיימת \( A \) וגזירת תת-קבוצה שלה באמצעות קריטריון קונקרטי כלשהו.

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

מה זה בעצם לכסון?

ובכן, בואו ננסה להציג טיעון “לכסון” בצורה כללית ונראה איך הוא בא לידי ביטוי בשתי ההוכחות הללו. בטיעון “לכסון” יש לנו שתי קבוצות, \( A\subseteq B \) ואנחנו רוצים להוכיח ש-\( A\ne B \) על ידי בניה של איבר של \( B \) שאינו שייך ל-\( A \).

בהוכחה של האלכסון של קנטור, \( A \) הייתה \( f\left(\mathbb{N}\right) \) - קבוצת כל המספרים שסימנתי בתור \( \left\{ a_{0},a_{1},a_{2},\ldots\right\} \) ו-\( B \) הייתה \( \left(0,1\right) \).

בהוכחה של המשפט \( \left|X\right|<\left|\mathcal{P}\left(X\right)\right| \) (שיניתי לאיקס כדי לא להתנגש עם \( A \)), הקבוצה \( A \) היא הקבוצה \( f\left(X\right) \) - כל התמונות של הפעלת \( f \) על אברי \( X \), ו-\( B \) הייתה \( \mathcal{P}\left(X\right) \).

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

עכשיו, הרעיון הוא שכדי להוכיח ש-\( A\ne B \) אנחנו בונים איבר ספציפי \( b\in B \) בצורה כזו שהוא יהיה שונה מכל אברי \( A \). כדי לעשות את זה אנחנו מנצלים חופש בחירה שיש לנו בבניה של אברי \( B \). אפשר לחשוב על אברי \( B \) כבעלי “תכונות” מסויימות, שאפשר לשלוט עליהן בצורה בלתי תלויה פחות או יותר, וכשאנחנו בונים את \( b \) אז לכל \( a\in A \), אנחנו מהנדסים את אחת מהתכונות של \( b \) כדי שתהיה שונה מאותה התכונה אצל \( a \).

באלכסון של קנטור, \( b \) היה האיבר שכינתי \( d=0.d_{0}d_{1}d_{2}\ldots \) וה”תכונות” הן פשוט הספרות של \( d \). את \( d_{0} \) הינדסתי כדי להיות שונה מ-\( a_{0} \), אז \( d_{1} \) כדי להיות שונה מ-\( a_{1} \) וכן הלאה. שימו לב שלא היה לי חופש בחירה מוחלט של הספרות \( d_{i} \) הללו - נזהרתי לא להשתמש ב-0 או 9 כדי לא להתנגש בתופעה הקטנונית והמצערת של \( 0.999\ldots=1 \).

במשפט על קבוצת החזקה, \( b \) היה הקבוצה \( D \) שבניתי וה”תכונות” היו האיברים של \( D \). לכל \( x\in X \), ה”תכונה” הייתה השאלה האם \( x\in D \) או \( x\notin D \), ואת זה באמת שיכלתי לבחור באופן בלתי תלוי לכל \( x \).

עכשיו, נקודה שכדאי לשים אליה לב היא שבשתי ההוכחות, הייתה לי דרך כלשהי לאנדקס את האיברים של \( A \), והתבססתי על שיטת האינדקס הזו כשבניתי את \( b \). באלכסון של קנטור, \( A=\left\{ a_{0},a_{1},a_{2},\ldots\right\} \) והאינדקסים של האיברים הם פשוט מספרים טבעיים. נעזרתי את זה כשבניתי את \( d=0.d_{0}d_{1}d_{2}\ldots \): השתמשתי באותה קבוצת אינדקסים כדי לאנדקס את הספרות של \( d \). שימו לב שזה לא מובן מאליו: יצרנו כאן קשר בין האינדקסים של אברים של \( A \) ובין האינדקסים של הספרות שמרכיבות את \( d \).

בהוכחה של המשפט עם קבוצת החזקה, ה”אינדקסים” היו האיברים של \( X \). כזכור, הגדרתי את \( A \) בתור \( f\left(X\right) \), כלומר כל איבר של \( A \) היה קבוצה מהצורה \( f\left(x\right) \) עבור \( x\in X \), ואני ניצלתי את האינדקס הזה כדי לבנות קבוצה \( D \) כך ש-\( x\in D\iff x\notin f\left(x\right) \), כך ש-\( D \) (הקבוצה שאני בונה) ו-\( f\left(x\right) \) (הקבוצה שמאונדקסת על ידי \( x \)) נבדלו ביניהן בתכונה “\( x \) שייך אלי”.

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

עוד דוגמאות ללכסונים

אני רוצה לתת עוד דוגמא או שתיים לאופן שבו משתמשים בכלי של לכסון כדי להוכיח שקבוצה כלשהי היא גדולה יותר מהמספרים הטבעיים. לשם כך אני אסתכל על קבוצת הסדרות של טבעיים: קבוצת הפונקציות \( f:\mathbb{N}\to\mathbb{N} \), ואקח ממנה תת-קבוצות מסוימות.

בדוגמא הראשונה שלי, \( B \) היא קבוצת הסדרות של טבעיים שבה במקומות האי-זוגיים יש תמיד 42. למה? ככה. כדי להקשות. פורמלית, \( B=\left\{ f\in\mathbb{N}^{\mathbb{N}}\ |\ \forall n\in\mathbb{N}:f\left(2n+1\right)=42\right\} \). טיעון לכסון שמטרתו להוכיח ש-\( \left|\mathbb{N}\right|\ne\left|B\right| \) מתחיל כך: ניקח פונקציה כלשהי \( g:\mathbb{N}\to B \) ונוכיח שאינה חח”ע. נסמן \( A=g\left(\mathbb{N}\right)=\left\{ f_{0},f_{1},f_{2},\ldots\right\} \) - הנה יש לנו “אינדוקס” של אברי \( A \) כמו קודם. עכשיו אני אבנה פונקציה חדשה, \( h\in B \), בצורה שמבטיחה ש-\( h\ne f_{n} \) לכל \( n\in\mathbb{N} \).

הדבר ה”טבעי” היה אולי להגדיר כך: \( h\left(n\right)=\begin{cases} 4 & f_{n}\left(n\right)\ne4\\ 3 & f_{n}\left(n\right)=4 \end{cases} \). זה מאוד מתאים לאלכסון של קנטור שראינו קודם. זה גם מאוד שגוי כי אין לנו חופש בחירה כזה כשאנחנו בונים את \( h \). כזכור, היעד שלנו הוא שיתקיים \( h\in B \) וכדי שזה יקרה, על ערכים אי זוגיים אני חייב להגדיר את \( h \) להחזיר 42.

אם כך, לכאורה אני בצרות! איך אני אוכל להבטיח ש-\( h \) שונה מ-\( f_{1} \) אם אני לא יכול להגדיר אותה על \( 1 \) איך שבא לי?! אם \( h\left(1\right)=f_{1}\left(1\right)=42 \), כל טיעון האלכסון של קנטור נהרס! הו לא!

כמובן שבפועל זה מכשול זניח שקל מאוד לעקוף. אני עדיין אשתמש באינדקס של \( f_{n} \); אני פשוט אכפול אותו ב-2:

\( h\left(n\right)=\begin{cases} 42 & n=2k+1\\ 4 & n=2k\wedge f_{k}\left(n\right)\ne4\\ 3 & n=2k\wedge f_{k}\left(n\right)\ne4 \end{cases} \)

מה עשיתי פה? כש-\( h \) מקבלת קלט, קודם כל היא בודקת אם הוא זוגי או לא. אם הוא אי זוגי, אין לה ברירה - היא מחזירה 42. אם הוא זוגי, היא מחלקת אותו ב-2 והתוצאה שהיא מקבלת היא האינדקס של ה-\( f \) שהיא “תתקוף” באמצעות הקלט \( n \). שימו לב שאני מגדיר את \( h\left(n\right) \) כך ש-\( h\left(n\right)\ne f_{k}\left(n\right) \) - כלומר, ש-\( h \) ו-\( f_{k} \) יבדלו זו מזו במקום ה-\( n \)-י. אם הייתי מגדיר \( h\left(n\right)\ne f_{k}\left(k\right) \) אז מה שיש בצד ימין היה מזכיר יותר את האלכסון ה”קלאסי” של קנטור, אבל הוא גם לא היה אומר שום דבר - אם \( n\ne k \) אין שום דבר מעניין שאפשר להסיק \( h\left(n\right)\ne f_{k}\left(k\right) \); אי אפשר להסיק מזה \( h\ne f_{k} \).

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

נעבור לדוגמא השניה שלי. בדוגמא הזו, \( B \) תהיה קבוצת הסדרות של טבעיים שהן מונוטוניות עולות. סדרה \( f \) היא מונוטונית עולה אם לכל \( n<m \) מתקיים \( f\left(n\right)<f\left(m\right) \) - או במילים אחרות, לכל שני איברים סמוכים בסדרה, הראשון קטן מהשני. כמקודם, הטיעון האלכסוני מגיע לכך שיש לי קבוצה \( \left\{ f_{0},f_{1},\ldots\right\} \) של סדרות כאלו ואני רוצה לבנות אחת חדשה \( h \) ששונה מהן.

הפעם הבניה \( h\left(n\right)=\begin{cases} 4 & f_{n}\left(n\right)\ne4\\ 3 & f_{n}\left(n\right)=4 \end{cases} \) לא תעבור כי \( h \) לא תהיה מונוטונית. מה שטוב בדרישת המונוטוניות הזו הוא בכך שהיא קצת מקלקלת לי את האי-תלות בין ערכים שונים של \( h \). אם נעיף מבט בתיאור הכללי של של שיטת הלכסון נראה שכתבתי ניסוח מאוד מעורפל: “אפשר לחשוב על אברי \( B \) כבעלי “תכונות” מסויימות, שאפשר לשלוט עליהן בצורה בלתי תלויה פחות או יותר”. עכשיו אנחנו ב”פחות” הזה. אבל אין סיבה שזה יעצור אותנו - כל מה שאנחנו צריכים הוא שכל איבר יהיה גדול יותר מהקודם וגם מהאיבר המקביל אצל \( f \). אז אני אשתמש בסימון \( h\left(-1\right)=0 \), וכעת אגדיר \( h\left(n\right)=h\left(n-1\right)+f_{n}\left(n\right)+1 \). כאן אפילו לא צריך חלוקה למקרים.

מה קורה פה? ראשית, בגלל שאנחנו מוסיפים 1, אז \( h\left(n\right)>f_{n}\left(n\right) \) ולכן \( h\ne f_{n} \). שנית, בגלל אותה תוספת 1, אנחנו מקבלים \( h\left(n\right)>h\left(n-1\right) \) ולכן הסדרה מונוטונית עולה. זה מסיים את ההוכחה. למעשה, זה טיעון כל כך פשוט שלא ברור למה באלכסון המקורי של קנטור לא הגדרתי \( d_{n}=a_{n}^{n}+1 \), אבל התשובה פשוטה: שם ה-\( d \)-ים היו ספרות בייצוג עשרוני, כלומר היו מוגבלים להיות בין 0 ל-9. כאן אין לי הגבלה כזו.

ועכשיו למשהו לא קשור בעליל - פונקציות שאינן ניתנות לחישוב

אני לא יכול לסיים פוסט על לכסון בלי לגלוש לתחום שאהוב עלי במיוחד ולכסונים מככבים גם בו - תורת החישוביות. מכיוון ששולי הפוסט הזה צרים מלהכיל מבוא מלא לחישוביות, הנה התקציר: במרכז מה שעושים בחישוביות נמצא מודל חישובי כלשהו. לעתים קרובות מדברים על משהו שנקרא מכונת טיורינג אבל אני לא צריך את זה פה ואדבר על תוכניות מחשב בשפה קונקרטית כלשהי - נאמר, פייתון. לא צריך להכיר את פייתון בשביל המשך הטיעון - רק לדעת שכל תוכנית מחשב כזו אפשר לקודד באמצעות מספר טבעי (זה האופן שבו קבצי טקסט נשמרים בזכרון של המחשב, פחות או יותר). הקידוד הזה הוא חד-חד-ערכי ועל ולכן אפשר לסמן את קבוצת כל תוכניות הפייתון ב-\( \left\{ M_{0},M_{1},M_{2},\ldots\right\} \).

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

נניח ש-\( L \) היא קבוצה של מספרים טבעיים ו-\( M \) היא תוכנית מחשב כלשהי. אני אומר ש-\( M \) מכריעה את \( L \) אם:

• לכל \( a\in L \), התוכנית \( M \) עוצרת על הקלט \( a \) עם התשובה "כן"
• לכל \( a\notin L \) התוכנית \( M \) עוצרת על הקלט \( a \) עם התשובה "לא"

ועכשיו בואו נסבך: אני אומר ש-\( M \) מקבלת את \( A \) אם:

• לכל \( a\in L \), התוכנית \( M \) עוצרת על הקלט \( a \) עם התשובה "כן"
• לכל \( a\notin L \) התוכנית \( M \) עוצרת על הקלט \( a \) עם התשובה "לא" או שאינה עוצרת בכלל

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

הנה איך שמבנה הלכסון שהצגתי קודם עובד כאן: \( B \) שלי תהיה קבוצת כל קבוצות הטבעיים \( L \) שאפשר לקבל ואילו \( A\subseteq B \) תהיה קבוצת כל קבוצות הטבעיים \( L \) שאפשר להכריע. יש לי דרך פשוטה לאנדקס את אברי \( A \): אם אפשר להכריע את \( L \) אז קיימת תוכנית \( M \) שמכריעה את \( L \). כבר ראינו קודם שאפשר למספר את כל התוכניות, כך שגם ל-\( M \) הזו יש מספר סידורי כלשהו, \( n \), כלומר אני מסמן אותה ב-\( M_{n} \). עכשיו אני אבנה קבוצה \( D \) של טבעיים באופן הבא: \( D \) תכיל את ה-\( n \)-ים ש-\( M_{n} \) אומרת עליהם “לא”.

הנה איך נובע מההגדרה הזו שלא קיימת מכונה \( M \) שמכריעה את \( D \): נסתכל על המכונה \( M_{n} \), עבור \( n \) כלשהו. מה המכונה \( M_{n} \) עושה על הקלט \( n \)? ייתכן ש-\( M_{n} \) בכלל לא עוצרת על הקלט הזה, אבל אז \( M_{n} \) היא לא מכונה שמכריעה קבוצות; מכונה שמכריעה קבוצות חייבת לעצור על כל קלט. מכיוון שכל מה שאנחנו רוצים לעשות הוא להראות ש-\( D \) לא מוכרעת על ידי \( M_{n} \), סיימנו במקרה הזה. נשארנו עם המקרה שבו \( M_{n} \) כן עוצרת על \( n \). במקרה הזה, אם \( M_{n} \) אומרת “לא” אז \( n\in D \) על פי הגדרת \( D \). אם לעומת זאת \( M_{n} \) אומרת “כן” אז \( n\notin D \) על פי הגדרת \( D \). בכל אחד משני המקרים הללו, \( M_{n} \) עונה את התשובה הלא נכונה מבחינת \( D \), ולכן הקבוצה ש-\( M_{n} \) מכריעה איננה \( D \).

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

איך נפנוף הידיים שלי בא לידי ביטוי? ראשית, בהנחה שאפשר לשחזר את \( M_{n} \) מתוך \( n \) - כדי להסביר את זה צריך להיכנס לפרטים של איך בדיוק מקודדים תוכניות מחשב - לא אעשה את זה כאן, וממילא זה מה שעורכי טקסט עושים כשהם טוענים תוכניות מחשב מקבצים. שנית, בהנחה שתוכנית מחשב שלי יודעת להריץ תוכנית מחשב אחרת, שנתונה לה כקלט - גם את זה קל לעשות במחשבים מודרניים. מתי הדברים הללו לא היו מובנים מאליהם? בשנת 1936, כשאלן טיורינג פרסם את המאמר שלו ``On computable numbers, with an application to the Entscheidungsproblem’’ שבו הוא:

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

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

בזאת סיימנו את מה שיש לי להגיד כרגע על לכסונים - בפוסט הבא של תורת הקבוצות נחזור לדבר על דברים קונקרטיים יותר, כמו המספרים הרציונליים: מה בעצם קורה איתם? מה הגודל האינסופי שלהם? הרי יש קטע כזה שבין כל שני מספרים ממשיים יש מספר רציונלי, אז בוודאי צריך להתקיים \( \left|\mathbb{Q}\right|=\left|\mathbb{R}\right| \). נכון? נכון? נכון? לא נכון…?