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

בערך זה נעשה שימוש בסימנים מוסכמים מתחום המתמטיקה. להבהרת הסימנים ראו סימון מתמטי.

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

היותה של קבוצה אינסופית ניתנת למניה היא תכונה של הגודל של הקבוצה. מושג העוצמה של קבוצות מכליל רעיון זה לקבוצות אינסופיות כלשהן. בשפה זו, מסמנים ב-$\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},...\}$, ואיננו חוששים לחזרות.

דוגמאות

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

להלן הוכחת גאורג קנטור שקבוצת הזוגות של מספרים טבעיים היא בת מנייה:

נסדר את הזוגות באופן הבא; ראשית יבוא (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) היא גדולה מכדי להיות בת מנייה. מכיוון שכך, גם קבוצת המספרים הממשיים אינה בת מנייה.

ראו גם

• הוכחת האי-מנייה הראשונה של קנטור

קישורים חיצוניים

• קבוצה בת מנייה, באתר MathWorld (באנגלית)