תורת הקבוצות - עוצמות

מבוא

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

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

מה זו עוצמה, פורמלית?

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

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

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

אם כן, מונה הוא סוג מסויים של סודר: כזה שאינו שקול עוצמה לאף סודר שבא לפניו. פורמלית, סודר \( \alpha\in\text{Ord} \) הוא מונה אם לכל \( \beta<\alpha \) לא קיימת פונקציה חח”ע ועל \( f:\beta\to\alpha \). עכשיו אפשר להגדיר עוצמה של קבוצה כך: בהינתן קבוצה \( A \) כלשהי, \( \left|A\right| \) יהיה הסודר המינימלי במחלקת הסודרים שיש פונקציה חח”ע ועל מ-\( A \) אליהם:

\( \left|A\right|=\min\left\{ \alpha\in\text{Ord}\ |\ A\sim\alpha\right\} \)

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

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

כשאנחנו מדברים על \( \omega \) בתור מונה ולא בתור סודר, אנחנו משתמשים בסימון אחר עבורו: \( \aleph_{0} \). למה בכלל לעשות הפרדה כזו? כי, למשל, עוד מעט נראה שיש עבור מונים כללי חיבור, כפל וחזקה, והכללים הללו שונים מהכללים עבור סודרים (למשל, חיבור וכפל הם כן קומוטטיביים) ולכן ההקשר פה הוא קריטי. גם הסימונים שבהם אשתמש כדי לתאר מונים “כלליים” יהיו שונים: \( \kappa,\lambda,\theta \) וכאלו, להבדיל מה-\( \alpha,\beta,\gamma \) ששימשו אותנו בהקשר של סודרים.

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

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

\( \aleph_{0}<\aleph_{1}<\aleph_{2}<\ldots \)

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

\( \aleph_{\omega}=\sup\left\{ \aleph_{0},\aleph_{1},\aleph_{2},\ldots\right\} \)

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

כדי להוכיח, נסמן \( \alpha=\sup A \). אני יודע ש-\( \alpha \) הוא סודר, אבל אני צריך גם להראות שלכל סודר אחר \( \beta<\alpha \) לא קיימת פונקציה חח”ע ועל בין \( \alpha \) ו-\( \beta \); מספיק להראות שאם קיימת \( f:\alpha\to\beta \) שהיא חח”ע אז מגיעים לסתירה. עכשיו, מכיוון ש-\( \alpha=\text{sup}A \) הוא הסודר הקטן ביותר שגדול או שווה לכל אברי \( A \), מה שאומר בפרט ש-\( \beta \) אינו כזה, ולכן קיים \( \kappa\in A \) כך ש-\( \beta<\kappa\le\alpha \). מצד שני, מכיוון ש-\( \kappa \) הוא מונה אז \( \kappa=\left|\kappa\right| \), ומכיוון ש-\( \kappa<\alpha \) ו-\( \alpha \) סודר אז \( \kappa\subseteq\alpha \) ולכן אפשר לצמצם את \( f \) אל \( \kappa \) ולקבל פונקציה חח”ע \( f|_{\kappa}:\kappa\to\beta \). קיבלנו \( \left|\kappa\right|=\left|f|_{\kappa}\left(\kappa\right)\right| \), ומכיוון ש-\( f|_{\kappa}\left(\kappa\right)\subseteq\beta \) אז \( \left|f|_{\kappa}\left(\kappa\right)\right|\le\left|\beta\right| \), אז בסך הכל קיבלנו את השרשרת

\( \kappa=\left|\kappa\right|=\left|f|_{\kappa}\left(\kappa\right)\right|\le\left|\beta\right| \)

ומכך ש-\( \kappa\le\left|\beta\right| \) אנחנו מקבלים בפרט \( \kappa\le\beta \) (כי \( \kappa \) קטן או שווה לסודר הראשון ששווה עוצמה ל-\( \beta \)), בסתירה להנחה ש-\( \beta<\kappa \). זה מסיים את ההוכחה.

מה שטוב בהוכחה הזו הוא שהיא לא סתם מראה לנו ש-\( \aleph_{\omega} \) היא מונה; היא מאפשרת לנו להראות שלכל סודר \( \alpha \) קיים מונה \( \aleph_{\alpha} \) ששונה מקודמיו. ההגדרה של האלפים היא ברקורסיה על-סופית:

