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