קבוצות בנות מנייה

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

את קבוצת כל המספרים הטבעיים מסמנים באות $\ \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|$.

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

<< השיעור הקודם - אריתמטיקה של עוצמות

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

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