• \( \aleph_{0}=\omega \)
• \( \aleph_{\alpha+1}=\aleph_{\alpha}^{+} \) לכל סודר \( \alpha \) כאשר \( \aleph_{\alpha}^{+} \) מסמן את המונה הקטן ביותר שגדול מ-\( \aleph_{\alpha} \).
• \( \aleph_{\alpha}=\text{sup}\left\{ \aleph_{\beta}\ |\ \beta<\alpha\right\} \) כאשר \( \alpha \) הוא סודר גבולי.

האם כל המונים האינסופיים הם מהצורה \( \aleph_{\alpha} \) עבור סודר \( \alpha \) כלשהו? כן! בהינתן מונה \( \kappa \) כלשהו, אפשר להסתכל על אוסף כל המונים שקטנים ממנו. האוסף הזה הוא תת-קבוצה של \( \kappa \) עצמו (כי \( \kappa \) הוא בפרט סודר ולכן כולל את כל הסודרים הקטנים ממנו) ולכן האוסף הזה הוא בעצמו קבוצה, ולא סתם קבוצה - קבוצה של סודרים, ולכן קבוצה שסדורה בסדר טוב, ולכן איזומורפית לסודר \( \alpha \) כלשהו, וקיבלנו את ה-\( \aleph_{\alpha} \) שאנחנו מחפשים, כי \( \left\{ \aleph_{\beta}\ |\ \beta<\alpha\right\} \) זה בדיוק אוסף המונים שקטן מ-\( \kappa \).

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

אריתמטיקה של עוצמות

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

• \( \left|A\right|+\left|B\right|=\left|A\cup B\right| \) (בהינתן \( A\cap B=\emptyset \))
• \( \left|A\right|\cdot\left|B\right|=\left|A\times B\right| \)
• \( \left|A\right|^{\left|B\right|}=\left|A^{B}\right| \)

כמובן, בשביל להבין מה הולך פה צריך להכיר את הפעולות על הקבוצות עצמן. אז בואו נזכיר אותן.

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

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

ועבור חזקה? כזכור, השימוש \( A^{B} \) משמש אותנו להגדרת קבוצת הפונקציות מ-\( B \) אל \( A \) (לאו דווקא פונקציות חח”ע/על; כל פונקציה). אם \( A,B \) קבוצות סופיות, אז קל לספור כמה פונקציות כאלו יש: כל פונקציה כזו צריכה לבצע \( \left|B\right| \) בחירות, אחת לכל איבר של \( B \) , לאן היא רוצה להעביר אותו. יש לנו \( \left|A\right| \) אפשרויות לכל בחירה כזו, כלומר מספר האפשרויות הכולל הוא \( \left|A\right|\cdot\left|A\right|\cdots\left|A\right| \) בדיוק \( \left|B\right| \) פעמים, ולכן בסך הכל \( \left|A\right|^{\left|B\right|} \). זה מסביר גם את מה שנראה כמו “היפוך” שבו \( A^{B} \) הוא פונקציות מ-\( B \) אל \( A \) ולא ההפך; זה מה שמסתדר לנו עם התוצאה המספרית המתמטית.

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

זה הולך ככה:

• \( \kappa+\lambda\triangleq\left|A\cup B\right| \) עבור קבוצות \( A,B \) כך ש-\( \left|A\right|=\kappa,\left|B\right|=\lambda \) ו-\( A\cap B=\emptyset \)
• \( \kappa\cdot\lambda\triangleq\left|A\times B\right| \) עבור קבוצות \( A,B \) כך ש-\( \left|A\right|=\kappa,\left|B\right|=\lambda \)
• \( \kappa^{\lambda}\triangleq\left|A^{B}\right| \) עבור קבוצות \( A,B \) כך ש-\( \left|A\right|=\kappa,\left|B\right|=\lambda \)

ההגדרה הזו טיפה בעייתית כי היא מסתמכת על בחירת נציגים עבור \( \kappa,\lambda \), וצריך להוכיח שלמרות זאת הכל מוגדר היטב. כלומר, שאם ניקח \( A^{\prime},B^{\prime} \) כך ש-\( \left|A^{\prime}\right|=\kappa,\left|B^{\prime}\right|=\lambda \) אז נקבל ש-\( \left|A\cup B\right|=\left|A^{\prime}\cup B^{\prime}\right| \) (אם גם הקבוצות החדשות זרות) ו-\( \left|A\times B\right|=\left|A^{\prime}\times B^{\prime}\right| \) ו-\( \left|A^{B}\right|=\left|\left(A^{\prime}\right)^{B^{\prime}}\right| \).

