מבוא לתורת הקבוצות

פרופסור רון אהרוני

הפקולטה למתמטיקה

הטכניון

מבוא לתורת הקבוצות

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

מנהל פרויקט כדאי לדעת: פרופ' אילון סולן

עריכת לשון: ד״ר דנה ברעם

ריכוז אדמיניסטרטיבי: גלית הרצברג

עיצוב גרפי ועימוד: ניצן-שמיר מעצבים

איור עטיפה: shutterstock

כתובת אתר כדאי לדעת: goodtoknow.tau.ac.il

תודות

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

אנו מודים לנועם וולף שסייע בעריכת החוברת ובכתיבת התרגילים, לפרופ' דוד גילת על הערותיו לחוברת, למורה בטי כהן ולתלמידי כיתות ז 4, ח 1, ח 3, ו-ח 4 בשנת הלימודים תשע"ט בחטיבת ביניים שמואל הנגיד בהרצליה שלמדו מהחוברת והעירו עליה.

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

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

גירסה 2 מרס 2024

תוכן

1. הקדמה 4

2. קבוצות ופעולות עם קבוצות 5

2.1 ייצוג של קבוצה 5

2.2 פעולות על קבוצות 7

איחוד של קבוצות 7

חיתוך של קבוצות 8

הפרש של קבוצות 8

הכלה של קבוצה 10

קבוצת התת-קבוצות 11

2.3 דיאגרמת וֶן 12

2.4 גודל של קבוצה סופית 15

3. אין-סופים גדולים וגדולים יותר 19

3.1 שוויון בין קבוצות 19

3.2 הפתעה 24

3.3 מה פירוש "למנות" 29

3.4 השוואה בין קבוצות 33

3.5 אי-שוויון בין קבוצות 38

3.6 שיטת האלכסון של קנטור 42

3.7 הפרדוקס של קנטור 45

3.8 איך בונים קבוצות 48

4. סיכום 52

5. פתרונות לתרגילים 53

1. הקדמה

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

קבוצה היא אוסף של עצמים הנקראים איברים. אוסף הילדים בכיתה הוא קבוצה. אוסף הנמלים הוא קבוצה גדולה יותר, שאת גודלה איננו יודעים. אוסף המספרים הטבעיים – 0, 1, 2, וכן הלאה1 – אף הוא קבוצה, שבה יש מספר אין-סופי של איברים.

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

2. קבוצות ופעולות עם קבוצות

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

(הלן קלר)

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

2.1 ייצוג של קבוצה

קבוצה היא אוסף של עצמים, מוחשיים או מופשטים, שנקרא להם איברים. דרך מקובלת לסמן קבוצה היא בעזרת סוגריים מסולסלים ועם פסיקים בין האיברים. לדוגמה, הקבוצה שאיבריה הם הצבעים אדום, כחול וצהוב תסומן {אדום, כחול, צהוב}, קבוצת ימי השבוע תסומן {ראשון, שני, שלישי, רביעי, חמישי, ששי, שבת}, והקבוצה שאיבריה הם כל המספרים הטבעיים תסומן {0,1,2,…}. את קבוצת המספרים הטבעיים נהוג לסמן באות N, המציינת את האות הראשונה במילה האנגלית natural, שמשמעותה טבעי. כלומר:

{0,1,2,…} = N.

איבר יכול להופיע בקבוצה פעם אחת בלבד. הקבוצה {אלי, גילי, איילה, גילי} מכילה פעמיים את האיבר גילי, ולכן אינה קבוצה.

במקום לרשום את איברי הקבוצה בתוך סוגריים מסולסלים, אפשר גם לרשום אותם בתוך אליפסה, ראו תרשים 1.

תרשים 1: שתי קבוצות מתוארות כאיברים הנמצאים בתוך אליפסה

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

קבוצה מיוחדת היא הקבוצה הריקה, שאינה מכילה אף איבר. מסמנים אותה כך: ø. בסימון הקודם נרשום ø = { }. לדוגמה, קבוצת האנשים בעולם שגובהם מעל 3 מטרים היא הקבוצה הריקה.

יש גם קבוצות שאיבריהן הם בעצמם קבוצות. למשל, איברי הקבוצה {{1,2}, {3,4}} הם שתי קבוצות, שבכל אחת מהן שני איברים: הקבוצה {1,2} והקבוצה {3,4}. הקבוצה {רחל} מכילה איבר אחד בלבד, האדם רחל, והקבוצה {{רחל}} מכילה אף היא רק איבר אחד, שהוא הקבוצה שאיברה היחיד הוא האיבר רחל. מכיוון שהקבוצה {רחל} שונה מהאיבר רחל, הרי {רחל, {רחל}} היא קבוצה שמכילה שני איברים, שאחד מהם הוא קבוצה.

היכן נתקלים באופן טבעי בקבוצות שאיבריהן קבוצות? כל ועדה בכיתה – לדוגמה ועדת חברה, ועדת קישוט, ועדת ספורט – היא קבוצה שאיבריה הם חברי הוועדה. למשל, ועדת חברה יכולה להיות {עידן, נעה, מעיין, טל}, ועדת קישוט יכולה להיות {יובל, טל}, וועדת ספורט יכולה להיות {נילי, אלי, גל, סיגי}. הקבוצה A, המורכבת מכל הוועדות בכיתה, היא הקבוצה שאיבריה הם שלוש קבוצות:

{{עידן, נעה, מעיין, טל}, {יובל, טל}, {נילי, אלי, גל, סיגי}} = A.

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

את הימצאותו של איבר מסוים בקבוצה מסמנים באמצעות התו ∋, ואת היעדרו של איבר מסוים מהקבוצה מסמנים באמצעות התו ∌. למשל, את חברותו של עידן בוועדת חברה נסמן {עידן, נעה, מעיין, טל} ∋ עידן, ואת היעדרה של נילי מוועדת חברה נסמן {עידן, נעה, מעיין, טל} ∌ נילי.

תרגיל 1: באמצעות רישום האיברים בעזרת הסימון {...}, יַצגו את הקבוצות האלה:

1. קבוצת המספרים הטבעיים בין 1 ל-6 (כולל שניהם)

2. קבוצת המספרים הטבעיים בין 0 ל-15 המתחלקים ב-2 אך לא ב-3

3. קבוצת נשיאי ישראל בין השנים 1948–1980

2.2 פעולות על קבוצות

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

איחוד של קבוצות

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

למשל, האיחוד של הקבוצות {1,2} ו-{1,3,4} הוא {1,2,3,4}. את האיחוד של הקבוצות A ו-B נסמן ב-A∪B. אם נציג את שתי הקבוצות האלה בצורה של רשימת איברים בתוך אליפסה (ראו תרשים 2), האיחוד יהיה רשימת המספרים הנמצאים בתוך האליפסות. נשים לב שהאיבר 1, המופיע בשתי הקבוצות, נרשם בחיתוך בין שתי האליפסות.

