תורת הקבוצות - קבוצות בנות מניה

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

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

למה זה מוזר? ובכן, מספרים רציונליים יש המון. בין זוג המספרים הטבעיים 0 ו-1 יש אינסוף מספרים רציונליים מסוגים שונים ומשונים. כל המספרים מהצורה \( \frac{1}{n} \) נמצאים שם - הרי לכם כבר “אותו מספר” של מספרים טבעיים, וזה רק בין 0 ו-1, וזה לא כל מה שנמצא שם כי גם מספרים מהצורה \( \frac{2}{n} \) עבור \( n>2 \) נמצאים שם, ועוד ועוד וכך עד אינסוף - בעצם בין 0 ו-1 יש “אינסוף עותקים” של דברים שהם מאותו גודל כמו המספרים הטבעיים. אבל זו אפילו לא הסיבה העיקרית שזה מוזר, אלא הדמיון של המספרים הרציונליים לממשיים. אחד מהמשפטים הראשונים שלומדים בחשבון דיפרנציאלי ואינטגרלי הוא שבין כל שני מספרים ממשיים \( r\ne s \) קיים מספר רציונלי \( r<q<s \). שזה אומר, במילים אחרות, שלא משנה כמה נעשה zoom in על ציר המספרים, תמיד נמצא שם איזה רציונלי (להבדיל מהטבעיים, שנעלמים לגמרי אם עושים זום מספיק גדול). אם הרציונליים נמצאים ככה בכל מקום, איך יכול להיות שיש הבדל מהותי שכזה בינם ובין הממשיים? אני מקווה שעד סוף הפוסט האינטואיציה שלנו תתמודד עם זה טוב יותר.

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

סימון אחר שמשתמשים בו לתיאור קבוצה אינסופית בת מניה הוא \( \left|A\right|=\aleph_{0} \) - כן, זו האות העברית אל”ף שבה קנטור בחר להשתמש. כרגע זה נראה כמו סימון ותו לא - אין לנו הגדרה פורמלית למה זה ה-\( \aleph_{0} \) הזה, אבל קיימת הגדרה כזו ונראה אותה בהמשך, אחרי שנכיר את המושג של סודרים.

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

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

1. בסדרה \( b_{0},b_{1},b_{2},\ldots \) בהחלט יכולים להופיע גם איברים שלא שייכים ל-\( A \).
2. בסדרה \( b_{0},b_{1},b_{2},\ldots \) בהחלט אותו איבר של \( A \) יכול להופיע יותר מפעם אחת.

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

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

• \( 1,2,3,\ldots \)
• \( 1,4,9,16,\ldots \)

הסדרות הללו “מוכיחות” (קצת בנפנוף ידיים) שהקבוצות הן בנות מניה. ועכשיו אפשר לעשות משהו דומה מאוד עבור המספרים השלמים \( \mathbb{Z} \):

• \( 0,1,-1,2,-2,3,-3,\ldots \)

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

עכשיו נעבור אל הרציונליים. ראשית אני אטפל רק ברציונליים האי שליליים כי אחר כך להוסיף את השליליים זה בדיוק אותו טריק כמו עבור \( \mathbb{Z} \) שזה עתה הראיתי. הרעיון שלי הוא פשוט: מספר רציונלי הוא מהצורה \( \frac{a}{b} \), אז אפשר לסדר את הרציונליים בסדרה כך שקודם כל באים כל הרציונליים שעבורם \( a+b=0 \), אחר כך אלו שעבורם \( a+b=1 \) וכן הלאה. ככה זה נראה:

\( \frac{0}{0},\frac{0}{1},\frac{1}{0},\frac{0}{2},\frac{1}{1},\frac{2}{0},\ldots \)

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

בואו נרחיב עוד טיפה את הסדרה כדי שהעיקרון בה יהיה ברור:

