קבוצות סופיות ואינסופיות

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

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

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

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

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