עוצמה של קבוצה

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

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

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

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

<< השיעור הקודם - הרכבת פונקציות

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

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