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

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

בתורת הקבוצות, קבוצה בַּת מְנִיָּה היא קבוצה שקיימת פונקציה חד־חד ערכית ממנה לקבוצת המספרים הטבעיים. קבוצה בת־מנייה היא סופית, או קבוצה אינסופית שעוצמתה אָלֶף אֶפֶס ($\aleph _{0}$). על קבוצה כזו נאמר שהיא נמצאת בהתאמה לקבוצת המספרים הטבעיים. לכן, ניתן לסדר את איבריה בסדרה, ללא חזרות. לדוגמה, קבוצת המספרים הרציונליים וקבוצת המספרים האלגבריים, הן בנות־מנייה. לעומת זאת, קבוצת המספרים הממשיים היא קבוצה שאינה בת־מנייה. כל קבוצה אינסופית שאפשר לסדר את איבריה בסדרה, ואפילו עם חזרות, היא בת־מנייה (לפי משפט קנטור-שרדר-ברנשטיין). עובדה זו נדרשת בהוכחה של טענות יסודיות כמו שאיחוד קבוצות בן מנייה, גם הוא בן מנייה.

דוגמאות

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

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

נסדר את הזוגות באופן הבא; ראשית יבוא (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 (באנגלית)
• גדי אלכסנדרוביץ', תורת הקבוצות - קבוצות בנות מנייה, באתר "לא מדויק", 31 באוקטובר 2020