\( \frac{0}{0},\frac{0}{1},\frac{1}{0},\frac{0}{2},\frac{1}{1},\frac{2}{0},\frac{0}{3},\frac{1}{2},\frac{2}{1},\frac{3}{0},\ldots \)

כדי לחדד, אני אשים סוגריים סביב כל המספרים שסכום המונה והמכנה שלהם הוא 0, עבור אלו שאצלם זה 1 וכן הלאה:

\( \underset{0}{\left[\frac{0}{0}\right]},\underset{1}{\left[\frac{0}{1},\frac{1}{0}\right]},\underset{2}{\left[\frac{0}{2},\frac{1}{1},\frac{2}{0}\right]},\underset{3}{\left[\frac{0}{3},\frac{1}{2},\frac{2}{1},\frac{3}{0}\right]},\ldots \)

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

בהערת אגב, זה מאוד דומה לקסם שמאפשר לנו לכפול טורי חזקות: בכפל \( \left(\sum_{n=0}^{\infty}a_{n}x^{n}\right)\cdot\left(\sum_{m=0}^{\infty}b_{m}x^{m}\right) \) מקבלים בתור תוצאה את \( \sum_{k=0}^{\infty}c_{k}x^{k} \) כך ש-\( c_{k}=\sum_{i+j=k}a_{i}b_{j} \) - גם כאן מתבססים על כך שכל מקדם \( c_{k} \) שכזה מתקבל כסכום של מספר סופי של איברים, ואם היינו מנסים לכפול שני טורי חזקות שבהם יש גם חזקות שלילות עד אינסוף, זה כבר לא היה עובד כי המקדמים היו יוצאים סכום אינסופי.

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

בדוגמא הזו ממש מתווים “מסלול” על הטבלה הדו-ממדית של הרציונליים ואפשר לראות את הרעיון - עוברים סדרתית על האלכסונים בטבלה הזו (בכל אלכסון שכזה יש את המספרים \( \frac{a}{b} \) כך ש-\( a+b \) הוא \( n \) מסויים). בדוגמא הזו טרחו להיזהר - לא הכניסו את 0 למשחק כדי לא לחטוף לפרצוף את \( \frac{0}{0} \) וחברים, וסימנו באדום מספרים רציונליים שכבר נספרו קודם. אבל אני בכוונה נקטתי בגישה ה”עצלנית” כי חשוב לי להבהיר שכשרוצים להראות שקבוצה היא בת מניה, לא חייבים להיות מדוייקים-מדוקדקים כל כך. לרוב זה סתם מקשה עלינו.

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

\( \frac{0}{0},-\frac{0}{0},\frac{0}{1},-\frac{0}{1},\frac{1}{0},-\frac{1}{0},\frac{0}{2},-\frac{0}{2},\frac{1}{1},-\frac{1}{1},\frac{2}{0},-\frac{2}{0},\ldots \)

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

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

\( \pi=3.14159\ldots \)

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

מה קורה לעומת זאת במספרים רציונליים? הכל טוב ויפה! למשל, \( \frac{1}{2}=0.5 \) כולל רק מספר סופי של ספרות, ולכן קל לייצג אותו עם כמות סופית של מידע. ויש את \( \frac{1}{4}=0.25 \) שגם כן דורש מספר סופי של ספרות אבל יותר ספרות מאשר \( \frac{1}{2} \); מכאן מגיעה ה”כמות לא חסומה”. יש מספרים רציונליים שכדי לייצג אותם נצטרך 100 ספרות, או 1,000, או \( 10^{100} \); אבל אף פעם לא נצטרך אינסוף ספרות.

