משפט קנטור

שעור שבעה-עשר: משפט קנטור

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

נתחיל בבניה של קבוצה שאינה בת-מנייה. לפי ההגדרה, הקבוצה $\ A^{\mathbb {N} }$ היא קבוצת הפונקציות מן המספרים הטבעיים אל הקבוצה A; אבל פונקציה מן המספרים הטבעיים אינה אלא התאמה של ערך לכל מספר טבעי, כלומר - סדרה של ערכים מ-A.

נסמן $\ 2=\{0,1\}$.

משפט. הקבוצה $\ 2^{\mathbb {N} }$ אינה בת-מנייה.

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

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

אנחנו כותבים $\ |A|<|B|$ אם $\ |A|\leq |B|$ ו- $\ |A|\neq |B|$. (פירושו של התנאי הזה אינו "קיימת פונקציה חד-חד-ערכית מ-A ל-B שאינה על", אלא "קיימת פונקציה חד-חד-ערכית מ-A ל-B, ולא קיימת פונקציה כזו שהיא על". מה משמעות התנאי הראשון?)

(הערה. לא יתכן ש- $\ |A|<|B|$ וגם $\ |B|<|A|$, משום שמזה נובע לפי הטרנזיטיביות $\ |A|<|A|$ ובפרט $\ |A|\neq |A|$.)

את עוצמת הקבוצה $\ 2^{\mathbb {N} }$, הלוא היא $\ 2^{\aleph _{0}}$, מסמנים באות $\ \aleph$. עוצמה זו נקראת עוצמת הרצף, משום שהיא עוצמתו של קטע רצוף של מספרים ממשיים; מכיוון שלא הגדרנו מהם מספרים ממשיים, לא נוכל להוכיח טענה זו כאן, אבל היא נובעת מן הפיתוח הבינארי של מספרים ממשיים.

מסקנה. $\ \aleph _{0}<\aleph$ (הפונקציה המתאימה לכל מספר n את הסדרה שכולה אפסים פרט ל-1 במקום ה-n היא בוודאי חד-חד-ערכית, ולכן $\ \aleph _{0}\leq 2^{\aleph _{0}}$; המשפט קובע שהעוצמות שונות).

נעיר שאת הקבוצה $\ 2^{\aleph _{0}}$ אנחנו כבר מכירים, למעשה, בשם אחר.

טענה. לכל קבוצה A, מתקיים שוויון העוצמות $\ |2^{A}|=|P(A)|$.

דוגמא. אם A היא הקבוצה הריקה, אוסף הפונקציות משמאל כולל רק פונקציה אחת, שהיא הקבוצה הריקה, ואילו אוסף תת-הקבוצות מימין כולל רק תת-קבוצה אחת - הקבוצה הריקה. היינו, $\ 2^{\emptyset }=\{\emptyset \}=P(\emptyset )$. לעומת זאת עבור $\ A=\{6\}$, אגף שמאל הוא $\ 2^{A}=\{\{(6,0)\},\{(6,1)\}\}$, ואגף ימין הוא $\ P(A)=\{\emptyset ,\{6\}\}$; בשתיהן שני אברים.

הוכחת הטענה. נבנה פונקציה $\ \Phi :2^{A}\rightarrow P(A)$, כך: $\ \Phi (f)=\{x\in A:f(x)=1\}$. תרגיל: בדוק שהפונקציה הזו חד-חד-ערכית ועל.

אם-כך, העוצמה האינסופית הקטנה ביותר היא $\ \aleph _{0}$, והמשפט מספק עוצמה גדולה ממנה, $\ 2^{\aleph _{0}}$. אפשר לתהות האם יש עוצמות בין שתי אלה - האם כל עוצמה אינסופית שאינה בת-מנייה גדולה לפחות כמו $\ 2^{\aleph _{0}}$. זוהי השערת הרצף, שהעלה קנטור, ונשארה פתוחה עד לאמצע שנות ה-60 של המאה ה-20.

פרדוקס הספר ומשפט קנטור

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

משפט קנטור. לכל קבוצה A, $\ |A|<|P(A)|$.

הוכחה. ראשית, ברור ש- $\ A\leq P(A)$, משום שהפונקציה המתאימה לכל איבר $\ a\in A$ את האיבר $\ \{a\}\in P(A)$ היא חד-חד-ערכית. נשאר להוכיח שלא קיימת פונקציה $\ A\rightarrow P(A)$ שהיא על. נניח שיש פונקציה כזו, $\ f:A\rightarrow P(A)$. שימו לב שלכל $\ a\in A$, $\ f(a)$ היא תת-קבוצה של A, ולכן a עשוי להיות שייך או לא שייך לה. נתבונן בקבוצה $\ X=\{a\in A:a\not \in f(a)\}$. בהנחה ש- f היא על, מוכרח להיות איבר $\ x\in A$ כך ש- $\ f(x)=X$. אבל אז, מה היחס בין x ל-X? אם $\ x\in X$, אז לפי ההגדרה של X, בהכרח $\ x\not \in f(x)=X$. ומאידך אם $\ x\not \in X$ אז לפי אותה הגדרה $\ x\in X$. הגענו לסתירה, שנבעה מן ההנחה ש- f היא על - ומכאן ש-f אינה יכולה להיות על, מה שהיה להוכיח.

שימו לב שעבור הקבוצה $\ A=\mathbb {N}$, הוכחה זו (בצירוף הוכחת השוויון $\ |2^{\mathbb {N} }|=|P(\mathbb {N} )|$) אינה אלא עקרון האלכסון בשינוי אדרת.

הפרדוקס של ראסל

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

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

אותו מכתב מערער הציג גרסה פורמלית של פרדוקס הספר, המכונה היום הפרדוקס של ראסל:

• "תהי A קבוצת כל הקבוצות שאינן שייכות לעצמן. האם A שייכת לעצמה?"

בהוכחה של משפט קנטור כבר ניתחנו את הטענה הזו, וראינו שהיא מובילה לסתירה. למעשה, אם נסמן ב-U את "קבוצת כל הקבוצות", יתברר לנו ש-$\ P(U)\subseteq U$ משום שקבוצה של אברים של U היא קבוצה, ולכן שייכת ל-U; מכאן ש-$\ |P(U)|\leq |U|$, וזו סתירה חזיתית למשפט קנטור, הקובע ש-$\ |U|<|P(U)|$. אכן, פרדוקס. הבעיה היא בהנחה הסמויה של תורת הקבוצות הנאיבית (שלה היה שותף גם פרגה), לפיה עבור כל תכונה ניתן לבנות קבוצה של כל האיברים המקיימים את התכונה. הפרדוקס של ראסל מראה שהנחת יסוד זו מביאה לסתירה, ולכן יש להמנע ממנה.

(תרגיל. נתח את הטענה "תהי A קבוצת כל הקבוצות שאינן מכילות את עצמן. האם A מכילה את עצמה?"; שים לב להבדל בין "שייך" לבין "מוכל".)

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

<< השיעור הקודם - משפט קנטור-ברנשטיין

דף הקורס - תורת הקבוצות

השיעור הבא - סיכום וכיווני המשך >>