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

From Wikiversity

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

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

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

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

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

הוכחה. לפי הטענה מסוף שעור 13, קבוצה המכילה קבוצה בת-מנייה (שהיא אינסופית) היא אינסופית בעצמה. כעת נניח ש-A אינסופית. פירושו של דבר הוא שיש פונקציה שהיא חד-חד-ערכית אבל אינה על. נסמן , ובאינדוקציה . לפי ההנחה, . נראה, באינדוקציה, שלכל n>0 מתקיים : ההכלה ברורה (משום ש- ); ואם מתקיים שוויון, אז גם שהרי f חד-חד-ערכית, וזו סתירה להנחת האינדוקציה. כעת נותר רק לבחור איבר מכל הפרש . ההפרשים זרים זה לזה (תרגיל), ולכן האיברים שונים, ותת-הקבוצה של A היא בת-מנייה.

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

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

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

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

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

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

סידור אפשרי של הזוגות בהוכחתו של גאורג קנטור


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

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

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

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

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

תרגיל. לכל n, (אינדוקציה על n).

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

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

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

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

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

טענה. אם A אינסופית ו-Z סופית או בת-מנייה, אז (כלומר, לכל עוצמה סופית n).

הוכחה. מכיוון ש-A אינסופית יש לה תת-קבוצה בת-מנייה C, ואז כי .

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







<< השיעור הקודם - אריתמטיקה של עוצמות דף הקורס - תורת הקבוצות השיעור הבא - משפט קנטור-ברנשטיין >>