אלו הוכחות סטנדרטיות אבל בואו נבין את הרעיון עבור המקרה של \( \left|A\times B\right|=\left|A^{\prime}\times B^{\prime}\right| \): אם \( \left|A\right|=\kappa=\left|A^{\prime}\right| \) אז בפרט קיימת פונקציה \( f_{A}:A\to A^{\prime} \) שהיא חח”ע ועל, ובדומה קיימת \( f_{B}:B\to B^{\prime} \) חח”ע ועל. עכשיו נגדיר \( g:A\times B\to A^{\prime}\times B^{\prime} \) בדרך ה”טבעית”: \( g\left(\left(a,b\right)\right)=\left(f_{A}\left(a\right),f_{B}\left(b\right)\right) \). זו פונקציה חח”ע כי אם \( g\left(\left(a,b\right)\right)=g\left(\left(x,y\right)\right) \) אז \( \left(f_{A}\left(a\right),f_{B}\left(b\right)\right)=\left(f_{A}\left(x\right),f_{B}\left(y\right)\right) \) ומהגדרת מכפלה קרטזית נקבל שוויון רכיב-רכיב, כלומר \( f_{A}\left(a\right)=f_{A}\left(x\right) \) ומכך ש-\( f_{A} \) חח”ע נקבל \( a=x \) ובאופן דומה נקבל \( b=y \) ולכן \( \left(a,b\right)=\left(x,y\right) \). בנוסף, \( g \) גם על כי אם \( \left(x,y\right)\in A^{\prime}\times B^{\prime} \) אז מהגדרת מכפלה קרטזית \( x\in A^{\prime} \) ומכיוון ש-\( f_{A} \) על קיים \( a\in A \) כך ש-\( f_{A}\left(a\right)=x \) ובדומה קיים \( b\in B \) כך ש-\( f_{B}\left(b\right)=y \) ולכן \( g\left(\left(a,b\right)\right)=\left(f_{A}\left(a\right),f_{B}\left(b\right)\right)=\left(x,y\right) \).

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

• \( \kappa+\lambda=\lambda+\kappa \) וגם \( \kappa\cdot\lambda=\lambda\cdot\kappa \) (קומוטטיביות)
• \( \left(\kappa+\lambda\right)+\theta=\lambda+\left(\kappa+\theta\right) \) וגם \( \left(\kappa\cdot\lambda\right)\cdot\theta=\lambda\cdot\left(\kappa\cdot\theta\right) \) (אסוציאצטיביות)
• \( \kappa\left(\lambda+\theta\right)=\kappa\lambda+\kappa\theta \) (דיסטריביוטיביות)
• \( \left(\kappa\lambda\right)^{\theta}=\kappa^{\theta}\lambda^{\theta} \)
• \( \kappa^{\lambda+\theta}=\kappa^{\lambda}\cdot\kappa^{\theta} \)
• \( \left(\kappa^{\lambda}\right)^{\theta}=\kappa^{\lambda\theta} \)
• אם \( \kappa\le\lambda \) אז \( \kappa^{\theta}\le\lambda^{\theta} \)
• אם \( 0<\lambda\le\theta \) אז \( \kappa^{\lambda}\le\kappa^{\theta} \)
• \( \kappa^{0}=1 \), \( 1^{\kappa}=1 \) ו-\( 0^{\kappa}=0 \) אם \( \kappa>0 \)

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

יש דברים שהם קצת יותר ברורים מהאחרים: למשל, קומוטטיביות ואסוציאטיביות של חיבור וכפל נובעת מהקומוטטיביות והאסוציאטיביות של איחוד ומכפלה קרטזית של קבוצות (מכפלה קרטזית של שתי קבוצות היא לא בדיוק אסוציאטיבית אבל קרוב מספיק: \( \left(A\times B\right)\times C\sim A\times\left(B\times C\right) \) בצורה פשוטה). מעניין לחשוב על מה “נשבר” בקומוטטיביות בהקשר של חיבור וכפל של סודרים, הרי משתמשים גם שם באיחוד זר ובמכפלה קרטזית - אלא שבמקרה של סודרים יש מבנה נוסף של יחס סדר שמוגדר על הקבוצות הללו, והוא מוגדר בצורה מאוד לא סימטרית.