“רגע רגע רגע” אתן אומרות עכשיו - “מה אתה מקשקש בכלל? הרי אפשר לייצג את פאי בדרכים סופיות למהדרין וחוץ מזה יש מספרים רציונליים בני אינסוף ספרות” ואתן כמובן צודקות. הטיעון שלי לא יכול להיות עד כדי כך פשטני. נתחיל מרציונליים בני אינסוף ספרות, למשל \( \frac{1}{3}=0.333\ldots \). מצד אחד, זה מספר שמשתמש באינסוף ספרות בייצוג שלו (ובעצם, גם \( \frac{1}{2}=0.5000\ldots \) משתמש באינסוף כאלו) אבל אנחנו לא צריכים אינסוף ספרות כדי לייצג אותו כי הוא מחזורי. ב-\( 0.333\ldots \) כל מה שיש לנו הוא את הספרה 3 שחוזרת על עצמה שוב ושוב. אפשר לכתוב את זה בצורה מקוצרת: \( \frac{1}{3}=0.\overline{3} \), כשהקו מעל ה-3 אומר “ומכאן והלאה חוזרים על התבנית הזו”. זה תקף גם למספרים רציונליים עם ייצוג עשרוני מסובך יותר, למשל \( \frac{1}{7}=0.\overline{142857} \). דיברתי על זה בפירוט גדול יותר כאן.

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

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

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

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

ראשית, בואו נכתוב במפורש את אברי הקבוצות. הן כולן בנות מניה, אז אפשר למספר את האיברים שלהן:

\( A_{0}=\left\{ a_{0}^{0},a_{1}^{0},a_{2}^{0},\ldots\right\} \)

\( A_{1}=\left\{ a_{0}^{1},a_{1}^{1},a_{2}^{1},\ldots\right\} \)

וכן הלאה. כלומר, \( a_{n}^{k} \) הוא סימן של המספר ה-\( n \)-י ששייך לקבוצה \( A_{k} \). עכשיו, הנה סדרה שכוללת את כל אברי \( \bigcup_{n=0}^{\infty}A_{n} \):

\( a_{0}^{0},a_{1}^{0},a_{0}^{1},a_{2}^{0},a_{1}^{1},a_{0}^{2},\ldots \)

רואים את העיקרון? כמקודם, אפשר לקבץ את האיברים בסדרה לקבוצות: קודם כל האיברים מהצורה \( a_{n}^{k} \) שעבורם \( n+k=0 \) (זה רק \( a_{0}^{0} \)), אחר כך אלו שעבורם \( n+k=1 \) (\( a_{1}^{0} \) ו-\( a_{0}^{1} \)) וכן הלאה. כמקודם, ייתכן שאיבר יופיע יותר מפעם אחת בסדרה הזו, אבל זה לא מפריע לי, וזה מסיים את ההוכחה.

אבל רגע, רגע, רגע, לא שכחתי משהו? מה עם הוכחה של טיעון הסדרה הזה עצמו? נזכיר מה הוא אומר: אם \( A \) היא קבוצה וקיימת סדרה \( b_{0},b_{1},\ldots \) כך שכל איבר של \( A \) מופיע בסדרה הזו, אז \( A \) בת מניה. איך נוכיח את זה? באופן הבא: ראשית נגדיר פונקציה \( f:A\to\mathbb{N} \) על ידי כך ש-\( f\left(a\right) \) יהיה שווה לאינדקס של המקום הראשון בסדרה שבו \( a \) מופיע. למשל, אם \( a=3 \) והסדרה היא \( 0,5,1,7,3,6,1,3,1,6,\ldots \) אז \( f\left(a\right)=4 \). בבירור \( f \) הזו מוגדרת לעל \( a\in A \) כי כל \( a \) כזה מופיע לפחות פעם אחת בסדרה ולכן אפשר לקחת את מספר המקום הראשון שלו; כמו כן, \( f \) היא חד–חד-ערכית כי אם \( f\left(a_{1}\right)=f\left(a_{2}\right) \) זה אומר ש-\( a_{1},a_{2} \) מופיעים יחד בסדרה באותו מקום ולכן הם כמובן שווים. זה מוכיח ש-\( \left|A\right|\le\left|\mathbb{N}\right| \).

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