תרשים 2: איחוד בין קבוצות

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

חיתוך של קבוצות

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

לדוגמה, החיתוך של הקבוצות {1,2} ו-{1,3,4} הוא {1}. את החיתוך של הקבוצות A ו-B נסמן ב-B∩A. בתרשים 3 אנו מציגים את הקבוצות כרשימת איברים בתוך אליפסה, והחיתוך ביניהן מודגש בצבע צהוב.

תרשים 3: חיתוך בין קבוצות

הגדרה: שתי קבוצות שחיתוכן הוא הקבוצה הריקה נקראות קבוצות זרות.

למשל, הקבוצות {1,2,3} ו-{4,5} הן קבוצות זרות. גם קבוצת צבעי היסוד וקבוצת המספרים הטבעיים הן קבוצות זרות. הקבוצות {גילי} ו-{{גילי}} אף הן זרות, וזאת משום שהקבוצה {גילי} מכילה איבר בודד, גילי, בעוד שהקבוצה {{גילי}} אינה מכילה את האיבר גילי אלא את הקבוצה שמכילה את האיבר גילי.

הפרש של קבוצות

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

לדוגמה, ההפרש בין הקבוצה {1,3,4} לקבוצה {1,2} הוא הקבוצה {3,4}. את ההפרש בין A ל-B נסמן ב-A \ B. בתרשים 4 אנו מציגים את הקבוצות כרשימת איברים בתוך אליפסה, וההפרש ביניהן מודגש בצבע צהוב.

תרשים 4: הפרש בין קבוצות

תרגיל 2: רשמו את האיברים של קבוצות אלה:

1. {גילי, יניב, {אלה, יניב}}

2. {גילי, {גילי}, {{גילי}}, {{{גילי}}}}

3. {גילי, רוני, {גילי, {רוני}}}

4. {{גילי, רוני}, {{גילי}, {רוני}}, {{גילי}}}

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

1. {1,2,3,4,5}∪{{4,5},1,2,3}

2. {1,2,3,4,5}∩{{4,5},1,2,3}

3. {אלה, יניב, תמי} \ {גילי, יניב, {אלה, יניב}}

4. {יניב, {אלה, יניב}} \ {גילי, יניב, {אלה, יניב}}

5. {1,2,{4,5}} ∩ ({1,3,5}∪{{4,5},2,3})

הכלה של קבוצה

הגדרה: קבוצה A מוכלת בקבוצה B אם כל איבר של הקבוצה A שייך לקבוצה B.

לדוגמה, הקבוצה {1,2,4} מוכלת בקבוצת המספרים הטבעיים, הקבוצה {נועה, אלי} מוכלת בקבוצה {נועה, גלי, אלי}, והקבוצה {אדום, כחול} מוכלת בקבוצה {אדום, כחול}. קבוצות רבות מוכלות בקבוצת המספרים הטבעיים N, למשל קבוצת המספרים הזוגיים {...,0,2,4}, הקבוצה {6} המכילה את המספר 6 בלבד, והקבוצה הריקה ø. הקבוצה {1,2,4} אינה מוכלת בקבוצה {1,2}, משום שהאיבר 4 נמצא בקבוצה {1,2,4} אך אינו נמצא בקבוצה {1,2}. הקבוצה {גילי} אינה מוכלת בקבוצה {{גילי}}, וזאת משום שהקבוצה {גילי} מכילה איבר בודד, גילי, בעוד שהקבוצה {{גילי}} אינה מכילה את האיבר גילי אלא את הקבוצה שמכילה את האיבר גילי.

את ההכלה של קבוצה A בקבוצה B נסמן ב-A⊆B, ונאמר ש-A היא תת-קבוצה של B, ש-A היא קבוצה חלקית של B או ש-B מכילה את A.

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

נשים לב שכל קבוצה מוכלת בעצמה: לכל קבוצה A מתקיים A⊆A. אם הקבוצה A מוכלת בקבוצה B אך אינה שווה לה, נכתוב BA.

הגדרה: שוויון בין קבוצות – שתי קבוצות הן שוות אם הן מכילות את אותם איברים.

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

הגדרה: הקבוצות A ו-B שוות אם הקבוצה A מוכלת בקבוצה B וכן הקבוצה B מוכלת בקבוצה A.

את השוויון בין הקבוצות A ו-B נסמן באמצעות B=A.

קבוצת התת-קבוצות

הגדרה: קבוצת התת-קבוצות של קבוצה A היא קבוצת כל הקבוצות המוכלת ב-A.

למשל, לקבוצה הריקה ø יש תת-קבוצה יחידה – הקבוצה הריקה עצמה. לכן קבוצת התת-קבוצות של הקבוצה הריקה היא הקבוצה {ø}, המכילה את הקבוצה הריקה. לקבוצה {אדום, כחול} יש ארבע תת-קבוצות: הקבוצה הריקה ø, הקבוצה {אדום}, הקבוצה {כחול} והקבוצה {אדום, כחול}.

קבוצת התת-קבוצות של הקבוצה A מסומנת ב-P(A), ונקראת קבוצת החזקה של A.

דוגמאות:

P(ø) = {ø}

P({a}) = {ø,{a}}

P({a,b}) = {ø,{a},{b},{a,b}}

P({a,b,c}) = {ø,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}

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

1. A∩B ⊆ A

2. AA∪B

3. A⊆P(A)

4. A∈P(A)

2.3 דיאגרמת וֶן

דיאגרמת וֶן היא התרשים שבו הקבוצות מוצגות כאליפסות. זוהי דרך גרפית נוחה להציג פעולות עם קבוצות – חיתוכים, איחודים והפרשים בין קבוצות. שיטת תרשימי האליפסות נקראת על שם המתמטיקאי והפילוסוף הבריטי ג'ון וֶן (John Venn, 1834–1923), אף שגם לפניו השתמשו בה.

ג'ון ון. מקור: ויקיפדיה. שימוש חופשי

דוגמה: נסמן שלוש קבוצות:

A = קבוצת המספרים הטבעיים הזוגיים

B = קבוצת המספרים הטבעיים המתחלקים ב-3

C = קבוצת המספרים הטבעיים המתחלקים ב-5

בתרשים 5 מתוארת דיאגרמת ון של שלוש הקבוצות הללו.

תרשים 5: קבוצות A, B ו-C והחיתוכים ביניהן

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

תרשים 6: דיאגרמת ון – חיתוך בין שלוש קבוצות

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

א. A ∩ B)) \ A

ב. A \ (B ∪ C)

ג. (B \ A) ∪ (B ∩ C)

ד. הראה בעזרת דיאגרמת ון ששתי הקבוצות שוות: A \ B ו-A ∩ B)) \ A.

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