בכל זאת, בלי להוכיח משהו מהטענות אי אפשר, אז אני אבחר את החביבה עלי (ולטעמי הכי מורכבת להוכחה כאן): \( \left(\kappa^{\lambda}\right)^{\theta}=\kappa^{\lambda\theta} \). כלומר, אני צריך להראות שעבור שלוש קבוצות \( A,B,C \) מתקיים \( \left(\left|A\right|^{\left|B\right|}\right)^{\left|C\right|}=\left|A\right|^{\left|B\right|\left|C\right|} \), כלומר שמתקיים \( \left|\left(A^{B}\right)^{C}\right|=\left|A^{B\times C}\right| \), כלומר שמתקיים \( \left(A^{B}\right)^{C}\sim A^{B\times C} \). כלומר, מספיק אם אראה פונקציה חח”ע ועל \( \Psi:A^{B\times C}\to\left(A^{B}\right)^{C} \): אני בונה התאמה \( \Psi \) שמקבלת פונקציה בשני משתנים \( f:B\times C\to A \), ובונה מתוכה פונקציה שמחזירה פונקציות. אותי זה קצת הפחיד בהתחלה, אבל אפשר לחשוב על זה בדרך נוחה: על \( f\left(b,c\right) \) אני חושב בתור פונקציה במשתנה יחיד שתלויה בפרמטר. \( b \) הוא המשתנה, ו-\( c \) הוא הפרמטר. למשל, פונקציית הלוגריתם היא כזו: \( \log x \) מניחה באופן מובלע שיש בסיס ללוגריתם. כשכותבים \( \log \) בדרך כלל מתכוונים במובלע לבסיס 10, וכשכותבים \( \ln \) מתכוונים לבסיס \( e \) וכשכותבים \( \lg \) מתכוונים לבסיס 2; באופן כללי כותבים \( \log_{b}x \) כדי לציין שזה לוגריתם בבסיס \( b \). אז, קונספטואלית, \( \log_{b}x \) היא פונקציה במשתנה יחיד (\( x \)) שתלויה בפרמטר (\( b \)). אם ממש רוצים, אפשר גם לחשוב עליה בתור פונקציה בשני משתנים, \( \left(x,b\right) \). ההתאמה \( \Phi \) עושה את הסוויץ’ בין שתי נקודות המבט הללו.

הרעיון הוא כזה: נניח שיש לי ביד פונקציה של שני משתנים, \( f\left(x,y\right) \), ואני מקבל ערך קונקרטי, \( c\in C \), שאני יכול להציב בתוך המשתנה השני. אז אני מציב אותו ומשאיר את המשתנה הראשון “פתוח” ומקבל פונקציה במשתנה אחד, \( f_{c}\left(x\right)=f\left(x,c\right) \). הטריק הזה שבו אני מקבל פונקציה של כמה משתנים, מבצע בה “הצבה חלקית” ומקבל פונקציה חדשה נקרא Currying, על שם הלוגיקאי והפילוסוף הסקל קרי. אם חושבים על מה שהלך בטריק הזה, מה שקרה הוא שלכל ערך \( c\in C \) אני ייצרתי פונקציה \( f_{c}:B\to A \). כלומר, יש לי פונקציה \( \Phi_{f}:C\to A^{B} \) שמוגדרת על ידי \( \Phi_{f}\left(c\right)=f_{c} \).

עכשיו אפשר לחזור אל האובייקט שאני אמור להראות את קיומו: פונקציה חח”ע ועל \( \Psi:A^{B\times C}\to\left(A^{B}\right)^{C} \). אני יכול סוף סוף להגדיר אותו, וזה יוצא די פשוט עם הסימונים שנתתי:

\( \Psi\left(f\right)=\Phi_{f} \)