עכשיו, משיש לי את טיעון ה”איחוד בן מניה של קבוצות בנות מניה הוא בן מניה”, אני יכול להוכיח דברים קצת יותר מרחיקי לכת מסתם “רציונליים”. ראשית, בואו נדבר על מכפלות קרטזיות. נניח ש-\( A,B \) שתיהן קבוצות בנות מניה, אז גם \( A\times B\triangleq\left\{ \left(a,b\right)\ |\ a\in A\wedge b\in B\right\} \) היא קבוצה בת מניה. דרך פשוטה לראות זאת היא כך: \( A\times B=\bigcup_{a\in A}\left(\left\{ a\right\} \times B\right) \). כלומר, אנחנו לוקחים את \( A\times B \) ופורסים אותה ל”פרוסות” מהצורה \( \left\{ \left(a,b\right)\ |\ b\in B\right\} \). כל פרוסה כזו היא קבוצה בת מניה היא \( f\left(b\right)=\left(a,b\right) \) היא פונקציה חח”ע ועל מ-\( B \) (הבת מניה) אל ה”פרוסה”, ולכן \( \bigcup_{a\in A}\left(\left\{ a\right\} \times B\right) \), שהוא איחוד בן מניה (כי \( A \) בת מניה) מגדיר קבוצה בת מניה.

אפשר להשתמש בטיעון דומה כדי להוכיח ש-\( A\times B\times C \) היא בת מניה אם \( A,B,C \) בנות מניה: נסתכל על ה”פרוסות” \( A\times B\times C=\bigcup_{a\in A}\left\{ a\right\} \times\left(B\times C\right) \) ונשתמש בכך שכבר ידוע ש-\( B\times C \) בת מניה. בצורה הזו אפשר להוכיח שכל מכפלה קרטזית של מספר סופי של קבוצות בנות מניה היא בת מניה. הטיעון האינדוקטיבי לא יכול לעבוד על מספר אינסופי של קבוצות בנות מניה שמוכפלות יחד - למרבה השמחה, כי עבור מקרה כזה, זה פשוט לא נכון שמכפלה כזו היא עדיין בת מניה. למשל, \( \prod_{n\in\mathbb{N}}\left\{ 0,1\right\} \) היא בעצם הקבוצה \( \left\{ 0,1\right\} ^{\mathbb{N}} \) בתחפושת, והקבוצה הזו היא בסך הכל \( \mathcal{P}\left(\mathbb{N}\right) \) בתחפושת, ומשפט קנטור מראה שהיא אינה בת מניה.

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

\( f\left(a,b\right)\triangleq\frac{\left(a+b\right)\left(a+b+1\right)}{2}+b \)

אני לא אוכיח כרגע לא שהפונקציה הזו באמת חח”ע ועל, ולא שהיא הפונקציה הפשוטה (במובן מסויים של “פשוטה”) היחידה שנותנת התאמה חח”ע ועל שכזו, ולא אציג את ההכללות שלה ל-\( \mathbb{N}^{k}\to\mathbb{N} \) - בפוסט הזה אני דווקא מעדיף את הגישה העצלנית.

עכשיו בואו נדבר על מספרים אלגבריים. מספר אלגברי הוא מספר \( a\in\mathbb{R} \) כך שקיים פולינום \( p\left(x\right) \) לא קבוע שכל המקדמים שלו הם מספרים רציונליים ו-\( p\left(a\right)=0 \). הדוגמא הקלאסית היא \( \sqrt{2} \) - מספר שאיננו רציונלי, אבל הוא אלגברי כי הוא שורש של הפולינום \( x^{2}-2 \).

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

