קבוצה בת מנייה
![]() בערך זה |
בתורת הקבוצות, קבוצה בַּת מְנִיָּה היא קבוצה שאפשר לסדר את איבריה בסדרה אינסופית (לפעמים כוללים במונח גם קבוצות סופיות). לדוגמה, קבוצת המספרים הטבעיים הזוגיים היא תת-קבוצה של המספרים הטבעיים ועוצמתה היא אינסופית, וגם קבוצת המספרים היא תת-קבוצה של המספרים הטבעיים אך עוצמתה היא סופית ושווה ל-3. שתי הקבוצות הללו הן בנות מניה.
קבוצה היא בת מנייה אם ניתן למצוא פונקציה חד-חד-ערכית ממנה אל קבוצת המספרים הטבעיים, כלומר, להתאים לכל איבר בה מספר טבעי שלא הותאם לאיבר אחר.
כל קבוצה שהיא קבוצה חלקית של הטבעיים (סופית או אינסופית), כגון קבוצת המספרים הזוגיים או קבוצת המספרים שבייצוג העשרוני שלהם מופיעה הספרה 7, היא קבוצה בת מנייה. תוצאות פחות מובנות מאליהן הן התוצאות לפיהן גם קבוצת המספרים הרציונליים וקבוצת המספרים האלגבריים הן קבוצות בנות מנייה. העוצמה של קבוצה בת מנייה אינסופית מסומנת בביטוי (אָלֶף אֶפֶס).
משפט קנטור-שרדר-ברנשטיין[עריכת קוד מקור | עריכה]
ממשפט קנטור-שרדר-ברנשטיין נובע שקבוצה אינסופית שאפשר לסדר את איבריה בסדרה (ואפילו עם חזרות) גם היא בת מנייה. למשל, אם הקבוצות ו- שתיהן בנות מנייה, אז האיחוד שלהן גם הוא בן מנייה, שהרי .
דוגמאות[עריכת קוד מקור | עריכה]
להלן הוכחת גאורג קנטור שקבוצת הזוגות של מספרים טבעיים היא בת מנייה:
נסדר את הזוגות באופן הבא; ראשית יבוא (1,1), אחריו (1,2) ו-(2,1), אחר-כך שלושת הזוגות שסכום הקואורדינטות שלהם , אחר-כך ארבעת הזוגות שסכום הקואורדינטות שלהם 5, וכן הלאה. (הזוגות שסכומם מסודרים לפי הערך של , מהקטן לגדול). הרשימה כוללת כל זוג של מספרים טבעיים, ולכן אוסף הזוגות בן מנייה. להתאמה שבהוכחה קוראים פונקציית זיווג.
מן ההוכחה הזו נובע למשל שאוסף המספרים הרציונליים (החיוביים) הוא בן מנייה: יש פונקציה מן הזוגות של מספרים טבעיים המכסה את כל המספרים הרציונליים, . העובדה שכל מספר רציונלי מתקבל יותר מפעם אחת (ולמעשה אינסוף פעמים) אינה מפריעה - אם רוצים ליצור רשימה שבה כל רציונלי יופיע פעם אחת, אפשר לדלג על זוגות שאינם זרים; או לחלופין להשתמש במשפט קנטור-שרדר-ברנשטיין.
הטיעון של קנטור מראה שכל מכפלה קרטזית של קבוצות בנות מנייה, גם היא בת מנייה. באינדוקציה נובע שאם קבוצה בת מנייה, אז לכל טבעי הקבוצה גם היא בת מנייה. יתרה מזו, גם איחוד של מספר בן מנייה של קבוצות, שכל אחת מהן בת מנייה, הוא בן מנייה.
הקבוצה היא קבוצה בת מנייה. בניסוח אחר, קבוצת כל הסדרות הסופיות של מספרים טבעיים היא בת מנייה. אלא שיש קבוצות גדולות יותר: משיטת האלכסון של קנטור יוצא שקבוצת כל הסדרות בנות המנייה של מספרים טבעיים (ואפילו של המספרים 0 ו-1) היא גדולה מכדי להיות בת מנייה. מכיוון שכך, גם קבוצת המספרים הממשיים אינה בת מנייה.
ראו גם[עריכת קוד מקור | עריכה]
קישורים חיצוניים[עריכת קוד מקור | עריכה]
- קבוצה בת מנייה, באתר MathWorld (באנגלית)
הערות שוליים[עריכת קוד מקור | עריכה]
נושאים בתורת הקבוצות | ||
---|---|---|
מושגי יסוד | תורת הקבוצות הנאיבית • תורת הקבוצות האקסיומטית • קבוצה • יחידון • הקבוצה הריקה • קבוצת החזקה | |
עוצמות | עוצמה • קבוצה בת מנייה • עוצמת הרצף | |
פעולות | איחוד • חיתוך • משלים • הפרש סימטרי • מכפלה קרטזית | |
אקסיומות | אקסיומת ההיקפיות • אקסיומת האיחוד • אקסיומת הקבוצה האינסופית • אקסיומת ההחלפה • אקסיומת קבוצת החזקה • אקסיומת היסוד • אקסיומת הבחירה • השערת הרצף | |
משפטים | האלכסון של קנטור • משפט קנטור-שרדר-ברנשטיין • הלמה של צורן • משפט הסדר הטוב | |
פונקציות | פונקציה • פונקציה חד-חד-ערכית • פונקציה על • פונקציה חד-חד-ערכית ועל • פונקציית הזיווג של קנטור | |
יחסים | יחס • יחס רפלקסיבי • יחס סימטרי • יחס טרנזיטיבי • יחס שקילות • סדר חלקי • יחס הופכי | |
סדר | סדר מלא • סדר טוב • סדר חלקי • טיפוס סדר • מספר סודר | |
שונות | הפרדוקס של ראסל |