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

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

העוצמה של קבוצה בת מנייה מסומנת באות העברית $\aleph_0$ (אלף אפס).

ממשפט קנטור-שרדר-ברנשטיין נובע שקבוצה אינסופית שאפשר לסדר את איבריה בסדרה (ואפילו עם חזרות) גם היא בת-מנייה. למשל, אם הקבוצות $\ A=\{a_1,a_2,a_3,...\}$ ו- $\ B = \{b_1,b_2,b_3,...\}$ שתיהן בנות מנייה, אז האיחוד שלהן גם הוא בן מנייה, שהרי $\ A\cup B = \{a_1,b_1,a_2,b_2,a_3,b_3,...\}$ .

מובן שקבוצת המספרים הטבעיים $\mathbb{N}$ היא קבוצה בת מנייה. גם כל קבוצה אינסופית שהיא קבוצה חלקית של הטבעיים, כגון קבוצת המספרים הזוגיים או קבוצת המספרים שבייצוג העשרוני שלהם מופיעה הספרה 7, היא קבוצה בת מנייה. תוצאות פחות מובנות מאליהן הן התוצאות לפיהן גם קבוצת המספרים הרציונליים וקבוצת המספרים האלגבריים הן קבוצות בנות מנייה.

הנה הוכחתו של גאורג קנטור שקבוצת הזוגות של מספרים טבעיים היא בת-מנייה. נסדר את הזוגות באופן הבא: ראשית יבוא (1,1), אחריו (1,2) ו-(2,1), אחר-כך שלושת הזוגות $\,(i,j)$ שסכום הקואורדינטות שלהם $\,i+j=4$ , אחר-כך ארבעת הזוגות שסכום הקואורדינטות שלהם 5, וכן הלאה. (הזוגות $\,(i,j)$ שסכומם $\,n$ מסודרים לפי הערך של $\,i$ , מהקטן לגדול). ברור שהרשימה כוללת כל זוג של מספרים טבעיים, ולכן אוסף הזוגות בן-מנייה.

מן ההוכחה הזו נובע למשל שאוסף המספרים הרציונליים (החיוביים) הוא בן מנייה: יש פונקציה מן הזוגות של מספרים טבעיים המכסה את כל המספרים הרציונליים, $\ (i,j) \mapsto \frac{i}{j}$ . העובדה שכל מספר רציונלי מתקבל יותר מפעם אחת (ולמעשה אינסוף פעמים) אינה מפריעה - אם רוצים ליצור רשימה שבה כל רציונלי יופיע פעם אחת, אפשר לדלג על זוגות $\,(i,j)$ שאינם זרים; או לחילופין להשתמש במשפט קנטור-שרדר-ברנשטיין.

הטיעון של קנטור מראה שכל מכפלה קרטזית $A \times B$ של קבוצות בנות-מנייה, גם היא בת-מנייה. באינדוקציה נובע שאם $\,A$ קבוצה בת-מנייה, אז לכל $\,k$ טבעי הקבוצה $\ A^k$ גם היא בת-מנייה. יתרה מזו, גם איחוד של מספר בן-מנייה של קבוצות, שכל אחת מהן בת-מנייה, הוא בן מנייה.

למשל, $\cup_{k=1}^{\infty} \mathbb{N}^k$ היא קבוצה בת מנייה. בניסוח אחר, קבוצת כל הסדרות הסופיות של מספרים טבעיים היא בת-מנייה. אלא שיש קבוצות גדולות יותר: משיטת האלכסון של קנטור יוצא שקבוצת כל הסדרות בנות-המנייה של מספרים טבעיים (ואפילו של המספרים 0 ו-1) היא גדולה מכדי להיות בת-מנייה.