למה זו פונקציה חח”ע ועל? ראשית, אם \( \Psi\left(f\right)=\Psi\left(g\right) \), כלומר אם \( \Phi_{f}=\Phi_{g} \), זה אומר שלכל \( c\in C \) \( \Phi_{f}\left(c\right)=\Phi_{g}\left(c\right) \), כלומר לכל \( c\in C \) \( f_{c}=g_{c} \), כלומר לכל \( \left(b,c\right) \) מתקיים \( f\left(b,c\right)=f_{c}\left(b\right)=g_{c}\left(b\right)=g\left(b,c\right) \), ומכאן ש-\( f=g \), מה שמראה ש-\( \Psi \) חח”ע.

שנית, אם יש לנו \( \Phi\in\left(A^{B}\right)^{C} \) כלשהי, אני אגדיר פונקציה \( f\in A^{B\times C} \) באופן הבא:

\( f\left(b,c\right)\triangleq\Phi\left(c\right)\left(b\right) \)

כלומר, אני קודם כל מחשב את \( \Phi\left(c\right) \), מקבל פונקציה ב-\( A^{B} \), ואז מפעיל את הפונקציה הזו על \( b \) ומחזיר את התוצאה. כעת, אני כזכור מסמן \( \Psi\left(f\right)=\Phi_{f} \); אם אני אראה ש-\( \Phi=\Phi_{f} \), סיימנו. בשביל להראות את זה, צריך להראות שהן מזדהות על כל הקלטים, כלומר לכל \( c\in C \) מתקיים \( \Phi\left(c\right)=\Phi_{f}\left(c\right) \). הפלטים הללו הם בעצמם פונקציות על \( B \), אז צריך להראות שלכל \( b\in B \) מתקיים \( \Phi\left(c\right)\left(b\right)=\Phi_{f}\left(c\right)\left(b\right) \), אבל זה נובע ישירות מההגדרה:

\( \Phi_{f}\left(c\right)\left(b\right)=f_{c}\left(b\right)=f\left(b,c\right)=\Phi\left(c\right)\left(b\right) \)

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

ועכשיו... בואו נדבר על השערת הרצף

לפני שנדבר על השערת הרצף, בואו נשים לב למשהו קל שנובע ממה שכבר ראינו: אם אני מסמן ב-\( \mathcal{P}\left(A\right) \) את קבוצת החזקה של \( A \), כלומר קבוצת כל תתי-הקבוצות של \( A \) (היא קיימת כי יש אקסיומה מיוחדת שמניחה שהיא קיימת), אז \( \left|\mathcal{P}\left(A\right)\right|=2^{\left|A\right|} \).

ההוכחה די פשוטה: צריך להראות ש-\( \mathcal{P}\left(A\right)\sim2^{A} \). בהינתן \( B\in\mathcal{P}\left(A\right) \) נעביר אותה אל הפונקציה \( \chi_{B}:A\to2 \) (בואו נזכר ש-\( 2=\left\{ 0,1\right\} \) על פי ההגדרות שלנו) שמוגדרת על ידי

\( \chi_{B}\left(a\right)=\begin{cases} 1 & a\in B\\ 0 & a\notin B \end{cases} \)

זה מה שנקרא הפונקציה המציינת של \( B \) וקל לראות שזו התאמה חח”ע ועל. זה משתלב יפה עם הבחירה שלנו לסמן את \( \mathcal{P}\left(A\right) \) לפעמים בתור \( 2^{A} \); אלו לא קבוצות זהות מבחינה פורמלית, אבל הן בתכל’ס אותו הדבר עד כדי סימונים.

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

השערת הרצף הועלתה במקור בידי גאורג קנטור, ממציא תורת הקבוצות. בנאום 23 הבעיות המתמטיות המפורסם שלו מ-1900, דויד הילברט הציב את השערת הרצף בתור השאלה הפתוחה הראשונה ברשימה. קנטור עצמו האמין שהתשובה חיובית וש-\( \aleph_{1}=2^{\aleph_{0}} \); שקבוצה מ”עוצמת ביניים” כזו בין \( \aleph_{0} \) ובין \( 2^{\aleph_{0}} \) תהיה דבר מוזר ביותר, אבל הוכחה - לא נמצאה. בינתיים עבר קצת זמן, ועל תורת הקבוצות עברו תהפוכות עם גילוי הפרדוקס של ראסל.

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

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

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