משפט 1: לכל שלוש קבוצות A, B ו-C מתקיים A \ (B ∪ C) = (A \ B) ∩ (A \ C).

הוכחה: בדיאגרמות ון המוצגות הדגשנו את הקבוצות (A \ B) ,A \ (B ∪ C) ו-(A \ C). קל להשתכנע כי אכן החיתוך של שתי הקבוצות (A \ B) ו-(A \ C) שווה לקבוצה (A \ (B ∪ C.

תרגיל 6: הוכיחו שלכל שלוש קבוצות A, B ו-C מתקיים:

A \ (B ∩ C) = (A \ B) ∪ (A \ C).

2.4 גודל של קבוצה סופית

הגדרה: גודל של קבוצה סופית הוא מספר האיברים שבה.

לדוגמה, הגודל של קבוצת צבעי היסוד הוא 3, והגודל של הקבוצה הריקה הוא 0.

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

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

ב) אפשר גם לספור כמה איברים יש בכל קבוצה ולהשוות את המספרים שקיבלנו.

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

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

את מספר האיברים בקבוצה הסופית A נסמן ב-|A|.

למשל, |{1,2,3}| = 3, 2 = |{רינה, עידן}|, 1 = |{{רינה, עידן}}| ו- 0 = |ø|. הקבוצה {ø} מכילה איבר אחד – הקבוצה הריקה. לכן 1 = |{ø}|. כזכור, הקבוצה N היא קבוצת המספרים הטבעיים. אף שקבוצה זו היא קבוצה אין-סופית, הרי הקבוצה {N} מכילה איבר אחד בלבד, את קבוצת המספרים הטבעיים. לכן |{N}|=1.

תרגיל 7: מהו |{ø, {ø,{ø}}, {{ø}}}|?

בעמוד 11 ראינו את קבוצת החזקה P(A) כאשר הקבוצה A מכילה 0, 1, 2, או 3 איברים. נרשום את קבוצות החזקה הללו שנית בטבלה שבתרשים 7.

תרשים 7: קבוצת החזקה עבור קבוצות A המכילות לכל היותר שלושה איברים

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

משפט 2: תהי A קבוצה סופית. גודל קבוצת החזקה של קבוצה סופית A הוא 2 בחזקת גודל הקבוצה A, כלומר |P(A)| = 2|A|.

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

מכיוון שמספר האיברים בקבוצה A הוא |A|, בעת בניית התת-קבוצה עלינו להחליט |A| החלטות, ובכל נקודת החלטה יש שתי אפשרויות: להוסיף את האיבר לתת-קבוצה שאנחנו בונים או לא להוסיף אותו. כל סדרת החלטות שנערוך תיצור תת-קבוצה אחרת של A (ראו תרשים 8 לעץ החלטות עבור קבוצה A המכילה 3 איברים). מספר סדרות ההחלטות האפשריות הוא 2 × 2 × ... × 2 (|A| פעמים), ולכן מספר התת-קבוצות שאפשר לבנות הוא 2|A|.

תרשים 8: עץ ההחלטות בעת בניית קבוצת החזקה של הקבוצה A = {a1, a2, a3}

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

1. אם A⊆B אז |A|≤|B|.

2. |A∪B| = |A|+|B|.

3. |A \ B| = |A|-|B|.

4. |A| + |B| = |A∪B| + |A∩B|.

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

3. אין-סופים גדולים וגדולים יותר

אין-סוף הוא המקום שבו קורים דברים שאינם קורים.

(סטודנט אלמוני)

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

3.1 שוויון בין קבוצות

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

גיאורג קנטור (Georg Kantor, 1845–1918) היה מתמטיקאי מהעיר האלה (Halle) בצפון-מזרח גרמניה. קנטור חקר קבוצות אין-סופיות, והיה הראשון שהבין לאשורם מושגים בסיסיים כמו "מספר", מתי קבוצה אחת גדולה מקבוצה אחרת ומתי הן שוות בגודלן. קנטור הבין שיש יותר מסוג אחד של אין-סוף: יש אין-סופים גדולים ויש אין-סופים גדולים יותר.

גיאורג קנטור. מקור: ויקיפדיה. שימוש חופשי

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

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

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

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

תרשים 9: התאמה אחד לאחד בין שתי קבוצות, הממצה את שתיהן

בתרשים 10 מוצגות שתי קבוצות שגודלן שונה, ואין ביניהן התאמה אחד לאחד הממצה את שתיהן.

תרשים 10: שתי קבוצות ללא התאמה אחד לאחד ביניהן הממצה את שתיהן;

העציצים שנותרו ללא התאמה מסומנים באדום.

את ההגדרה של שוויון בגודל של קבוצות אפשר להפעיל גם על קבוצות אין-סופיות. הקבוצה הפשוטה ביותר המכילה אין-סוף איברים היא קבוצת המספרים הטבעיים {0, 1, 2, 3, 4, ...}. כאשר הקבוצות A ו-B שוות, ברור שהן בעלות אותו גודל, ואפשר למצוא התאמה אחד לאחד ביניהן, הממצה את שתיהן: לכל איבר בקבוצה A נתאים את העותק שלו בקבוצה B. בתרשים 11, הקבוצה A היא קבוצת המספרים הטבעיים, הקבוצה B אף היא קבוצת המספרים הטבעיים, ובהתאמה בין שתי הקבוצות כל מספר מתאים לעצמו.

תרשים 11: התאמה אחד לאחד בין שתי קבוצות המספרים הטבעיים A ו-B, הממצה את שתיהן

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

תרשים 12: התאמה אחד לאחד בין קבוצת המספרים הטבעיים לקבוצת המספרים השלמים, הממצה את שתיהן

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

תרשים 13: התאמה אחד לאחד בין שתי קבוצות המספרים הטבעיים A ו-B, שאינה ממצה את שתיהן

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

3.2 הפתעה

מתמטיקה לא מבינים. למתמטיקה מתרגלים.

(ג'ון פון נוימן, מתמטיקאי הונגרי-אמריקני)

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

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

נכון או לא? רק חלקית. אכן, יש פי שניים מספרים טבעיים מאשר מספרים זוגיים, אבל במקרה של האין-סוף, "פי שניים" אין פירושו "יותר". למרבה ההפתעה, שתי הקבוצות בכל זאת שוות בגודלן! איך מראים זאת? באמצעות התאמה, ממש כפי שכדי להראות שבשתי הידיים שלנו יש אותו מספר אצבעות נצמיד כף אל כף. לכל מספר טבעי נתאים מספר זוגי בדרך זו: למספר 0 נתאים את עצמו; למספר 1 נתאים את 2; ל-2 נתאים את 4; ל-3 נתאים את 6; ל-4 נתאים את 8 וכן הלאה. קיצורו של דבר, לכל מספר טבעי נתאים את כפולתו ב-2. זוהי התאמה בין המספרים הטבעיים למספרים הזוגיים, שבה לכל מספר זוגי מתאים בדיוק מספר טבעי אחד. ההתאמה מודגמת בתרשים 14. בשורה התחתונה כתבנו בכוונה את כל המספרים, ובכללם האי-זוגיים, כדי להדגיש שההתאמה היא מקבוצה (קבוצת כל המספרים הטבעיים) לקבוצה חלקית לה ממש (הזוגיים).

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

הסופר לורנס סטרן (Laurence Sterne; 1713–1768) כתב ספר שגיבורו, אדם ששמו טריסטרם שנדי, עסוק בכתיבת קורות חייו. הגיבור מפרט בתיאורים עד כדי כך שלוקח לו יום אחד לתאר את האירועים שקרו לו במשך שעה אחת מימי חייו (הניסוח בספר קצת שונה, אבל זהו הרעיון). האם אי פעם יסיים את כתיבת הספר? אם אורך ימיו סופי, כי אז ודאי שלא. אבל אם יחיה אין-סוף זמן, יספיק לכתוב את כל קורותיו. לכל שעה יגיע בשלב כלשהו – את השעה הראשונה יתאר ביום הראשון לכתיבה, את השעה ה-25 (שהיא השעה הראשונה ביום השני) יתאר ביום הכתיבה ה-25 שלו, ואת השעה החמישית ביום ה-1,001 יתאר ביום הכתיבה ה-24,005. לטריסטרם שנדי יש סיבה לרצות לחיות עד אין-סוף, מלבד הסיבות שיש לכולנו. בשפה של תורת הקבוצות, בנינו התאמה אחד לאחד בין קבוצת הימים שבהם חי טריסטרם שנדי לקבוצת השעות שבהן הוא חי, התאמה הממצה את שתי הקבוצות, ולכן שתי קבוצות אלה הן שוות-גודל.

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

במלון של הילברט יש אין-סוף חדרים, והם ממוספרים 1, 2, 3, 4 וכן הלאה. באחד הימים התמלאו כל החדרים במלון. והנה לעת ערב הגיע אורח נוסף. לו היה המלון סופי, היה האורח החדש נשאר לישון בחוץ. אבל לא כן במלון אין-סופי. בעל המלון השתמש במערכת כריזה כדי להודיע לאורחים: "כל אורח יעבור לחדר הבא" – כלומר, האורח בחדר מספר 1 יעבור לחדר מספר 2, האורח בחדר מספר 2 יעבור לחדר מספר 3, וכך כל האורחים האחרים. לכל אורח יש עכשיו חדר משלו, וחדר מספר 1 התפנה לאורח החדש.

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

תרשים 15: התאמה אחד לאחד בין קבוצת האורחים לקבוצת החדרים במלון של הילברט

גם למחרת התמלא המלון כולו. אולם בשעת ערב קרה דבר מדאיג עוד יותר: הפעם הופיעו אין-סוף אורחים! גם הפעם בעל המלון לא התרגש. הוא ציווה על כל אחד מאורחיו לעבור לחדר שמספרו כפול ממספר החדר הקודם שבו לן: האורח בחדר מספר 1 יעבור לחדר מספר 2, האורח בחדר מספר 2 לחדר מספר 4, האורח בחדר 3 יעבור לחדר 6 וכן הלאה. כך יש לכל אורח חדר משלו, והתפנו אין-סוף חדרים – החדרים שמספריהם 1, 3, 5, … באלו אפשר לשכן את אין-סוף האורחים החדשים.

נקרא לקבוצת האורחים המקוריים {א1, א2, א3, ...}, לקבוצת האורחים החדשים {אח1, אח2, אח3, ...} ולקבוצת החדרים {ח1, ח2, ח3, ...}. קבוצת האורחים הכללית היא, אם כן, {א1, א2, א3, ..., אח1, אח2, אח3, ...}. בשפה של תורת הקבוצות, בעל המלון מצא התאמה אחד לאחד בין הקבוצה {א1, א2, א3, ..., אח1, אח2, אח3, ...} לקבוצה {ח1, ח2, ח3, ...} באופן הממצה את קבוצת החדרים. ראו את ההתאמה בתרשים 16.

תרשים 16: התאמה אחד לאחד בין קבוצת האורחים לקבוצת החדרים כאשר יש אין-סוף אורחים חדשים

דויד הילברט (David Hilbert, 1862–1943), היה המתמטיקאי המשפיע ביותר בסוף המאה התשע-עשרה ובראשית המאה העשרים, ותרם לתחומים מתמטיים רבים. הילברט התאהב בתורת הקבוצות וכדי להמחיש את המושג אין-סוף המציא את סיפור המלון. "מגן העדן של קנטור", כך אמר, "איש לא יגרשנו". אחת מתרומותיו של הילברט הייתה ביסוס המתמטיקה על אקסיומות והניסיון לבדוק את נכונותם של כל המשפטים מאקסיומות אלה.

תרגיל 9: רשמו התאמה אחד לאחד בין הקבוצה האין-סופית {0, 5, 10, 15, 20, ...} לבין הקבוצה האין-סופית {3, 7, 11, 15, 19, ...}, הממצה את שתי הקבוצות.

3.3 מה פירוש "למנות"

מְנֵה אוֹתָם

אַתָּה יָכוֹל לִמְנוֹת אוֹתָם. הֵם

אֵינָם כַּחוֹל אֲשֶׁר עַל שְׂפַת הַיָּם. הֵם

אֵינָם כַּכּוֹכָבִים לָרוֹב. הֵם כַּאֲנָשִׁים בּוֹדְדִים.

(יהודה עמיחי, מנה אותם, בכל חומרת הרחמים)2

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

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

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

תחילה נעשה לעצמנו הנחה: נמנה רק את השברים החיוביים, כלומר לא נכלול במנייה את 0 ואת השברים השליליים. לשם כך נרשום את השברים החיוביים בטבלה (ראו תרשים 17).

תרשים 17: השברים החיוביים מסודרים בטבלה

בטבלה שבתרשים 17, השברים שהמונה שלהם הוא 1 מסודרים בשורה התחתונה, השברים שהמונה שלהם הוא 2 מסודרים מעליה וכן הלאה. מחקנו מהטבלה את השברים הכפולים; למשל, מהשורה השנייה מחקנו את ששווה ל-, את ששווה ל- וכדומה. למעשה אנחנו מוחקים מהטבלה את כל השברים שלמכנה ולמונה שלהם יש מחלק משותף.

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

תרשים 18: כל השברים החיוביים

תרשים 19: סידור השברים החיוביים

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

תרשים 20: סידור קבוצת השברים כולה

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

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

3.4 השוואה בין קבוצות

השוואה היא בריון ששודד לנו את האושר.

אן ווסקמפ

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

תרשים 22: קבוצת הפרחים גדולה מקבוצת העציצים או שווה לה

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

הנה אפוא ההגדרה.

הגדרה: קבוצה A תהיה גדולה מקבוצה B או שווה לה אם יש התאמה בין איברי קבוצה A לאיברי קבוצה B, הכוללת – או "מכסה" – את כל איברי קבוצה B. כלומר, לכל איבר בקבוצה B יש איבר מתאים בקבוצה A.

שימו לב: לכל איבר בקבוצה A מותאם בדיוק איבר אחד, ולכל איבר בקבוצה B מותאם לפחות איבר אחד.

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

תרגיל 11: הראו שקבוצת המספרים הממשיים גדולה מקבוצת המספרים השלמים או שווה לה.

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

משפט 3: אם קבוצה A גדולה מקבוצה B או שווה לה וכן קבוצה B גדולה מקבוצה A או שווה לה,
אזי שתי הקבוצות שוות בגודלן.

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

תרשים 23: התאמה אחד לאחד בין איברי קבוצה A לאיברי קבוצה B, המכסה את איברי קבוצה B

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

תרשים 24: התאמה אחד לאחד בין הקבוצות B ו-A, המכסה את איברי קבוצה A

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

נדמיין שלכל איבר בקבוצה A ולכל איבר בקבוצה B יש שתי ידיים, ימנית ושמאלית. בידו הימנית יאחז כל איבר בקבוצה A את ידו השמאלית של האיבר בקבוצה B שלו הותאם בתרשים 24. לדוגמה, בידו הימנית יאחז האיבר a0 את ידו השמאלית של האיבר b0, בידו הימנית יאחז האיבר a1 את ידו השמאלית של האיבר b1, ובידו הימנית יאחז האיבר a2 את ידו השמאלית של האיבר b4.

באותו אופן, כל איבר בקבוצה B יאחז בידו הימנית את ידו השמאלית של האיבר בקבוצה A שלו הותאם בתרשים 23. לדוגמה, בידו הימנית יאחז האיבר b0 את ידו השמאלית של האיבר a1, בידו הימנית יאחז האיבר b1 את ידו השמאלית של האיבר a0, ובידו הימנית יאחז האיבר b2 את ידו השמאלית של האיבר a4.

נסדר עתה את האיברים של הקבוצות A ו-B בשרשראות בהתאם לאחיזת הידיים שלהם. האיבר a0 אוחז את b0 (ראו תרשים 24) שאוחז את a1 (ראו תרשים 23) שאוחז את b1 (ראו תרשים 24) שאוחז את a0 (ראו תרשים 23). קיבלנו שרשרת באורך ארבע:

a0 ↔ b0 ↔ b1 ↔ a1

האיבר a2 אוחז את b4 שאוחז את a6 שאוחז את b8 שאוחז את a10 שאוחז את b12 שאוחז את a14 וכן הלאה. נשים לב שאף איבר מקבוצה B אינו אוחז את ידו השמאלית של a2. קיבלנו אם כן שרשרת אין-סופית שמתחילה ב-a2:

↔ b12 ↔ a14 ... b8 ↔ a10 ↔ a6 ↔ b4 ↔ a2

האיבר b2 אוחז את a4 שאוחז את b6 שאוחז את a8 שאוחז את b10 שאוחז את a12 שאוחז את b14 וכן הלאה. נשים לב שאף איבר מקבוצה A אינו אוחז את ידו השמאלית של b2. קיבלנו אם כן שרשרת אין-סופית שמתחילה ב-b2:

... b14 ↔ a12 ↔ a8 ↔ b10 ↔ b6 ↔ a4 ↔ b2

נשים לב שיש שרשרת אין-סופית נוספת, ללא התחלה וללא סוף: בידו הימנית אוחז האיבר a3 באיבר b5 שאוחז את a7 שאוחז את b9 שאוחז את a10 שאוחז את b12 שאוחז את a14 וכן הלאה. מצד שני, בידו השמאלית אוחז האיבר a3 באיבר b3 שאוחז את a5 שאוחז את b7 שאוחז את a9 שאוחז את b11 שאוחז את a13 וכן הלאה. קיבלנו אם כן שרשרת זו:

b13 ... ↔ a11 ↔ b9 ↔a7 ↔ b5 ↔ a3 ↔ b3 ↔ a5 ↔ b7 ↔ a9 ↔ ↔ b11 a13 ...

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

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

בשרשרת אין-סופית משני הכיוונים, נבחר שני איברים צמודים בשרשרת, נאמר b5 ו-a7, ונתאים אותם זה לזה. כעת נתאים את הזוגות שמימינם, למשל נתאים את b9 ל-a11, את b11 ל-a13 וכן הלאה, ונתאים את הזוגות שמשמאלם, למשל את a3 ל-b3, את a5 ו-b7 וכן הלאה.

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

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

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

תרשים 25: התאמה אחד לאחד בין הקבוצות A ו-B, הממצה את שתיהן

3.5 אי-שוויון בין קבוצות

כל החיות שוות, אבל יש כאלה ששוות יותר.

ג'ורג' אורוול, חוות החיות

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

הגדרה: קבוצה A גדולה מקבוצה B אם קבוצה A גדולה מקבוצה B או שווה לה, אבל לא להפך. כלומר, קבוצה B אינה גדולה מקבוצה A או שווה לה.

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

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

משפט 4: אין קבוצה גדולה ביותר. לכל קבוצה יש קבוצה גדולה ממנה.

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

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

משפט 5: במשחק מר תפוח אדמה יש יותר דמויות מאביזרים.

למשל, אם ברשותנו 0 אביזרים, יש רק דמות אחת – זו שאין בה אביזר כלשהו. אם כן, מספר הדמויות, 1, גדול ממספר האביזרים, 0.

אם יש אביזר אחד, יש שתי אפשרויות – להשתמש בו או לא להשתמש. אם כן, יש שתי דמויות. גם כאן מספר הדמויות, 2, גדול ממספר האביזרים, 1.

אם יש 2 אביזרים, נאמר אף וכובע, יש 4 דמויות: עם אף ועם כובע, עם אף ובלי כובע, בלי אף ועם כובע, בלי אף ובלי כובע. ואכן, 4 גדול מ-2.

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

כל אביזר מגדיל את מספר הדמויות האפשריות פי 2. לפיכך, אם יש n אביזרים, יש 2n (2 בחזקת n) דמויות אפשריות. ו-2n גדול מ-n.

את המשפט של קנטור אפשר לכתוב כך:

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

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

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

תרשים 26: התחלה של התאמה אחד לאחד בין קבוצת האביזרים לקבוצת הדמויות

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

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

עכשיו אנחנו מבינים מניין נטלה דווקא את שמה. מה שחשוב לנו הוא שדווקא אינה זהה לדמות שהמוכר התאים לאף. הרי היא שונה ממנה בעניין האף, ושתי דמויות ששונות ולוּ באביזר אחד אינן אותה דמות.

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

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

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

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

מכאן קצרה הדרך למשפט שהזכרנו קודם:

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

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

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

משפט 8: קבוצת הקבוצות החלקיות של קבוצה כלשהי גדולה מן הקבוצה עצמה.

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

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

משפט 9: קבוצת המספרים הממשיים גדולה מקבוצת המספרים הטבעיים.

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

משפט 10: קבוצת המספרים הממשיים אינה בת מנייה.

המשמעות היא שאי אפשר למנות את כל המספרים הממשיים כך: מספר ממשי ראשון, מספר ממשי שני, מספר ממשי שלישי וכן הלאה. המספרים האלה רבים מדי. קנטור הוכיח אפילו יותר מזה: הוא הצביע על תת-קבוצה מסוימת של המספרים הממשיים הכוללת רק חלק קטן מהם – המספרים שבפיתוחם העשרוני מופיע 0 לפני הנקודה והספרות בהם הן רק 0 ו-1, כלומר מספרים כמו 0.111…, 0.010101… או 0.101001000… – והראה שכבר אותם אי אפשר למנות. אם נַראה שכבר את המספרים האלו אי אפשר למנות, כלומר לסדר את כולם כ"מספר ראשון", "מספר שני" וכן הלאה, על אחת כמה וכמה אי אפשר למנות את כל המספרים הממשיים כולם, המכילים גם מספרים שבפיתוח העשרוני מופיעות הספרות 2, 3, ..., 9.

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

משפט 11: אי אפשר למנות את קבוצת הסדרות של הספרות 0 ו-1.

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

S1=0,0,0,0,0,0,0,…

S2=1,1,1,1,1,1,1,…

S3=0,1,0,1,0,1,0,…

S4=0,0,1,1,0,0,1,…

S5=1,0,1,1,0,1,1,…

S6=1,0,1,0,1,0,1,…

S7=0,0,0,1,1,1,0,…

.

.

.

תרשים 27: מנייה של קבוצת הסדרות שאיבריהן הם הספרות 0 ו-1

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

S1=0,0,0,0,0,0,0,…

S2=1,1,1,1,1,1,1,…

S3=0,1,0,1,0,1,0,…

S4=0,0,1,1,0,0,1,…

S5=1,0,1,1,0,1,1,…

S6=1,0,1,0,1,0,1,…

S7=0,0,0,1,1,1,0,…

.

.

.

תרשים 28: איברי האלכסון במנייה

נכתוב את הסדרה המופיעה באלכסון: 0,1,0,1,0,0,0,… ונהפוך בה כל 0 ל-1 וכל 1 ל-0. נקבל את הסדרה: D=1,0,1,0,1,1,1,…. D מציין "דווקא", כי D מתנהגת באורח דווקאי בנוגע לאלכסון. נַראה עתה שהסדרה D אינה זהה לאף אחת מן הסדרות המופיעות ברשימה שבתרשים 27, בניגוד להנחה שהצלחנו למנות את כל הסדרות בעולם.

מדוע הסדרה D אינה מופיעה ברשימה שבתרשים 27? משום שהיא "דווקאית". היא הקפידה להיות שונה מכל איבר בסדרה: היא שונה מהסדרה S1 באיבר הראשון שלה – הרי כך בחרנו אותה, הפוכה מ-S1 באיבר זה. לכן היא לא יכולה להיות זהה ל-S1. היא לא יכולה להיות זהה לסדרה S2, משום שהיא שונה מ-S2 במקום השני – כך הגדרנו אותה, המקום השני בה הפוך מן המקום השני ב-S2. היא שונה מהסדרה S3 במקום השלישי, לכן היא אינה זהה לסדרה S3, וכן הלאה. לכל מספר טבעי i, הסדרה D שונה מן הסדרה Si במקום ה-i. אם כן, D שונה מכל הסדרות Si ואינה מופיעה ברשימת הסדרות שלנו, רשימה שבה היו אמורות להופיע כל הסדרות בעולם!

למעשה, הוכחת מר תפוח אדמה – שמראה שיש יותר תת-קבוצות מאיברים – היא הכללה של ההוכחה הזאת. הסיבה לכך היא שקבוצת המספרים הממשיים שצורתם 0.10010001…, כלומר שבפיתוחם העשרוני יש 0 לפני הנקודה העשרונית ואחריה רק סדרה של הספרות 0 ו-1, שקולה לקבוצת תת-הקבוצות של המספרים הטבעיים. לכל מספר מן הצורה הזאת נתאים את תת-הקבוצה של המספרים הטבעיים שבה כלולים בדיוק האיברים n שבמקום ה-n-י במספר מופיע 1. למשל, למספר 0.1010101… מתאימה קבוצת המספרים הזוגיים (זכרו שהמספר הטבעי הראשון הוא 0), למספר 0.010101… מתאימה קבוצת המספרים האי-זוגיים, למספר 0.1111… מתאימה קבוצת כל המספרים הטבעיים, למספר 0.01010010001… מתאימה הקבוצה {1,3,6,10…}. ואם תבדקו את הוכחת האלכסון מקרוב, תראו שהיא יוצרת בדיוק את הדמות "דווקא" שפגשנו בהוכחה של משפט 5!

3.7 הפרדוקס של קנטור

העולם הוא מקום לא פשוט

נעמי שמר, השיר "סיירת לעולם"

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

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

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

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

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

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

לגזור או לא לגזור?

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

3.8 איך בונים קבוצות

כולנו בונים את העולם שלנו, ברגע זה ממש, בזמן אמת. בואו נבנה אותו טוב יותר.

לינדי ווסט, "צווחה: הערות מאישה קולנית"

כפי שאמרנו בסעיף 3.7, הפתרון של קנטור לפרדוקס הוא שהקבוצה W המכילה את כל הדברים בעולם אינה קבוצה. מכאן עולה השאלה, – מהי היא קבוצה? האם קבוצת כל גרגירי החול היא קבוצה? וקבוצת כל הכוכבים ביקום? וקבוצת כל התת-קבוצות של קבוצת הכוכבים ביקום? וקבוצת כל היקומים האפשריים? המתמטיקאי הגרמני ארנסט צרמלו (Ernst Zermelo, 1871–1953) בנה מערכת של כללים, הנקראים אקסיומות, המאפשרת לבנות את אוסף כל הקבוצות מבלי להגיע לפרדוקס. המתמטיקאי היהודי אברהם פרנקל (Abraham Fraenkel, 1891–1965) הוסיף למערכת של צרמלו אקסיומה שצרמלו לא שם לב לנחיצותה, והמערכת הזאת נקראת כיום על שם שניהם, צרמלו-פרנקל (ZF).

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

אַקְסְיוֹמָה היא הנחה שמקבלים אותה כנכונה. מקור המילה אקסיומה מיוונית (αξιωμα) ופירושה "עיקרון מובן מאליו". במתמטיקה, כאשר מפתחים תורה מסוימת, רושמים רשימה של אקסיומות ומתוכן מוכיחים את כל המשפטים של התורה.

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

האקסיומה הראשונה של צרמלו היא שיש קבוצה שאינה מכילה אף איבר, כלומר הקבוצה הריקה:

אקסיומה 1: קיימת קבוצה ריקה ø.

האקסיומה השנייה מאפשרת לבנות אין-סוף קבוצות:

אקסיומה 2: לכל קבוצה יש קבוצה שמכילה אותה כאיבר יחיד.

מאקסיומה 1 נקבל כי ø היא קבוצה, ומאקסיומה 2 נובע שגם {ø} היא קבוצה. זוהי הקבוצה שיש לה איבר יחיד – הקבוצה הריקה. שימוש נוסף באקסיומה 2 יראה שגם {{ø}} היא קבוצה. זוהי הקבוצה שמכילה איבר יחיד – הקבוצה שמכילה את הקבוצה הריקה.

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

אקסיומה 3: האיחוד של שתי קבוצות הוא קבוצה.

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

0 = ø

1 = {ø}

2 = {ø,{ø}} = {0,1}

3 = {ø,{ø}, {ø,{ø}}} = {0,1,2}

וכן הלאה.

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

ג'ון פון נוימן (John von Neumann, 1903–1957) היה מתמטיקאי ממשפחה יהודית שנולד בהונגריה והיגר לארצות הברית בשנת 1930. הוא השתתף בפיתוח פצצת האטום הראשונה ופצצת המימן, היה מעורב בתוכנית הטילים הבין-יבשתיים האמריקנית ונחשב לאביה של תורת המשחקים.

ג'ון פון נוימן. מקור: ויקיפדיה. נחלת הכלל

תרגיל 12: רשמו את המספר 5 בכתיב של פון-נוימן.

תרגיל 13: מהו האיחוד של הקבוצות 2 ו-1?

תרגיל 14: מהו האיחוד של הקבוצות 3 ו-5?

האקסיומה הרביעית מדברת על קיומה של קבוצה אין-סופית.

אקסיומה 4: קיימת קבוצה S שאחד מאיבריה הוא הקבוצה הריקה,

ולכל איבר x ב-S, גם הקבוצה x∪{x} נמצאת ב-S .

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

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

4. סיכום

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

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

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

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

5. פתרונות לתרגילים

תרגיל 1: יַצגו באמצעות רישום האיברים (בעזרת הסימון {...}) את הקבוצות האלה:

1. קבוצת המספרים הטבעיים בין 1 ל-6 (כולל שניהם): {1,2,3,4,5,6}.

2. קבוצת המספרים הטבעיים בין 0 ל-15 המתחלקים ב-2 אך לא ב-3: {2,4,8,10,14}.

3. קבוצת נשיאי ישראל בין השנים 1948-1980: {חיים וייצמן, יצחק בן צבי, זלמן שזר, אפרים קציר, יצחק נבון}.

תרגיל 2: רשמו את האיברים של קבוצות אלה:

1 {גילי, יניב, {אלה, יניב}}.

תשובה: הקבוצה מכילה שלושה איברים: גילי, יניב, {אלה, יניב}. כלומר, אחד האיברים בקבוצה הוא הקבוצה שמכילה את אלה ויניב.

2. {גילי, {גילי}, {{גילי}}, {{{גילי}}}}.

תשובה: הקבוצה מכילה ארבעה איברים: גילי, {גילי}, {{גילי}}, {{{גילי}}}. כלומר, הקבוצה מכילה את האיבר גילי, את הקבוצה שמכילה את האיבר גילי, את הקבוצה שמכילה את הקבוצה שמכילה את האיבר גילי, ואת הקבוצה שמכילה את הקבוצה שמכילה את הקבוצה שמכילה את האיבר גילי.

3. {גילי, רוני, {גילי, {רוני}}}

תשובה: הקבוצה מכילה שלושה איברים: גילי, רוני, והקבוצה {גילי, {רוני}}.

4. {{גילי, רוני}, {{גילי}, {רוני}}, {{גילי}}}

תשובה: הקבוצה מכילה שלושה איברים, שכל אחד מהם הוא קבוצה: {גילי, רוני}, {{גילי}, {רוני}}, {{גילי}}.

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

תשובה:

1. {1,2,3,4,5}∪{{4,5},1,2,3} = {{4,5},4,51,2,3}.

2. {1,2,3,4,5}∩{{4,5},1,2,3} = {1,2,3}.

3. {אלה, יניב, תמי} \ {גילי, יניב, {אלה, יניב}} = {גילי, {אלה, יניב}}.

4. {יניב, {אלה, יניב}} \ {גילי, יניב, {אלה, יניב}} = {גילי}.

5. {1,2,{4,5}}∩({1,3,5}∪{{4,5},2,3}) = {1,2,{4,5}}.

תרגיל 4: בדקו כל אחת מהטענות וכתבו אם היא נכונה או לא. אם הטענה נכונה, נמקו. אם הטענה אינה נכונה, תנו דוגמה שמראה שהיא אינה נכונה.

תשובה:

1. A∩B⊆A

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

2. AA∪B

הטענה אינה נכונה בהכרח: כל איבר בקבוצה A נמצא בקבוצה A∪B, אך ייתכן ששתי הקבוצות שוות. הדבר קורה למשל כאשר A=B.

3. A⊆P(A)

הטענה אינה נכונה: P(A) היא קבוצה שכל איבריה הם קבוצות – הקבוצות החלקיות של A, בעוד ש-A היא קבוצה של איברים. למשל, אם A = {1}, אז P(A) = { ø ,{1}}. האיבר 1 נמצא ב-A, אך לא ב-P(A).

4. A∈P(A)

הטענה נכונה. קבוצת החזקה P(A) מכילה את כל התת-קבוצות של A, ו-A היא אחת מתת-הקבוצות של A.

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

תשובה:

א. (A ∩ B) \ A: בתרשים מימין מופיעה הקבוצה A ∩ B, ובתרשים משמאל הקבוצה (A ∩ B) \ A:

ב. A \ (B ∪ C): בתרשים מימין מופיעה הקבוצה B ∪ C, ובתרשים משמאל הקבוצה (B ∪ C) \ A:

ג. (B \ A) ∪ (B ∩ C):

ד. הראה בעזרת דיאגרמת ון ששתי הקבוצות שוות: A \ B ו- (A ∩ B) \ A.

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

תרגיל 6: הוכיחו שלכל שלוש קבוצות A, B ו-C מתקיים:

A \ (B ∩ C) = (A \ B) ∪ (A \ C).

תשובה: נדגיש בדיאגרמת ון את שלוש הקבוצות A \ (B ∩ C) ,(A \ B) ו-(A \ C). קל להשתכנע כי אכן האיחוד של שתי הקבוצות (A \ B) ו-(A \ C) שווה לקבוצה A \ (B ∩ C).

תרגיל 7: מהו |{ø, {ø,{ø}}, {{ø}}}|?

תשובה: הקבוצה מכילה שלושה איברים: ø, {ø,{ø}}, {{ø}}}.

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

תשובה:

1. אם A⊆B אז |A|≤|B|.

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

2. |A∪B| = |A| + |B|.

הטענה אינה נכונה: למשל, אם A = {1} וגם B={1} אז A∪B={1}, ולכן |A∪B| = 1. מנגד, |A| = 1 וכן |B| = 1, ולכן |A| + |B| = 2. הטענה נכונה אם הקבוצות A ו-B זרות, כלומר אין אפילו איבר אחד הנמצא בשתיהן, והיא אינה נכונה אם הן אינן זרות ויש איבר הנמצא בשתיהן.

3. |A\B| = |A| - |B|.

הטענה אינה נכונה: למשל, אם A = {1} ו- B = {2}, אז A\B = {1} ולכן |A\B| = 1. מנגד, |A| = 1 וכן |B| = 1, ולכן |A| - |B| = 0. הטענה נכונה רק אם הקבוצה B מוכלת בקבוצה A, והיא אינה נכונה אם אינה מוכלת.

4. |A| + |B| = |A∪B| + |A∩B|.

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

קבוצה A היא הקבוצה המכילה את האותיות האנגליות ואת המספרים. קבוצה B היא הקבוצה המכילה את האותיות העבריות ואת המספרים. החיתוך A∩B הוא קבוצת המספרים, והאיחוד A∪B הוא הקבוצה המכילה את האותיות האנגליות, את האותיות העבריות ואת המספרים.

כמה איברים יש בקבוצה A? 8 איברים: מספר האותיות האנגליות (5) ומספר המספרים (3).

כמה איברים יש בקבוצה B? 9 איברים: מספר האותיות העבריות (6) ומספר המספרים (3).

לכן הסכום |A| + |B| שווה 17: מספר האותיות האנגליות ועוד מספר האותיות העבריות ועוד פעמיים מספר המספרים, שכן המספרים נספרים פעמיים – פעם בקבוצה A ופעם בקבוצה B.

כמה איברים יש באיחוד A∪B? 41 איברים: מספר האותיות האנגליות (5), מספר האותיות העבריות (6) ומספר המספרים (3).

כמה איברים יש בחיתוך A∩B? 3 איברים, משום שהחיתוך של A ו-B כולל רק את המספרים.

לכן הסכום |A∪B| + |A∩B| אף הוא שווה 17: מספר האותיות האנגליות ועוד מספר האותיות העבריות ועוד פעמיים מספר המספרים, שכן המספרים מופיעים הן באיחוד A∪B הן בחיתוך A∩B.

תרגיל 9: רשמו התאמה אחד לאחד בין הקבוצה האין-סופית {0, 5, 10, 15, 20, ...} לבין הקבוצה האין-סופית {3, 7, 11, 15, 19, ...}, הממצה את שתי הקבוצות.

תשובה: נתאים את 0 ל-3, את 5 ל-7, את 10 ל-11 וכן הלאה. צורתו של איבר כללי בקבוצה {0, 5, 10, 15, 20, ...} היא 5n וצורתו של איבר כללי בקבוצה {3, 7, 11, 15, 19, ...} היא 3+4n. לכן ההתאמה שציינּו מתאימה מספר מהצורה 5n למספר מהצורה 3+4n, לכל n ≥ 0. דרך אחרת להציג את ההתאמה היא לומר שהמספר x בקבוצה {0, 5, 10, 15, 20, ...} מתאים ל-3+4x/5 בקבוצה {3, 7, 11, 15, 19, ...}.

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

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

תרגיל 11: הראו שקבוצת המספרים הממשיים גדולה מקבוצת המספרים השלמים או שווה לה.

תשובה: כדי להראות שקבוצת המספרים הממשיים גדולה מקבוצת המספרים השלמים או שווה לה, יש למצוא התאמה בין המספרים הממשיים למספרים השלמים, המכסה את כל המספרים השלמים. התאמה אפשרית אחת היא ההתאמה שבה לכל מספר ממשי x מותאם החלק השלם של x. למשל, למספר הממשי 2.3 נתאים את המספר השלם 2, למספר הממשי 2.3- נתאים את המספר השלם 3-, ולמספר הממשי π = 3.1415… נתאים את המספר השלם 3.

תרגיל 12: רשמו את המספר 5 בכתיב של פון-נוימן.

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

4 = {ø,{ø}, {ø,{ø}}, {ø,{ø},{ø,{ø}}}} = {0,1,2,3} ;

ולכן המספר 5 מיוצג באמצעות הקבוצה

.{0,1,2,3,4} = {ø,{ø}, {ø,{ø}}, {ø,{ø},{ø,{ø}}}, {ø,{ø}, {ø,{ø}}, {ø,{ø},{ø,{ø}}}}}

תרגיל 13: מהו האיחוד של הקבוצות 2 ו-1?

תשובה: ראינו כי

1 = {ø}

2 = {ø,{ø}} = {0,1}

לכן

1 ∪ 2 = {ø} ∪ {ø,{ø}} = {ø,{ø}} = 2

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

לכן, 2 = 1 ∪ {1}, ולכן 1 ∪ 2 = 1 ∪ 1 ∪ {1} = 1 ∪ {1} = 2.

תרגיל 14: מהו האיחוד של הקבוצות 3 ו-5?

תשובה: בהגדרה של פון נוימן, כל מספר הוא קבוצה, המתקבלת מהאיחוד של המספר הקודם לו (שהוא קבוצה) עם הקבוצה המכילה את המספר הקודם. לכן 4 = 3 ∪ {3} ו-5 = 4 ∪ {4}. מכאן נובע כי 5 = 3 ∪ {3} ∪ {4}.

לכן, 3 ∪ 5 = 3 ∪ 3 ∪ {3} ∪ {4} = 3 ∪ {3} ∪ {4} = 5.

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

לורנס סטרן, פסל: Joseph Nollekens, 1766. צילום: Stephencdickson.

רישיון: CC BY-SA 4.0

דויד הילברט. מקור: ויקיפדיה. שימוש חופשי

2 עמיחי, י' (1977). בכל חומרת הרחמים, שירים 1948–1962. ירושלים-תל אביב: שוקן, עמ' 253.