ובכן, אני הולך להוכיח שהמספרים האלגבריים הם קבוצה בת מניה, מה שיראה ש”רוב” המספרים הממשיים אינם רציונליים כי הממשיים אינם בני מניה. למרבה השמחה, קל להוכיח את זה בלי לדעת כמעט כלום על מספרים אלגבריים. ראשית, מה זה פולינום רציונלי, בכלל? זה ביטוי מהצורה \( \sum_{i=0}^{n}a_{i}x^{i} \) כאשר \( n\in\mathbb{N} \) טבעי כלשהו ו-\( a_{i}\in\mathbb{Q} \) נקרא המקדם של החזקה \( x^{i} \) בפולינום (אצלנו המקדם הוא מספר רציונלי אבל באופן כללי מקדמים יכול להגיע ממקומות שונים ומשונים). הקונבנציה היא שאם כותבים פולינום בתור \( \sum_{i=0}^{n}a_{i}x^{i} \) אז המקדם של החזקה הגבוהה ביותר, \( a_{n} \), הוא שונה מאפס - על זה אומר שהפולינום הוא ממעלה \( n \). אם כן, אפשר להתחיל לפרוס את העולם של המספרים האלגבריים לפרוסות: יש את אלו שהם שורש של פולינום ממעלה 1, ואלו שהם שורש של פולינום מעלה 2, ואלו שהם שורש של פולינום ממעלה 3… מספיק אם נוכיח שעבור \( n \) שרירותי, המספרים האלגבריים שהם שורש של פולינום ממעלה \( n \) הם קבוצה בת מניה, ואז טיעון ה”איחוד בן מניה של קבוצות בנות מניה” יעבוד על כלל המספרים האלגבריים.

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

איך להוכיח שיש מספר בן מניה של פולינומים ממעלה \( n \)? זה קל: נגדיר פונקציה \( f\left(\sum_{i=0}^{n}a_{i}x^{i}\right)=\left(a_{0},a_{1},\ldots,a_{n}\right) \) שלוקחת פולינום ומחזירה את סדרת המקדמים שלו. הסדרה הזו היא בבירור איבר של \( \mathbb{Q}^{n+1}=\underset{n+1}{\underbrace{\mathbb{Q}\times\mathbb{Q}\times\ldots\times\mathbb{Q}}} \) - וכבר ראינו קודם שמכפלה קרטזית של מספר סופי של קבוצות בנות מניה היא בת מניה! עכשיו, שימו לב לכך ש-\( f \) היא רק חח”ע ולא על, כי האיבר הימני ביותר ב-\( \left(a_{0},a_{1},\ldots,a_{n}\right) \) הוא שונה מאפס; אבל מכיוון ש-\( \mathbb{Q}^{n+1} \) בת מניה, מספיק להראות פונקציה חח”ע אליה כדי להוכיח שהקבוצה שממנה התחלנו בת מניה. זה מסיים את ההוכחה.

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

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

פורמלית, במדעי המחשב אוהבים לדבר על קבוצה \( \Sigma \) שנקראת אלפבית ולסמן ב-\( \Sigma^{*} \) את אוסף כל הסדרות הסופיות עם איברים מתוך \( \Sigma \). והטענה המאוד פשוטה שלי היא שכאשר \( \Sigma \) סופית, אז \( \left|\Sigma^{*}\right|=\aleph_{0} \). למה זו טענה פשוטה? כי \( \Sigma^{*}=\bigcup_{n=0}^{\infty}\Sigma^{n} \) כאשר \( \Sigma^{n} \) הוא אוסף כל הסדרות בנות \( n \) איברים עם איברים מתוך \( \Sigma \), ולכן אפשר לחשב במפורש: \( \left|\Sigma^{n}\right|=\left|\Sigma\right|^{n} \) - זה תרגיל פשוט בקומבינטוריקה (יש \( \left|\Sigma\right| \) אפשרויות לבחירת התו הראשון בסדרה, \( \left|\Sigma\right| \) לבחירת התו השני וכן הלאה; ועכשיו נפעיל את עיקרון הכפל). אם כן, \( \Sigma^{*} \) היא איחוד בן מניה של קבוצות סופיות - ולכן בת מניה. נגמרה ההוכחה, ומכאן נובע מיידית שאת רוב המספרים הממשיים אי אפשר לחשב.

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