ויקיפדיה:מיזמי ויקיפדיה/קורסים/תורת הקבוצות/תוכן הקורס

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

שיעור ראשון - מבוא

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

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

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

שיעור שני - מושג הקבוצה

• כיתת הלימוד

קבוצה היא אוסף של איברים (בתורת הקבוצות הנאיבית מושג הקבוצה אינו מוגדר, אבל מכאן ואילך נדייק יותר). אחת הדרכים להצגת קבוצה היא בתור רשימה של איברים, בין סוגריים מסולסלים (כאלה: $\ \{\ \}$), מופרדים בפסיקים. למשל, קבוצת האבות היא $\ \}$אברהם, יצחק, יעקב$\ \{$$\ A=\$, ואומרים שאברהם הוא איבר של הקבוצה $\ A$, או שהוא שייך לקבוצה. הקשר הוא הדדי: בקבוצה יש איברים, והאיברים שייכים לקבוצה. את יחס השייכות מסמנים עם אפסילון ירחי: $\ a\in A$ פירושו ש-$\ a$ הוא איבר בקבוצה $\ A$. כדי לומר ש-$\ b$ אינו שייך לקבוצה $\ A$, כותבים $\ b\not \in A$. לשמות האותיות אין כמובן חשיבות.

לקבוצה אין מבנה מעבר לנוכחות או ההעדר של איברים בתוכה. כלומר:

1. אין חשיבות לסדר האיברים. לדוגמה, הקבוצה $\{1,2,3\}$ שווה לקבוצה $\{3,2,1\}$.
2. אין חשיבות לחזרה על אותם איברים. לדוגמה, הקבוצה $\{1,2,2,3,3,3\}$ שווה לקבוצה $\{1,2,3\}$. איבר יכול להופיע או לא להופיע, אבל לא "להופיע פעמיים".

כשמספר האברים בקבוצה גדול ואין חשש לטעות, אפשר להעזר בסימון השלוש נקודות. לדוגמה, $\ N=\{0,1,2,\ldots ,9\}$ הוא כתיב מקוצר ל- $\ N=\{0,1,2,3,4,5,6,7,8,9\}$, ו- $\ \mathbb {N} =\{0,1,2,\ldots \}$ מתאר את קבוצת כל המספרים הטבעיים.

שיעור שלישי - שוויון קבוצות

• כיתת הלימוד

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

• הקבוצות $\ A$ ו-$\ B$ שוות אם ורק אם כל איבר של $\ A$ הוא איבר של $\ B$, וכל איבר של $\ B$ הוא איבר של $\ A$.

אפשר גם לנסח בכתיב יותר פורמלי:

• הקבוצות $\ A$ ו-$\ B$ שוות אם ורק אם לכל x, ($x\in A$ אם ורק אם $x\in B$).

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

קבוצה שאין בה אף איבר נקראת "קבוצה ריקה". כעת נוכיח את המשפט הראשון בקורס שלנו:

משפט. כל הקבוצות הריקות שוות. (במלים אחרות, אם $\ A$ ו-$\ B$ שתיהן קבוצות ריקות, אז הן שוות זו לזו).

הוכחה. לפי ההגדרה, כדי שהקבוצות תהיינה שוות, כל איבר של $\ A$ צריך להיות איבר של $\ B$, וכל איבר של $\ B$ צריך להיות איבר של $\ A$. אבל בשתי הקבוצות אין איברים, ולכן התנאי מתקיים באופן ריק.

השוויון הזה מצדיק הוספת הא הידיעה - יש קבוצה ריקה אחת, הנקראת הקבוצה הריקה.

את הקבוצה הריקה מסמנים בסימון מיוחד: $\emptyset$ ולפעמים גם $\ \{\}$. יש הבדל בין חדר ריק, לבין חדר שאין בו מאומה מלבד ארגז גדול וריק. באותו אופן יש הבדל בין הקבוצה הריקה (שבה יש אפס איברים), לבין הקבוצה $\ \{\emptyset \}$ שיש לה איבר אחד (הלוא הוא הקבוצה הריקה). אם בארגז שלנו מונחת קופסת נעליים ריקה, הוא אינו ריק; במקרה כזה אפשר לתאר את החדר ובו הארגז כקבוצה שיש לה איבר אחד, שהוא הקבוצה שיש לה איבר אחד, שהוא הקבוצה הריקה. זוהי כמובן הקבוצה $\ \{\{\emptyset \}\}=\{\{\{\}\}\}$.

תרגיל. כמה איברים יש בכל אחת מהקבוצות $\ \{\emptyset \}$, $\ \{\{\emptyset \}\}$ ו-$\ \{\emptyset ,\{\emptyset \}\}$? האם כולן שונות זו מזו? הוכח.

שעור רביעי - תת-קבוצות והכלה

• כיתת הלימוד

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

• הקבוצה A מוכלת בקבוצה B אם כל איבר של A הוא איבר B (בניסוח פורמלי אפשר לומר: לכל $\ x\in A$ מתקיים $\ x\in B$).

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

כמובטח, ההכלה מפרקת את יחס השוויון לשני תנאים סימטריים:

תרגיל. A=B אם ורק אם ($\ A\subseteq B$ וגם $\ B\subseteq A$).

תכונה חשובה אחרת של ההכלה היא ה"טרנזיטיביות" שלה:

תרגיל. אם $\ A\subseteq B$ ו- $\ B\subseteq C$ אז $\ A\subseteq C$.

הקבוצה הריקה היא הקבוצה הקטנה ביותר, ביחס להכלה. פירושו של דבר:

תרגיל. כל קבוצה מכילה את הקבוצה הריקה. אף קבוצה שאינה ריקה אינה מוכלת בקבוצה הריקה.

קבוצה המוכלת ב-B נקראת תת-קבוצה שלה. אחת הדרכים הנוחות לבנות קבוצה חדשה, היא בתור תת-קבוצה של קבוצה קיימת. למשל, $\ \{x\in \mathbb {N} :x<19\}$ היא קבוצה של מספרים בקבוצת המספרים הטבעיים $\ \mathbb {N}$ (בהגדרה מפורשת: קבוצת כל המספרים הטבעיים הקטנים מ-19). באופן כללי אפשר לתאר תת-קבוצה באמצעות תנאי, כך: $\ \{x\in A:\varphi (x)\}$ כאשר $\ \varphi$ הוא פסוק (פסוק הוא ביטוי סופי שאפשר לפענח באופן חד-משמעי). למעשה, תורת הקבוצות האקסיומטית (שאיננה חלק מקורס זה) מעדיפה תאורים כאלה; היא מספקת קבוצה אינסופית אחת ודרך אחת לבנות קבוצה "גדולה" מקבוצה נתונה. היא אינה מאפשרת לאסוף איברים לקבוצה באופן חופשי, אלא רק כתת-קבוצות של קבוצה קיימת, וגם זאת רק כשאפשר להגדיר את האברים בתת-הקבוצה באמצעות פסוק מתאים.

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

• הקבוצה הריקה $\ \emptyset$ מוכלת בעצמה, אבל אינה שייכת לעצמה;
• לעומת זאת, הקבוצה הריקה $\ \emptyset$ מוכלת בקבוצה $\ \{\emptyset \}$ ושייכת לה;
• הקבוצה $\ \{\emptyset \}$ שייכת לקבוצה $\ B=\{\{\emptyset \}\}$ אבל אינה מוכלת בה (משום ש-$\ \emptyset \not \in B$).
• הקבוצה $\ \{\emptyset \}$ אינה מוכלת בקבוצה הריקה ואינה שייכת לה.

תרגיל. תן דוגמא נוספת לכל אחת מהאפשרויות לעיל.

שעור חמישי - פעולות בין קבוצות

• כיתת הלימוד

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

הגדרה. האיחוד של שתי קבוצות A,B הוא הקבוצה שאבריה הם כל האברים השייכים ל-A או ל-B (או לשתיהן), ורק הם. את האיחוד מסמנים $\ A\cup B$.

הגדרה. החיתוך של שתי קבוצות A,B הוא הקבוצה שאבריה הם האברים השייכים ל-A וגם ל-B, ורק הם. את החיתוך מסמנים $\ A\cap B$.

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

• $\ A\cap A=A\cup A=A$;
• $\ A\cap B=B\cap A$, $\ A\cup B=B\cup A$;
• $\ (A\cap B)\cap C=A\cap (B\cap C)$, $\ (A\cup B)\cup C=A\cup (B\cup C)$.

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

• $\ A\cup \emptyset =A$, $\ A\cap \emptyset =\emptyset$.

הדרך הקלה לבדוק יחסים אלה, ומסובכים מהם (כמו $\ (A\cup B)\cap C=(A\cap C)\cup (B\cap C)$), היא באמצעות דיאגרמת וון, המקודדת את הקבוצות ותוצאות הפעולות עליהן באופן גרפי.

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

איחוד וחיתוך כלליים

בדיוק כפי שאפשר לאחד או לחתוך שתי קבוצות, אפשר לאחד ולחתוך אוסף כלשהו של קבוצות, סופי או אינסופי.

הגדרה. תהי $\ {\mathcal {A}}$ קבוצה של קבוצות. "האיחוד של $\ {\mathcal {A}}$", $\ \cup {\mathcal {A}}$, הוא קבוצה שאבריה הם כל האברים השייכים לאיבר כלשהו של $\ {\mathcal {A}}$, כלומר $\ x\in \cup {\mathcal {A}}$ אם ורק אם קיים $\ a\in {\mathcal {A}}$ כך ש- $\ x\in a$. באותו אופן, "החיתוך של $\ {\mathcal {A}}$", $\ \cap {\mathcal {A}}$, הוא קבוצה שאבריה הם כל האברים השייכים לכל האיברים של $\ {\mathcal {A}}$, כלומר $\ x\in \cap {\mathcal {A}}$ אם ורק אם לכל $\ a\in {\mathcal {A}}$ מתקיים $\ x\in a$.

לדוגמה, האיחוד של $\ {\mathcal {A}}=\{A,B\}$ הוא האיחוד של שתי הקבוצות, $\ \cup {\mathcal {A}}=A\cup B$.

(שמתם לב להבדל בין $\ A$ ו-$\ {\mathcal {A}}$? סימונים שונים מייצגים יישויות שונות; השימוש בסימונים דומים עשוי להיות מכוון, משום שקל יותר לזכור ש-$\ a,\alpha \in A\in {\mathcal {A}}$ ו-$\ b,\beta \in B\in {\mathcal {B}}$ מאשר ש-$\ y\in T\in {\mathcal {K}}$ ו-$\ r\in P\in {\mathcal {L}}$).

שעור שישי - משלים וחוקי דה-מורגן

• כיתת הלימוד

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

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

הגדרה. ההפרש $\ A-B$ הוא הקבוצה שאבריה הם האברים של A שאינם שייכים ל-B.

תרגיל. לכל שתי קבוצות A ו-B, ההפרש $\ A-B$ מוכל ב-A.

תרגיל. לכל קבוצה A, $\ A-A=\emptyset$ ו- $\ A-\emptyset =A$.

תרגיל. תן דוגמא המראה שפעולת ההפרש אינה אסוציאטיבית, כלומר, מצא שלוש קבוצות A,B ו-C כך ש- $\ A-(B-C)\neq (A-B)-C$.

ההפרש הוא פעולה בינארית. אם נקבע את ה"מרחב" X של האברים שבהם אנו מעוניינים לצורך הדיון ונחשב תמיד הפרש ביחס אליו, נקבל פעולה אונארית:

הגדרה. המשלים של קבוצה A, ביחס למרחב קבוע X, הוא קבוצת האברים של X שאינם ב-A. מסמנים את המשלים של $\ A$ ב-$\ {\overline {A}}$.

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

תרגיל. המשלים מקיים את התכונות הבאות: $\ {\overline {\overline {A}}}=A$ ("לא לא A" הוא "A"); וכן $\ {\overline {\emptyset }}=X,{\overline {X}}=\emptyset$ (לא אמת הוא שקר, לא שקר הוא אמת).

חוקי דה-מורגן

במקום לומר "חתול אינו שייך לקבוצת הרהיטים, וגם אינו שייך לקבוצת החרקים המעופפים", אפשר לומר "החתול אינו שייך לקבוצת הדברים שהם או רהיטים, או חרקים מעופפים". את השקילות הזו (שיש לה בוודאי דוגמאות שימושיות יותר) אפשר לנסח כך: דבר-מה אינו P וגם אינו Q, אם ורק אם הוא אינו (P או Q). חוקי דה-מורגן מציגים את הכלל הלוגי הזה בשפה של קבוצות, ומבטאים את האופן שבו קושר המשלים את פעולות האיחוד והחיתוך: $\ {\overline {A\cup B}}={\overline {A}}\cap {\overline {B}}$, ו- $\ {\overline {A\cap B}}={\overline {A}}\cup {\overline {B}}$.

תרגיל. צייר דיאגרמות וון המוכיחות את חוקי דה-מורגן.

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

תרגיל (קל יותר). נניח שכל אברי האוסף $\ {\mathcal {A}}$ מוכלים בקבוצה X. הוכח את הגרסה הכללית ביותר של חוק דה-מורגן - המשלים של האיחוד על אברי האוסף הוא חיתוך המשלימים שלהם.

ההפרש הסימטרי

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

הגדרה. ההפרש הסימטרי של הקבוצות A ו-B הוא קבוצת האיברים הנמצאים באחת הקבוצות, אבל לא בשתיהן. את ההפרש הסימטרי מסמנים ב- $\ A\Delta B$.

תרגיל. הוכיחו כי $\ A\Delta B=(A\cup B)-(A\cap B)=(A-B)\cup (B-A)$.

תרגיל. ההפרש הסימטרי מקיים את התכונות הבאות: $\ (A\Delta B)\Delta C=A\Delta (B\Delta C)$ (אסוציאטיביות); $\ A\Delta \emptyset =A$ (קיום איבר נייטרלי); $\ A\Delta A=\emptyset$ (קיום הופכי); $\ A\Delta B=B\Delta A$ (קומוטטיביות); $\ (A\Delta B)\cap C=(A\cap C)\Delta (B\cap C)$ (דיסטריבוטיביות ביחס לחיתוך).

שעור שביעי - קבוצת החזקה

• כיתת הלימוד

הגדרה. תהי $\ A$ קבוצה. קבוצת החזקה של $\ A$ היא הקבוצה שאבריה הם תת-הקבוצות של $\ A$. את קבוצת החזקה של $\ A$ מסמנים ב-$\ P(A)$.

כלומר, קבוצה $\ x$ שייכת ל-$\ P(A)$, אם ורק אם $\ x\subseteq A$. מכיוון שהקבוצה $\ A$ תמיד מוכלת בעצמה, $\ A\in P(A)$. גם הקבוצה הריקה מוכלת ב-$\ A$, ולכן $\ \emptyset \in P(A)$.

דוגמא. האברים בקבוצת החזקה של $\ \{1,2\}$ הם הקבוצות $\ \emptyset ,\{1\},\{2\},\{1,2\}$.

תרגיל. קבוצת החזקה של כל קבוצה $\ A$ מכילה את $\ A$ ואת הקבוצה הריקה. מצא דוגמה נגדית לטענה (השגויה) "בכל קבוצת חזקה יש לפחות שני אברים".

תרגיל. כתוב את כל האברים של $\ P(\{1,2,3\})$.

תרגיל. קבע האם $\ \{\emptyset ,\{\emptyset \}\}$ הוא איבר בקבוצת החזקה $\ P(\{\emptyset ,\{\emptyset ,\{\emptyset \}\}\})$.

תרגיל. הוכח (באינדוקציה) שאם בקבוצה $\ A$ יש בדיוק $\ n$ אברים שונים, אז בקבוצה $\ P(A)$ יש $\ 2^{n}$ אברים שונים.

תרגיל. אם $\ A\subseteq B$ אז $\ P(A)\subseteq P(B)$.

תרגיל. א. הוכח או הפרך: $\ P(A\cup B)=P(A)\cup P(B)$. ב. הוכח או הפרך: $\ P(A\cap B)=P(A)\cap P(B)$.

שעור שמיני - זוגות סדורים

• כיתת הלימוד

כשהגדרנו את השוויון בין קבוצות, הדגשנו שבתוך הקבוצה אין חשיבות לסדר בין האיברים: $\ \{7,2\}=\{2,7\}$. עובדה זו באה לידי ביטוי בטענה הבאה, שאותה נוכיח בזהירות, כהכנה לשלבים הבאים בשעור זה.

טענה. $\ \{a,b\}=\{c,d\}$ אם ורק אם ($\ a=c$ ו- $\ b=d$), או ($\ a=d$ ו- $\ b=c$).

הוכחה. a הוא איבר בקבוצה שבאגף שמאל, ומכיוון שהקבוצות שוות, הוא איבר גם בזו שבאגף ימין, שיש לה (לכל היותר) שני אברים - c ו-d. ("לכל היותר", משום ש-c ו-d עשויים להיות שווים). אותה טענה נכונה גם לגבי b. אם a ו-b שווים לאותו איבר, אז הם שווים גם זה לזה, ולכן בקבוצה שבאגף שמאל יש רק איבר אחד; לכן גם בזו שבאגף ימין צריך להיות רק איבר אחד, ומכאן ש-c=d; במקרה כזה מתקיימים שני התנאים שהבטחנו. אחרת, a ו-b אינם שווים לאותו איבר, ואז אחד מהם שווה ל-c והשני שווה ל-d.

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

הגדרה (Kuratowski, 1921). הזוג הסדור $\,(a,b)$ מוגדר כקבוצה $\ \{\{a\},\{a,b\}\}$.

כדי שיהיה מוצדק לקרוא לקבוצה $\ \{\{a\},\{a,b\}\}$ "זוג סדור", עלינו לוודא שאפשר לקרוא ממנה את הרכיב הראשון והרכיב השני, באופן חד-משמעי.

משפט. $\ (a,b)=(c,d)$ אם ורק אם $\ a=c$ ו- $\ b=d$.

הוכחה. אם $\ a=c$ ו- $\ b=d$ אז $\ \{a\}=\{c\}$ ו- $\ \{a,b\}=\{c,d\}$, ולכן $\ \{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}$. נראה שגם הכיוון ההפוך נכון. נתון ש- $\ \{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}$. לפי הטענה מתחילת השעור, יש שתי אפשרויות: ($\ \{a\}=\{c\}$ ו- $\ \{a,b\}=\{c,d\}$), או ($\ \{a\}=\{c,d\}$ ו- $\ \{a,b\}=\{c\}$). במקרה הראשון $\ a=c$ משום שכל אחד מהם הוא האיבר היחיד בקבוצה $\ \{a\}=\{c\}$; השוויון $\ \{a,b\}=\{c,d\}$ מראה (לפי אותה טענה) ש-($\ a=c$ ו- $\ b=d$), או ($\ a=d$ ו- $\ b=c$); אם האפשרות הראשונה נכונה - קיבלנו מה שרצינו לקבל, ואם השניה נכונה אז $\ d=a=c=b$, ושוב קיבלנו מה שרצינו. במקרה השני, (שבו, כזכור, $\ \{a\}=\{c,d\}$ ו- $\ \{a,b\}=\{c\}$), מתברר ש-$\ c,d\in \{a\}$ ולכן $\ a=c=d$, וכך גם $\ a=b=c$; לכן $\ a=c$ ו- $\ b=d$.

תרגיל. בדוק שאם $\ a\neq b$ אז הזוגות הסדורים $\ (a,b),(b,a)$ שונים זה מזה.

תרגיל. אשר ש- $\ (1,3)\cap (3,1)=\{\{1,3\}\}$.

תרגיל. חשב את (הקבוצה שהיא) הזוג הסדור $\ (a,a)$. כמה איברים יש לו?

לאור ההצלחה המסחררת של ההגדרה הזו, טבעי לנסות ולבדוק כמה אפשרויות אחרות. כדי שלא לבלבל, נסמן את הזוגות שיופיעו בהגדרות המתחרות בסימון $\ [a,b]$.

תרגיל. נגדיר $\ [a,b]=\{a,b\}$. מצא זוג $\ [a,b]=[c,d]$ שבו $\ a\neq c$ או $\ b\neq d$. לכן זו הגדרה גרועה לזוג סדור (ואיננו משתמשים בה).

תרגיל. נגדיר $\ [a,b]=\{a,\{b\}\}$. מצא זוג $\ [a,b]=[c,d]$ שבו $\ a\neq c$ או $\ b\neq d$.

תרגיל. הנח שלא יתכן שקבוצות x,y תקיימנה $\ x\in x$ או $\ x\in y\in x$, והוכח את המשפט ($\ [a,b]=[c,d]$ אם ורק אם הרכיבים שווים בהתאמה) עבור ההגדרה $\ [a,b]=\{a,\{a,b\}\}$ (ההנחה בתרגיל זה נראית אולי מוזרה במסגרת שבה אנו עובדים, אבל בתורת הקבוצות האקסיומטית היא מופיעה באופו טבעי ומתבקש).

תרגיל. נגדיר $\ [a,b]=\{a,b,\{b\}\}$. האם בהגדרה זו אפשר לקרוא באופן חד-משמעי את הרכיב הראשון והרכיב השני?

תרגיל. נגדיר $\ [a,b]=\{a,\{b,\{b\}\}\}$. האם בהגדרה זו אפשר לקרוא באופן חד-משמעי את הרכיב הראשון והרכיב השני?

תרגיל. נגדיר (בעקבות Wiener, 1914) $\ [a,b]=\{\{\{a\},\emptyset \},\{\{b\}\}\}$. הראה שתחת ההגדרה הזו אפשר לקרוא באופן חד-משמעי את שני הרכיבים.

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

הגדרה. ה-n-יה הסדורה $\ (a_{1},\dots ,a_{n})$ מוגדרת כזוג סדור, שרכיבו הראשון $\ a_{1}$, ורכיבו השני $\ (a_{2},\dots ,a_{n})$.

תרגיל. הוכח ש- $\ (a_{1},\dots ,a_{n})=(b_{1},\dots ,b_{n})$ אם ורק אם $\ a_{1}=b_{1},a_{2}=b_{2},\dots ,a_{n}=b_{n}$.

תרגיל. כתוב במפורש (כקבוצה) את השלשה הסדורה $\ (a,b,c)$. כתוב במפורש את השלשות $\ (a,a,a)$, $\ (a,b,b)$, $\ (a,a,b)$.

תרגיל. הסבר מדוע ההגדרה $\ [a,b,c]=\{\{a\},\{a,b\},\{a,b,c\}\}$ אינה טובה כהגדרה לשלשה סדורה.

שעור תשיעי - מכפלה קרטזית

• כיתת הלימוד

המושג הבא שנפגוש מבוסס על רעיון גאומטרי פשוט: כדי לתאר מלבן מישורי, שצלעותיו ניצבות לצירים, יש לתאר כל קואורדינטה בנפרד. למשל, כדי לבדוק אם אנחנו נמצאים בקבוצת הבלוקים במנהטן הנמצאים בין הרחוב ה-18 לרחוב ה-23 ובין השדרה ה-7-ית לשדרה ה-9-ית, עלינו לבדוק - בנפרד! - האם אנחנו ברחוב שבין 18 ל-23, והאם אנחנו בשדרה שבין ה-7-ית ל-9-ית. כמובן, המפתח להגדרה הוא הזוג הסדור שבנינו בשעור הקודם.

הגדרה. המכפלה הקרטזית של הקבוצות A ו-B היא הקבוצה $\ A\times B$ שאבריה הם כל הזוגות הסדורים $\ (a,b)$ עם $\ a\in A$ ו- $\ b\in B$.

דוגמא. $\ \{1\}\times \{2,6,7\}=\{(1,2),(1,6),(1,7)\}$, ו- $\ \{0,2\}\times \{0,3\}=\{(0,0),(0,3),(2,0),(2,3)\}$.

תרגיל. הוכח שהמכפלה הקרטזית $\ A\times B$ היא הקבוצה הריקה אם ורק אם אחד הגורמים A או B הוא הקבוצה הריקה.

אם בקבוצה A יש n אברים ובקבוצה B יש m אברים, אז במכפלה הקרטזית $\ A\times B$ יש nm אברים (בדוק טענה זו עבור ערכים קטנים של n ו-m). את העובדה הזו אפשר להוכיח באינדוקציה. אפשר גם להיפך - להגדיר את המכפלה של שני מספרים טבעיים, כמספר הזוגות הסדורים במכפלה קרטזית של קבוצות בגודל המתאים. דיון בהבדל שבין שתי הגישות (והקשר שלהן למערכת פאנו ואריתמטיקה של סודרים) נמצא מחוץ לגבולות הקורס הקצר שלנו.

תרגיל. הוכח שהזוג הסדור $\ (a,b)$ (שהוא, כזכור, הקבוצה $\ \{\{a\},\{a,b\}\}$) מוכל בקבוצת החזקה $\ P(\{a,b\})$, ושייך לקבוצת החזקה שלה, $\ P(P(\{a,b\}))$.

טענה. לכל שתי קבוצות A,B, המכפלה הקרטזית $\ A\times B$ מוכלת בקבוצת החזקה $\ P(A\cup B)$, ושייכת לקבוצת החזקה שלה, $\ P(P(A\cup B))$.

הוכחה. כדי להוכיח ש- $\ A\times B\subseteq P(A\cup B)$ עלינו לבדוק שכל זוג סדור $\ (a,b)\in A\times B$ שייך לקבוצה $\ P(A\cup B)$; אבל לפי התרגיל הקודם, הזוג הסדור שייך ל- $\ P(\{a,b\})$ המוכלת ב- $\ P(A\cup B)$ משום ש- $\ \{a,b\}\subseteq A\cup B$. כתת-קבוצה של $\ P(A\cup B)$, ברור ש- $\ A\times B\in P(P(A\cup B))$.

שעור עשירי - פונקציות

• כיתת הלימוד

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

הגדרה. פונקציה מ-A ל-B היא תת-קבוצה $\ f\subset A\times B$, כך שלכל $\ a\in A$, קיים $\ b\in B$ יחיד כך ש- $\ (a,b)\in f$. מסמנים $\ f:A\rightarrow B$; את הערך b המוזכר בהגדרה מסמנים בסימון המוכר $\,f(a)$. לפעמים אומרים שהפונקציה "מוגדרת מ-A", או "מוגדרת אל B".

דוגמא. הפונקציה המתאימה לכל מספר שלם בין 3 ל-7 את הריבוע שלו היא קבוצת הזוגות הסדורים $\ \{(3,9),(4,16),(5,25),(6,36),(7,49)\}$.

דוגמא. לכל קבוצה A יש פונקציה $\ id_{A}:A\rightarrow A$ הנקראת "פונקציית הזהות", וכוללת את כל הזוגות $\ (a,a)$ עבור $\ a\in A$, ורק אותם. הפונקציה הזו מתאימה לכל איבר של A את עצמו.

תרגיל. כתוב את כל הפונקציות האפשריות מהקבוצה $\ \{1,4\}$ לקבוצה $\ \{2,8\}$.

תרגיל. לכל קבוצה B, הפונקציה היחידה $\ \emptyset \rightarrow B$ היא הקבוצה הריקה.

תרגיל. אם A קבוצה לא ריקה, אז לא קיימות פונקציות $\ A\rightarrow \emptyset$.

תרגיל. אם $\ f,g:A\rightarrow B$ שתיהן פונקציות, ואחת מהן מכילה את רעותה (בתור תת-קבוצות של $\ A\times B$), אז הן שוות.

הערה. אם $\ f:A\rightarrow B$ היא פונקציה ו- $\ B\subseteq B'$ קבוצה, אז אפשר לראות ב-f פונקציה $\ A\rightarrow B'$ (זוהי "הרחבת טווח הפונקציה"). בדומה לזה, אם $\ A'\subseteq A$ תת-קבוצה, אז אפשר לצמצם את f לכדי פונקציה $\ f|_{A'}:A'\rightarrow B$ ("צמצום תחום הפונקציה"); הפונקציה המצומצמת מוגדרת לפי $\ f|_{A'}=f\cap (A'\times B)$, כלומר, היא כוללת את הזוגות $\ (a,b)\in f$ שעבורם $\ a\in A'$.

אם $\ f:A\rightarrow B$ פונקציה, אז לכל תת-קבוצה $\ A_{0}\subseteq A$ מסמנים $\ f(A_{0})=\{f(x):x\in A_{0}\}$, וזו תת-קבוצה של B. באופן הזה הפונקציה מגדירה פונקציה $\ P(A)\rightarrow P(B)$. זוהי הגדרה שימושית מאד, משום שלעתים קרובות אנו רוצים להפעיל את הפונקציה בבת-אחת על קבוצה של אברים. שימו לב שאם $\ A_{0}\subseteq A_{1}$ הן תת-קבוצות של A, אז $\ f(A_{0})\subseteq f(A_{1})$.

פונקציות חד-חד-ערכיות

• כיתת הלימוד

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

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

הגדרה. פונקציה $\ f:A\rightarrow B$ היא פונקציה חד-חד-ערכית אם לכל $\ a,a'\in A$, מהשוויון $\ f(a)=f(a')$ נובע $\ a=a'$. במלים אחרות, לכל $\ a\neq a'$ ב-A מתקיים $\ f(a)\neq f(a')$.

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

תרגיל. כמה פונקציות חד-חד-ערכיות יש מקבוצה בגודל 3 לקבוצה בגודל 4? וכמה מקבוצה בגודל 4 לקבוצה בגודל 3?

תרגיל. הוכח: הקבוצה הריקה, כפונקציה $\ \emptyset \rightarrow B$, היא חד-חד-ערכית.

תרגיל. כתוב את כל הפונקציות מהקבוצה $\ \{9,11\}$ אל עצמה, שהן חד-חד-ערכיות.

פונקציות על

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

הגדרה. פונקציה $\ f:A\rightarrow B$ היא פונקציה על אם לכל $\ b\in B$ קיים $\ a\in A$ כך ש-$\ f(a)=b$.

תרגיל. הסבר מדוע הפונקציה $\ f(x)=x^{2}$ מן המספרים הממשיים אל המספרים החיוביים היא על, אבל אינה חד-חד-ערכית.

תרגיל. כמה פונקציות על יש מקבוצה בגודל 3 לקבוצה בגודל 4? וכמה מקבוצה בגודל 4 לקבוצה בגודל 3?

תרגיל. כתוב את כל הפונקציות מהקבוצה $\ \{9,11\}$ על עצמה. השווה את התשובה לתרגיל הקודם שעסק באותה קבוצה.

הערה. הפונקציה $\ f:A\rightarrow B$ היא גם פונקציה $\ A\rightarrow f(A)$; וככזו, היא תמיד על.

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

• כיתת הלימוד

אם g היא הפונקציה המתאימה לכל בעל מכונית את המכונית הראשונה שלו, ו- f הפונקציה המתאימה לכל מכונית את נפח המנוע שלה, יהיה נוח להמציא פונקציה חדשה, המתאימה לכל בעל מכונית את נפח המנוע של המכונית הראשונה שלו, ולתאר אותה באמצעות הפונקציות g ו-f. אכן, לפי הסימון המקובל, המכונית של בעל מכונית x היא $\ g(x)$, ונפח המנוע שלה הוא $\ f(g(x))$. לפונקציה המוגדרת באופן כזה קוראים הרכבת הפונקציות f ו-g, ומסמנים אותה בסימון $\ f\circ g$ (שימו לב לסדר הפונקציות בהרכבה).

הגדרה. אם A,B,C קבוצות ו- $\ f:B\rightarrow C$ ו- $\ g:A\rightarrow B$ הן פונקציות, אז $\ f\circ g:A\rightarrow C$ היא הפונקציה המוגדרת לפי הנוסחה $\ (f\circ g)(x)=f(g(x))$. בשפת תורת הקבוצות, הזוג הסדור $\ (a,c)\in A\times C$ שייך ל- $\ f\circ g$ אם ורק אם קיים $\ b\in B$ כך ש- $\ (a,b)\in g$ ו- $\ (b,c)\in f$.

טענה. בתנאי ההגדרה, ההרכבה היא אכן פונקציה מ-A ל-C.

הוכחה. יהי $\ a\in A$. עלינו להוכיח שקיים $\ c\in C$ יחיד כך ש- $\ (a,c)\in f\circ g$; כלומר, שקיים c יחיד שעבורו קיים b כך ש- $\ (a,b)\in g$ ו- $\ (b,c)\in f$; אבל מכיוון ש-g פונקציה, קיים $\ b\in B$ יחיד כך ש- $\ (a,b)\in g$, ועבור אותו b, מכיוון ש-f פונקציה, קיים c יחיד כך ש- $\ (b,c)\in f$.

הערה. אם נתונות פונקציות $\ g:A\rightarrow B,\,f:B'\rightarrow C$, הגדרנו את ההרכבה $\ f\circ g$ רק בהנחה ש- $\ B'=B$; עם זאת, לפי הערה קודמת על הרחבת טווח הפונקציה, מספיק להניח ש- $\ B\subseteq B'$.

הרכבת פונקציות מקיימת את תכונת האסוציאטיביות:

הערה. אם $\ h:A\rightarrow B,\,g:B\rightarrow C,\,f:C\rightarrow D$ הן פונקציות, אז $\ f\circ (g\circ h)=(f\circ g)\circ h$ (הסוגריים מציינים, כרגיל, את סדר הפעולות).

תרגיל. אם f,g פונקציות חד-חד-ערכיות וההרכבה ביניהן מוגדרת, אז היא חד-חד-ערכית.

תרגיל. הוכח או הפרך: אם ההרכבה $\ f\circ g$ היא חד-חד-ערכית, אז שתי הפונקציות f,g הן חד-חד-ערכיות.

הפונקציה ההפוכה

הגדרנו פונקציה $\ f:A\rightarrow B$ כאוסף של זוגות סדורים במכפלה $\ A\times B$. ההגדרה הזו מאפשרת "להפוך" את הפונקציה באופן טבעי - נוכל להגדיר את $\ f^{-1}$ כקבוצת כל הזוגות הסדורים ההפוכים לאלו הנמצאים ב-f, כלומר $\ f^{-1}=\{(b,a):(a,b)\in f\}$. התוצאה היא תת-קבוצה של המכפלה $\ B\times A$, וזה מעלה את השאלה מתי מתקבלת באופן הזה פונקציה מ-B ל-A.

טענה. תהי $\ f:A\rightarrow B$ פונקציה. הקבוצה $\ f^{-1}$ היא פונקציה מ-B ל-A אם ורק אם f חד-חד-ערכית ועל.

הוכחה. $\ f^{-1}$ היא פונקציה אם לכל b קיים a יחיד כך ש- $\ (b,a)\in f^{-1}$; כלומר, לכל b קיים a יחיד כך ש- $\ (a,b)\in f$; כלומר, לכל b קיים a יחיד כך ש- $\ f(a)=b$. הדרישה ש-a כזה קיים שקולה לכך ש-f על, והיחידות שקולה לכך ש-f חד-חד-ערכית.

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

טענה. אם $\ f:A\rightarrow B$ היא חד-חד-ערכית ועל, אז הפונקציה ההפוכה $\ f^{-1}:B\rightarrow A$ גם היא חד-חד-ערכית ועל.

הוכחה. כדי ש-$\ f^{-1}$ תהיה חד-חד-ערכית ועל, נדרש שלכל a יהיה b יחיד כך ש- $\ f^{-1}(b)=a$, כלומר $\ (b,a)\in f^{-1}$ או $\ (a,b)\in f$; אבל תכונה זו מתקיימת מכיוון ש-f פונקציה.

טענה. אם $\ f:A\rightarrow B$ פונקציה חד-חד-ערכית ועל, אז ההרכבה $\ f^{-1}\circ f$ היא פונקציית הזהות של A, ואילו $\ f\circ f^{-1}=id_{B}$.

הוכחה. לכל $\ a\in A$ קיים $\ b\in B$ (יחיד, אבל כרגע אין בזה צורך) כך ש- $\ (a,b)\in f$. לפי הגדרת הפונקציה ההפוכה, $\ (b,a)\in f^{-1}$, ולפי ההגדרה של הרכבת פונקציות נובע מכאן ש- $\ (a,a)\in f^{-1}\circ f$. לכן ההרכבה מכילה את פונקציית הזהות, ומכאן שהיא שווה לה. באשר לכיוון ההפוך, שימו לב שמן ההגדרה נובע מיד ש- $\ (f^{-1})^{-1}=f$, ולכן די להפעיל את החלק שהוכחנו על הפונקציה $\ f^{-1}:B\rightarrow A$.

שעור שנים-עשר - עוצמה של קבוצה

• כיתת הלימוד

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

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

למרות כל הקשיים האלה, ואולי בגללם, ההגדרה של קנטור פשוטה למדי, ומבוססת על התכונות הבסיסיות של פונקציות הפיכות. המטרה היא להגדיר את המושג המרכזי של הקורס הזה - מושג העוצמה של קבוצה. מסיבה עקרונית שנסביר בהמשך, איננו מגדירים במפורש מהי העוצמה של קבוצה. במקום זה, אנו מסתפקים בקביעה מתי יש לשתי קבוצות אותה עוצמה. ההגדרה מבוססת על שידוך של אברי שתי הקבוצות על-ידי סידורם בזוגות. נבחין שאוסף של זוגות סדורים $\ f\subseteq A\times B$ שבו לכל איבר $\ a\in A$ יש איבר יחיד $\ b\in B$ המתאים לו (כלומר $\ (a,b)\in f$), ולהיפך, אינו אלא פונקציה חד-חד-ערכית ועל $\ f:A\rightarrow B$. הבחנה זו מוליכה להגדרה המרכזית:

הגדרה. הקבוצות A ו-B "שוות-עוצמה" אם קיימת פונקציה חד-חד-ערכית ועל מ-A ל-B.

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

טענה 1. כל קבוצה שוות-עוצמה לעצמה.

הוכחה. פונקציית הזהות היא פונקציה חד-חד-ערכית ועל מן הקבוצה אל עצמה. (תרגיל).

טענה 2. אם הקבוצות A ו-B שוות-עוצמה, אז גם הקבוצות B ו-A שוות-עוצמה.

הוכחה. אם $\ f:A\rightarrow B$ היא פונקציה חד-חד-ערכית ועל, אז הפונקציה ההפוכה $\ f^{-1}:B\rightarrow A$ גם היא חד-חד-ערכית ועל.

טענה 3. אם הקבוצות A ו-B שוות-עוצמה, וכך גם הקבוצות B ו-C, אז גם הקבוצות A ו-C שוות-עוצמה.

הוכחה. אם $\ f:A\rightarrow B$ ו- $\ g:B\rightarrow C$ חד-חד-ערכיות ועל, אז גם ההרכבה $\ g\circ f:A\rightarrow C$ היא חד-חד-ערכית ועל.

התכונות שהוכחנו כעת הן התכונות הבסיסיות של יחס השוויון: כל דבר שווה לעצמו, אם A שווה ל-B אז B שווה ל-A, ושני גדלים השווים לגודל שלישי שווים ביניהם. לכן אנחנו מציינים את העובדה ששתי קבוצות הן שוות-עוצמה בסימון דומה, וכותבים $\ |A|=|B|$.

תרגיל. הוכח שלקבוצה הריקה יש עוצמה ייחודית משלה, ואף קבוצה אחרת אינה שוות-עוצמה לה.

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

תרגיל. לכל n טבעי, הסבר מדוע כל הקבוצות שיש להן n אברים הן שוות-עוצמה.

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

שעור שלושה-עשר - קבוצות סופיות ואינסופיות

• כיתת הלימוד

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

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

הגדרה. קבוצה נקראת "אינסופית" אם היא שוות-עוצמה לתת-קבוצה אמיתית שלה, ו"סופית" אם לא. ("תת-קבוצה אמיתית" היא תת-קבוצה שאינה שווה לקבוצה עצמה).

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

טענה. שלוש הטענות הבאות שקולות: (1) A אינסופית; (2) יש פונקציה חד-חד-ערכית $\ A\rightarrow A$ שאינה על; (3) יש פונקציה $\ A\rightarrow A$ על שאינה חד-חד-ערכית.

הוכחה. אם (1) מתקיים אז לפי ההגדרה יש לה תת-קבוצה אמיתית $\ B\subset A$ עם פונקציה חד-חד-ערכית ועל $\ f:A\rightarrow B$. הפונקציה הזו, כשרואים אותה כפונקציה ל-A, היא חד-חד-ערכית אבל אינה על, ולכן מתקיים (2). הפונקציה ההפוכה $\ f^{-1}:B\rightarrow A$ היא חד-חד-ערכית ועל, וכשמרחיבים את תחום ההגדרה שלה לכל A על-ידי התאמת כל הנקודות ב-$\ A-B$ לנקודה מסויימת ב-A, היא על, אבל אינה חד-חד-ערכית; לכן מתקיים (3). מאידך, נניח שמתקיים (2), אז f היא חד-חד-ערכית ועל מ-A אל הטווח שלה $\ \{f(x):x\in A\}$, המוכל ממש ב-A, ולכן (1); ואם מתקיים (3), אז אפשר לבחור לכל איבר ב-A איבר ש-f מתאימה אליו, ואז A שוות-עוצמה עם קבוצת המקורות האלה, המוכלת ממש ב-A.

טענה. אם A קבוצה אינסופית אז כל קבוצה B המכילה אותה היא אינסופית.

הוכחה. לפי הטענה הקודמת יש פונקציה $\ f:A\rightarrow A$ שהיא על ואינה חד-חד-ערכית. נרחיב את הפונקציה הזו לפונקציה $\ g:B\rightarrow B$ על-ידי שנגדיר $\ g(x)=f(x)$ אם $\ x\in A$ ו- $\ g(x)=x$ אחרת. בדוק (תרגיל) ש-g על ואינה חד-חד-ערכית.

מסקנה. אם B קבוצה סופית אז כל תת-קבוצה שלה היא סופית. (אחרת B מכילה קבוצה אינסופית).

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

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

• כיתת הלימוד

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

למרות שעד כה הגדרנו רק מתי שתי קבוצות הן שוות-עוצמה, כדי שלא לסרבל את ההגדרות, נדבר מעכשיו על העוצמה $\ |A|$, ונתכוון ל-$\ A$ או כל קבוצה שוות-עוצמה לה. בפרט, נסמן ב-$\ n$ ("העוצמה $\ n$") את העוצמה של קבוצה (כלשהי) בת $\ n$ ("המספר הטבעי $\ n$") אברים.

תרגיל. לכל קבוצה $\ A$, אם בקבוצה $\ S$ יש איבר יחיד, אז $\ |A|=|A\times S|$.

תרגיל. אם $\ A,B$ זרות ו- $\ A',B'$ זרות, ומתקיים $\ |A|=|A'|$ ו- $\ |B|=|B'|$, אז $\ |A\cup B|=|A'\cup B'|$.

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

הגדרה. אם $\ A,B$ קבוצות זרות, אז סכום העוצמות שלהן הוא עוצמת האיחוד $\ A\cup B$ (היינו, $\ |A|+|B|=|A\cup B|$). באופן כללי (אם לא ידוע ש-$\ A$ ו-$\ B$ זרות), אפשר להעזר בתרגיל האחרון כדי להתחכם ולהחליף אותן במכפלות הקרטזיות $\ A\times \{1\}$ ו-$\ B\times \{2\}$, שהן בוודאי זרות.

תרגיל. לכל עוצמה $\ |A|+|\emptyset |=|A|$ (לכן עוצמת הקבוצה הריקה נקראת אפס); לכל שתי עוצמות, $\ |A|+|B|=|B|+|A|$; לכל שלוש עוצמות מתקיים $\ (|A|+|B|)+|C|=|A|+(|B|+|C|)$.

תרגיל. אם $\ |A|=|A'|$ ו- $\ |B|=|B'|$ אז $\ |A\times B|=|A'\times B'|$. (כעת אפשר להשתמש במכפלה הקרטזית כדי להגדיר פעולה בין עוצמות).

הגדרה. מכפלת עוצמות מוגדרת כעוצמת המכפלה הקרטזית, $\ |A|\cdot |B|=|A\times B|$. (כאן אין צורך להניח שהקבוצות זרות).

תרגיל. אם $\ S$ קבוצה בת איבר אחד, אז לכל עוצמה, $\ |A|\cdot |S|=|A|$; לכל שתי עוצמות מתקיים $\ |A|\cdot |B|=|B|\cdot |A|$ (מה בעצם מוכיחים כאן?); לכל שלוש עוצמות מתקיים $\ (|A|\cdot |B|)\cdot |C|=|A|\cdot (|B|\cdot |C|)$ (וכאן?); לכל שלוש עוצמות מתקיים $\ |A|\cdot (|B|+|C|)=|A|\cdot |B|+|A|\cdot |C|$.

ואל הפעולה השלישית והאחרונה -

הגדרה. לכל שתי קבוצות $\ A,B$, הקבוצה $\ A^{B}$ מסמנת את אוסף כל הפונקציות $\ B\rightarrow A$.

תרגיל. אם $\ |A|=|A'|$ ו- $\ |B|=|B'|$ אז $\ |A^{B}|=|{A'}^{B'}|$.

פתרון. לפי ההנחה יש פונקציות חד-חד-ערכיות ועל $\ f:A\rightarrow A'$ ו- $\ g:B\rightarrow B'$. עלינו לבנות פונקציה חד-חד-ערכית ועל מקבוצת הפונקציות $\ A^{B}$ אל הקבוצה $\ {A'}^{B'}$; בדוק שהפונקציה $\ \Phi (h)=g\circ h\circ f^{-1}$ עונה על הדרישות.

הגדרה. החזקה של עוצמות מוגדרת כעוצמה של קבוצת הפונקציות, היינו $\ |A|^{|B|}=|A^{B}|$.

תרגיל. לכל שלוש עוצמות מתקיים $\ |A|^{|B|+|C|}=|A|^{|B|}\cdot |A|^{|C|}$; לכל שלוש עוצמות מתקיים $\ |A|^{|B|\cdot |C|}=(|A|^{|B|})^{|C|}$; לכל שלוש עוצמות מתקיים $\ (|A|\cdot |B|)^{|C|}=|A|^{|C|}\cdot |B|^{|C|}$.

שעור חמישה-עשר - קבוצות בנות מנייה

• כיתת הלימוד

את קבוצת כל המספרים הטבעיים מסמנים באות $\ \mathbb {N} =\{0,1,2,3,\cdots \}$. אם A שוות-עוצמה לקבוצה זו, פירושו של דבר שאפשר למנות את אברי A בהתאמה למספרים הטבעיים, ולכתוב $\ A=\{a_{0},a_{1},a_{2},a_{3},\cdots \}$, כאשר האיברים $\,a_{i}$ שונים זה מזה. קבוצות כאלה נקראות קבוצות בנות-מנייה. כמו שלכל עוצמה סופית נתנו שם משלה (שם של מספר טבעי), גם לעוצמת הקבוצות בנות-המנייה יש שם מיוחד - אלף אפס, וכותבים $\ |\mathbb {N} |=\aleph _{0}$.

הערה. קבוצות בנות-מניה הן אינסופיות. אכן, הפונקציה $\ x\mapsto x+1$ מ- $\ \mathbb {N}$ אל עצמה היא חד-חד-ערכית אבל אינה על.

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

משפט. A אינסופית אם ורק אם היא מכילה קבוצה בת-מנייה.

הוכחה. לפי הטענה מסוף שעור 13, קבוצה המכילה קבוצה בת-מנייה (שהיא אינסופית) היא אינסופית בעצמה. כעת נניח ש-A אינסופית. פירושו של דבר הוא שיש פונקציה $\ f:A\rightarrow A$ שהיא חד-חד-ערכית אבל אינה על. נסמן $\ f^{0}(A)=A$, ובאינדוקציה $\ f^{n+1}(A)=f(f^{n}(A))$. לפי ההנחה, $\ f^{1}(A)\subset f^{0}(A)$. נראה, באינדוקציה, שלכל n>0 מתקיים $\ f^{n+1}(A)\subset f^{n}(A)$: ההכלה ברורה (משום ש- $\ f^{n+1}(A)=f^{n}(f(A))\subseteq f^{n}(A)$); ואם מתקיים שוויון, אז גם $\ f^{n}(A)=f^{n-1}(A)$ שהרי f חד-חד-ערכית, וזו סתירה להנחת האינדוקציה. כעת נותר רק לבחור איבר $\ a_{n}$ מכל הפרש $\ f^{n}(A)-f^{n+1}(A)$. ההפרשים זרים זה לזה (תרגיל), ולכן האיברים שונים, ותת-הקבוצה $\ \{a_{0},a_{1},a_{2},\dots \}$ של A היא בת-מנייה.

טענה. תת-קבוצה של קבוצה בת-מנייה היא סופית או בת-מנייה.

הוכחה. מספיק להוכיח את הטענה עבור תת-קבוצות $\ A\subseteq \mathbb {N}$, וקבוצה כזו אפשר למנות באינדוקציה ($\ a_{0}$ הוא האיבר הקטן ביותר של A, $\ a_{1}$ הוא האיבר הקטן ביותר מלבדו, וכן הלאה).

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

טענה. אם יש פונקציה מקבוצה בת-מנייה על A, אז A סופית או בת-מנייה.

הוכחה. נניח שיש פונקציה על $\ f:\mathbb {N} \rightarrow A$. לכל איבר a של A, אפשר לבחור איבר $\ n\in \mathbb {N}$ כך ש- $\ f(n)=a$. קבוצת המקורות האלה היא בת-מנייה או סופית לפי הטענה הקודמת, והיא שוות-עוצמה ל-A.

עוד קבוצות בנות-מנייה

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

טענה. אם A בת-מנייה, אז גם $\ A\times A$ בת-מנייה. כלומר, $\ \aleph _{0}^{2}=\aleph _{0}$.

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

מסקנה. יש פונקציה מן הזוגות הסדורים $\ \mathbb {N} \times \mathbb {N}$ אל המספרים הרציונליים החיוביים המוגדרת לפי $\ (a,b)\mapsto {\frac {a+1}{b+1}}$, שהיא על. לפי הטענה לעיל, גם אוסף הרציונליים החיוביים הוא בן-מנייה.

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

תרגיל. לכל n, $\ \aleph _{0}^{n}=\aleph _{0}$ (אינדוקציה על n).

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

טענה. אם $\ A_{1},A_{2},\dots$ סדרה של קבוצות סופיות או בנות-מנייה, אז האיחוד של כולן, $\ \cup A_{i}$ (הכולל את כל האיברים הנמצאים בקבוצה אחת לפחות מאלה המשתתפות באיחוד) גם הוא סופי או בן-מנייה.

הוכחה. לכל i יש פונקציה על $\ f_{i}:\mathbb {N} \rightarrow A_{i}$, ולכן הפונקציה $\ f:\mathbb {N} \times \mathbb {N} \rightarrow \cup A_{i}$ המוגדרת לפי $\ f(i,n)=f_{i}(n)$, היא על. אבל $\ \mathbb {N} \times \mathbb {N}$ בת-מנייה.

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

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

טענה. אם A אינסופית ו-Z סופית או בת-מנייה, אז $\,|A\cup Z|=|A|$ (כלומר, $\ |A|+\aleph _{0}=|A|+n=|A|$ לכל עוצמה סופית n).

הוכחה. מכיוון ש-A אינסופית יש לה תת-קבוצה בת-מנייה C, ואז $\ |A\cup Z|=|C\cup Z|+|A-C|=|C|+|A-C|=|A|$ כי $\ |C|+|Z|=\aleph _{0}+\aleph _{0}=\aleph _{0}=|C|$.

להרחבה בנושא שעור זה, ראו המלון של הילברט.

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

• כיתת הלימוד

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

טענה. יש פונקציה חד-חד-ערכית $\ A\rightarrow B$ אם ורק אם יש פונקציה על $\ B\rightarrow A$.

הוכחה. נזכיר שפונקציה היא אוסף של זוגות סדורים. אם $\ f:A\rightarrow B$ חד-חד-ערכית, אז "הפונקציה ההפוכה" מ-B ל-A אמנם אינה בהכרח פונקציה (היא אינה מוגדרת בכל הנקודות של B), אבל אפשר להשלים אותה לפונקציה על-ידי הגדרה $\ f(b)=a_{0}$ לכל הנקודות שאינן בטווח של f, עבור $\ a_{0}\in A$ קבוע. הפונקציה המתקבלת היא על (תרגיל). ולהיפך, אם $\ g:B\rightarrow A$ על, אז הפונקציה ההפוכה מ-A ל-B אמנם אינה בהכרח פונקציה (היא עשויה לקבל יותר מערך אחד בנקודות מסויימות של A), אבל אם מדללים אותה על-ידי השמטה, לכל a, של כל הזוגות מהצורה $\ (a,*)$ פרט לאחד, מתקבלת פונקציה חד-חד-ערכית מ-A ל-B.

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

הגדרה. נאמר ש-$\ |A|\leq |B|$ אם A שוות-עוצמה לתת-קבוצה של B.

דוגמאות.

1. אם $\ |A|=|B|$ אז בוודאי $\ |A|\leq |B|$.
2. לכל תת-קבוצה $\ A\subseteq B$ מתקיים $\ |A|\leq |B|$.
3. בעבר הוכחנו שאם A אינסופית, אז $\ \aleph _{0}\leq |A|$.

לסימן אי-השוויון "$\,\!\leq$" יש כמה תכונות מתבקשות. ראשית היינו רוצים שיתקיים $\ |A|\leq |A|$ ("רפלקסיביות"). שנית, טרנזיטיביות --

הערה. אם $\ |A|\leq |B|$ ו- $\ |B|\leq |C|$ אז $\ |A|\leq |C|$.

הוכחה. לפי ההנחה יש פונקציות חד-חד-ערכיות מ-A ל-B ומ-B ל-C; ההרכבה היא פונקציה חד-חד-ערכית מ-A ל-C.

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

אם $\ A,B$ קבוצות, פונקציה $\ F:P(A)\rightarrow P(B)$ היא מונוטונית, אם לכל שתי תת-קבוצות $\ A_{0}\subseteq A_{1}$ של A, מתקיים $\ F(A_{0})\subseteq F(A_{1})$.

למה. תהי $\ F:P(A)\rightarrow P(B)$ פונקציה מונוטונית. נסמן ב-K את האיחוד של כל הקבוצות C המקיימות את התנאי $\ C\subseteq F(C)$ (כלומר, איבר $\ a\in A$ שייך ל-K אם ורק אם יש תת-קבוצה C של A המקיימת $\ a\in C\subseteq F(C)$). אז $\ K=F(K)$.

הוכחה. נסמן ב- (*) את התנאי $\ C\subseteq F(C)$. נראה ש-K עצמה מקיימת את התנאי. אכן, כל נקודה $\ x\in K$ שייכת לקבוצה $\ C$ המקיימת את התנאי (*), ולכן מוכלת ב-K; אבל אז $\ x\in F(C)\subseteq F(K)$. לפי המונוטוניות, מ- $\ K\subseteq F(K)$ נובע שגם $\ F(K)\subseteq F(F(K))$; אבל אז הקבוצה $\ F(K)$ עצמה מקיימת את התנאי (*), ולפי הגדרת K (שהיא איחוד כל הקבוצות האלה) היא מוכלת ב-K. לכן $\ K=F(K)$.

משפט קנטור-ברנשטיין. אם $\ |A|\leq |B|$ ו- $\ |B|\leq |A|$ אז $\ |A|=|B|$.

הוכחה.

1. לפי ההנחה, יש פונקציות חד-חד-ערכיות $\ f:A\rightarrow B$ ו- $\ g:B\rightarrow A$. נגדיר פונקציה $\ \Delta :P(A)\rightarrow P(A)$ לפי $\ \Delta (C)=A-g(B-f(C))$. קל לראות שהפונקציה הזו היא מונוטונית: אם $\ C\subseteq C'$ תת-קבוצות של A, אז $\ \Delta (C)\subseteq \Delta (C')$ מכיוון שהפעלת הפונקציות f ו-g שומרת על סדר ההכלה, ופעולת המשלים (המבוצעת כאן פעמיים) הופכת אותה.
2. נסמן ב- K את איחוד הקבוצות C המקיימות $\ C\subseteq \Delta (C)$. (תרגיל, שאינו נחוץ להמשך: $\ C\subseteq \Delta (C)$ אם לכל $\ x\not \in f(C)$ מתקיים $\ g(x)\not \in C$).
3. לפי הלמה, $\ K=\Delta (K)$.
4. השוויון $\ K=\Delta (K)=A-g(B-f(K))$ נותן $\ A-K=g(B-f(K))$, ומכיוון ש-g חד-חד-ערכית, יוצא ש- $\ |A-K|=|B-f(K)|$. והרי גם $\ |K|=|f(K)|$, ולכן $\ |A|=|A-K|+|K|=|B-f(K)|+|f(K)|=|B|$.

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

• כיתת הלימוד

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

נתחיל בבניה של קבוצה שאינה בת-מנייה. לפי ההגדרה, הקבוצה $\ 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 שאינה על?)

(הערה. לא יתכן ש- $\ |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 אינה קבוצה (זוהי הסיבה שבגללה לא הגדרנו מהי עוצמה והסתפקנו בהשוואה של עוצמות); וגם מחלקת כל העוצמות האפשריות גדולה מכדי להיות קבוצה.

שעור שמונה-עשר: סיכום וכיווני המשך

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

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

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

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