כיוון אחד הוא קל: הגדרה סטנדרטית של \( \mathbb{R} \) היא באמצעות חתכי דדקינד. בצורה זו, כל \( r\in\mathbb{R} \) מיוצג על ידי קבוצה \( \left\{ q\in\mathbb{Q}\ |\ q<r\right\} \). ספציפית, מתקיים \( r=\sup\left\{ q\in\mathbb{Q}\ |\ q<r\right\} \). מכאן שיש לנו התאמה חח”ע מ-\( \mathbb{R} \) אל \( 2^{\mathbb{Q}} \), כלומר \( \left|\mathbb{R}\right|\le\left|2^{\mathbb{Q}}\right|=2^{\aleph_{0}} \).

הכיוון השני מעניין יותר. כדי להראות \( 2^{\aleph_{0}}\le\left|\mathbb{R}\right| \) די להראות התאמה חח”ע מאוסף הסדרות הבינאריות אל \( \mathbb{R} \), כש”סדרה בינארית” היא פונקציה מ-\( \mathbb{N} \) אל \( \left\{ 0,1\right\} \) שאפשר פשוט לכתוב בתור \( b_{0},b_{1},b_{2},\ldots \) עם \( b_{i}\in\left\{ 0,1\right\} \). כמובן, זה לא משנה בפועל אם בסדרה מופיע 1 או אם נחליף את כל המופעים של 1 ב-2, אז בואו נניח שהסדרה \( \left\{ b_{i}\right\} _{i=1}^{\infty} \) שלנו מקיימת דווקא \( b_{i}\in\left\{ 0,2\right\} \) כי זה מאוד יקל עלינו עוד שניה.

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

בלי להיכנס להגדרה של מידה, הרעיון הוא שאם אפשר לכסות קבוצה על ידי אוסף של קטעים קטנים כרצוננו (שסכום האורכים שלהם קטן מאיזה \( \varepsilon>0 \) נתון) אז היא ממידה אפס, וזה מה שקורה עם קבוצת קנטור - בכל שלב בבניה היא מכוסה על ידי אוסף הקטעים שבידינו באותו שלב, והאורך הכולל של הקטעים בשלב \( n \) הוא \( 2^{n}\cdot\left(\frac{1}{3}\right)^{n}=\left(\frac{2}{3}\right)^{n} \) - שואף לאפס כש-\( n \) שואף לאינסוף.

והנה זה פלא, למרות שהסרנו מהקבוצה את כל ה”אורך” שלה, עדיין היא לא בת מניה; אפשר להוכיח שאיבר שייך לקבוצת קנטור אם ורק אם אפשר לכתוב אותו בתור \( \sum_{n=0}^{\infty}\frac{a_{i}}{3^{n}} \) כך ש-\( a_{i}\in\left\{ 0,2\right\} \). הרעיון הוא לפתח את האיבר לייצוג טרנרי (בבסיס 3) ולהראות שאיבר מוסר מהבניה, כלומר הוא שייך לקטע אמצעי כלשהו בשלב הבניה ה-\( n \), רק אם הספרה במקום ה-\( n \) בכל ייצוג טרנרי שלו היא 1 (האינטואיציה הלא מדויקת עד הסוף היא הספרה 0 מכניסה אותו לחלק השמאלי והספרה 2 מכניסה אותו לחלק הימני של הקטע שחולק לשלושה חלקים; הזסיבה שצריך להיזהר היא שיש מספרים עם שני ייצוגים טרנריים שונים ומספיק ש-1 לא יופיע בכלל באחד מהם).

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

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

• \( \beth_{0}=\omega \)
• \( \beth_{\alpha+1}=2^{\beth_{\alpha}} \) לכל סודר \( \alpha \).
• \( \beth_{\alpha}=\text{sup}\left\{ \beth_{\beta}\ |\ \beta<\alpha\right\} \) כאשר \( \alpha \) הוא סודר גבולי.

בניסוח הזה, השערת הרצף היא הטענה \( \aleph_{1}=\beth_{1} \), ואפשר לנסח טענה חזקה יותר - השערת הרצף המוכללת, שאומרת ש-\( \aleph_{\alpha}=\beth_{\alpha} \) לכל סודר \( \alpha \). אני לא אתעסק עם ההשערה הזו בפוסטים שלי כרגע - השערת הרצף הרגילה זה די והותר עבורי…