הועלה לאתר:  
מספר עמודים: 95
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

תורת הקבוצות

ספר אלקטרוני מאת: ניר אדר

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

סימון

נסמן את העוצמה של קבוצת הטבעיים plot:\[\left| \mathbb{N} \right| = {\aleph _0}\].

הגדרה

נאמר שקבוצה A היא בת מניה אם קיימת פונקציה חח"ע plot:\[f:A \to \mathbb{N}\].

הגדרה שקולה: קבוצה A היא בת מניה אם היא סופית או שגודלה הוא plot:\[{\aleph _0}\].

הערה חשובה: במקומות רבים בספרות, כולל בגירסה הקודמת של מסמך זה, קבוצה בת מניה מוגדרת כקבוצה אינסופית בלבד שגודלה plot:\[{\aleph _0}\]. עניין זה הוא עניין של מוסכמה בלבד.

קבוצה A אינסופית תיקרא בת מניה אם plot:\[\left| A \right| = {\aleph _0}\].

כיצד מוכיחים שקבוצה A אינסופית היא בת מניה?

  1. מציגים התאמה חח"ע בין plot:\[A\]לקבוצה שידוע שהיא בת מניה.
  1. מציגים פונקציה חח"ע מ-plot:\[A\] לקבוצה כלשהי בת מניה ופונקציה חח"ע מקבוצה בת מניה כלשהי לA ומשתמשים במשפט CSB (יוצג בהמשך).
  1. מציגים מניה של אברי A שמקיימת:

    א. לפני כל איבר נמצא מספר סופי של איברים.

    ב. כל איבר נמצא במקום כלשהו במניה (כל איבר נספר).



דוגמא

נטען: plot:\[\mathbb{Z}\] הינה בת מניה.

ננסה למצוא מניה. נסיון ראשון: 0,1,2,...,-1,-2,-3,....

סדר זה איננו ספירה טובה, כי לפני המספר plot:\[ - 1\] עומדים אינסוף איברים. נסיון שני:

plot:\[\begin{array}{*{20}{c}}    \mathbb{Z} & 0 & 1 & { - 1} & 2 & { - 2} & 3 & { - 3}  \\    \mathbb{N} & 0 & 1 & 2 & 3 & 4 & 5 & 6  \\ \end{array} \]

נשים לב שזוהי למעשה התאמה חד חד ערכית. בשלב ה-plot:\[k\] של המניה סופרים את plot:\[k\] ואת plot:\[ - k\].

כל איבר plot:\[x\] נספר בשלב ה-plot:\[\left| x \right|\] וכל שלב אורכו לכל היותר 2, לכן כל מספר plot:\[x \in \mathbb{Z}\] מופיע בסידרה כשלפניו מספר סופי של איברים.

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

משפט

תהינה plot:\[{A_1},...,{A_k}\] קבוצות בנות מניה, אזי plot:\[\bigcup\limits_{i = 1}^\infty  {{A_i}} \] הינו בן מניה. איחוד של מספר סופי של קבוצות בנות מניה הוא בן מניה.

הוכחה: אם כל הקבוצות סופיות, ראינו שאיחוד סופי של קבוצות סופיות הוא סופי.

נתעניין לכן במקרה בו לפחות אחת הקבוצות הינה אינסופית, ומכאן שהאיחוד כולו הוא אינסופי.

נבנה טבלה בה בעמודה יהיו הקבוצות השונות ובתוך הטבלה יהיו האיברים השונים של הקבוצות:

plot:\[\begin{gathered}   {A_1} = \left\{ {{a_{10}},...} \right\} \hfill \\   {A_2} = \left\{ {{a_{20}},...} \right\} \hfill \\   ... \hfill \\   {A_k} = \left\{ {{a_{k0}},...} \right\} \hfill \\ \end{gathered} \]



בשלב ה-plot:\[j\] נספור את כל האיברים מהצורה plot:\[i = 1,...,k & {a_{ij}}\]. כל שלב הוא לכל היותר באורך plot:\[k\]. כל איבר יופיע בסדרה ולפניו מספר סופי של איברים ולכן plot:\[\bigcup\limits_{i = 1}^\infty  {{A_i}} \] הינו בן מניה.

משפט (בלא הוכחה)

איחוד של מספר בן מניה של קבוצות בנות מניה הוא בן מניה.

טענה

אם A ו-B בנות מניה, אזי plot:\[A \times B\] בת מניה.

טענה

plot:\[{\mathbb{Q}^ + }\] - הרציונליים החיוביים - בת מניה. plot:\[a,b \in \mathbb{N},\frac{a}{b}\]

אם נצליח לספור את החיוביים, נוכל לספור גם את השליליים. ניצור טבלה:

1

2

3

4

5

...

1

1/1

1/2

1/3

1/4

1/5

2

2/1

2/2

2/3

2/4

2/5

3

3/1

3/2

3/3

3/4

3/5

4

4/1

4/2

4/3

4/4

4/5

5

5/1

5/2

5/3

5/4

5/5

...

ישנם מספרים שמופיעים כמה פעמים - למשל - כל האלכסון הראשי.

בשלב ה-plot:\[k\], plot:\[k > 1\], נספור את כל המספרים מהצורה plot:\[\frac{a}{b}\] כך ש-plot:\[a + b = k\]. (ישנם plot:\[k + 1\] מספרים כאלו). כל מספר מהצורה plot:\[\frac{a}{b}\] יספר בשלב ה-plot:\[a + b\] קיים שלב כזה! זוהי ספירה עם חזרות.



דוגמא

תהיplot:\[\Sigma \] שפה סופית (קבוצה סופית של אותיות). קבוצת המילים הסופיות מעל plot:\[\Sigma \] היא בת מניה.

סקיצה להוכחה:

מספר המילים באורך k כלשהו הקיימות הינו plot:\[{\Sigma ^k}\].

נגדיר מניה בה בשלב ה-plot:\[k\] נספור את כל המילים באורך plot:\[k\]. כל שלב בספירה הוא סופי ולכן הטענה נכונה.

דוגמא

תהי plot:\[\Sigma \] קבוצה בת מניה של אותיות. נטען: קבוצת המילים הסופיות מעל plot:\[\Sigma \] היא בת מניה.

פתרון:

עבור כל תא במילה יש אין סוף אפשרויות לאותיות לכן אי אפשר להשתמש בדרך פתרון הקודמת.

- בשלב ה-plot:\[k\], plot:\[k \geqslant 1\], נספור את כל המילים באורך קטן שווה plot:\[k\] שהאותיות בהן הן מהקבוצה plot:\[\{ {a_0},{a_1},...,{a_{k - 1}}\} \].

כמה מילים כאלו יש? plot:\[\sum\limits_{i = 1}^k {{k^i}} \].

נוכיח שכל מילה נספרת בספירה זו.

תהיי מילה plot:\[{k_1}{k_2}...{k_r}\]. נסתכל על האות שבה האינדקס הוא מקסימלי. יהי s האינדקס. המילה תיספר בשלב שהוא המקסימום בין plot:\[r\] ל-plot:\[s + 1\].



טענה

אם B בת מניה ו-A קבוצה סופית, אזי plot:\[{B^A}\] היא בת בניה.

נגדיר מניה:

בשלב ה-k נספור את כל הפונקציות מ-A לקבוצה plot:\[\{ {b_1},...,{b_k}\} \]. יש plot:\[{k^{\left| A \right|}}\] פונקציות כאלו.

בהינתן פונקציה plot:\[f:A \to B\], יהיו plot:\[f({a_1}),...,f({a_n})\] ערכי הפונקציה.

יהיו plot:\[{b_{1j}} = f({a_j}),1 \leqslant j \leqslant n\]

נביט על הערך המקסימלי מבין plot:\[{b_{i1}},{b_{i2}},...,{b_{in}}\]. יהי plot:\[r\] המקסימלי שבהם. לכן plot:\[f\] נספרת בשלב ה-plot:\[r\].

טענה

לכל קבוצה אין סופית A יש תת קבוצה בת מניה.

נבנה קבוצה B: plot:\[B = \{ {b_i}|i \in N\} \].

יהי plot:\[{b_0} \in A\] ותהי plot:\[{B_0} = \{ {b_0}\} \]. יהיplot:\[{b_1} \in A/{B_0}\] ותהי plot:\[{B_1} = \{ {b_0},{b_1}\} \].

נניח plot:\[{B_i} = \{ {b_0},{b_1},...,{b_i}\} \] כאשר plot:\[{B_i} \subset A\]. יהיplot:\[{b_{i + 1}} \in A/{B_i}\] ותהי plot:\[{B_{i + 1}} = {B_i} \cup \{ {b_{i + 1}}_1\} \].

כל אחת מהקבוצות plot:\[{B_i}\] היא סופית. איחוד כל איברי קבוצות plot:\[{B_i}\] הוא אינסופי. המניה היא הסדר בו בחרנו איברים מ-A. הקבוצה הזו היא עם עוצמה שווה לזו של הטבעיים.

משפט

לכל קבוצה אינסופית A יש תת קבוצות אמיתיות (תת קבוצה ממש) בעלות עוצמה שווה ל-A.

כיוון

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

הוכחה

תהיי plot:\[B \subseteq A\] בת מניה plot:\[B = \{ {b_i}|i \in \mathbb{N}\} \], ותהי plot:\[B' = \{ {b_i}|i \in \mathbb{N},i \geqslant 1\} \].

נבנה העתקה בין שתי הקבוצות שהיא התאמה חח"ע.

נבנה g חד חד ערכית ועל.

plot:\[g:A \to A/\{ {b_0}\} \]

plot:\[A/\{ {b_0}\} \] היא תת קבוצה אמיתית של A. אם נצליח למצוא g כמבוקש נראה כי ל-A ולplot:\[A/\{ {b_0}\} \] יש אותה עוצמה.

נגדיר את g:

plot:\[g(x) = \left\{ {\begin{array}{*{20}{c}}    x & {x \in A/B}  \\    {{b_{i + 1}}} & {x \in B( \Rightarrow x \in {b_i})}  \\ \end{array} } \right.\]

מסקנה חשובה

אם ניקח קבוצה אינסופית ונוציא ממנה מספר סופי של איברים, נשמור על עוצמת הקבוצה.

מסקנה ללא הוכחה

אם ניקח קבוצה מעוצמה גבוהה, ונוציא מספר איברים מעוצמה נמוכה יותר, העוצמה תישמר.

דוגמא

תהי קבוצת הווקטורים האינסופיים מעל plot:\[\mathbb{N}\] כך שלכל plot:\[n \in \mathbb{N}\] סכום האיברים במקומות plot:\[n,n + 1,...,n + 6\] הינו 21. מהי עוצמת הקבוצה?

נשים לב שהגדרת 6 המקומות הראשונים בווקטור מגדירה את שאר האיברים שלו באופן יחיד, ולכן הקבוצה הינה קבוצה סופית, ומספר איבריה, העוצמה שלה הוא plot:\[\left( {\begin{array}{*{20}{c}}    {21 + \left( {6 - 1} \right)}  \\    {6 - 1}  \\ \end{array} } \right)\].

דוגמא

נניח שאנו מבצעים את הניסוי הבא: מטילים מטבע עד שמקבלים H בפעם הראשונה.

נגדיר את הקבוצה O:  { תוצאות הניסוי } = O

נוכיח כי O היא קבוצה בת מניה.

נגדיר plot:\[f:\mathbb{N} \to O\] בצורה באה:

plot:\[f\left( 0 \right) = H & f\left( 1 \right) = T,H & ... & f\left( n \right) = \underbrace {T,...,T}_{n{\text{ times}}},H\]

נשים לב:

אם plot:\[f\] היא על אזי O היא בת מניה (סופית או אינסופית). בנוסף, אם plot:\[f\] חח"ע אזי O אינסופית.

ניתן לראות בנקל כי הפונקציה שהגדרנו היא חח"ע, אולם פונקציה זו איננה על. לניסוי plot:\[T,T,T,...\], שהוא ניסוי חוקי, אין מקור. כדי להפוך פונקציה זו לעל נגדיר אותה מחדש:

plot:\[f\left( 0 \right) = T,T,... &  & f\left( 1 \right) = H & f\left( 2 \right) = T,H & ... & f\left( {n + 1} \right) = \underbrace {T,...,T}_{n{\text{ times}}},H\]

השיטה בה השתמשו כדי להפוך את הפונקציה לעל היא שימושית ומכונה לעתים "תרגיל המלון האינסופי". מקור השם הוא בתרגיל המחשבתי הבא: זוג מגיע לבית מלון בעל אינסוף חדרים, אולם אומרים להם שכל החדרים תפוסים, והשאלה – היכן למקם את בני הזוג? הפתרון: כל דייר שכבר נמצא במלון יעבור לחדר הבא (דייר מחדר 1 יעבור לחדר 2 וכו'), ואז חדר מספר 1 יהיה פנוי עבור הזוג.

הרעיון באופן כללי: כיצד נוכיח שאיחוד של קבוצה סופית וקבוצה בת מניה הינו בן מניה?

הפתרון: נשים את הקבוצה הסופית בהתחלת הספירה, ואת הקבוצה האינסופית אחריה.



תגיות המסמך:

לפרק הקודם5.3. הגדרה 2 לקבוצה אינסופית – הגדרה לפי תכונה
לפרק הבא5.5. משפט קנטור
מאת: סטודנטית

הוכחות להגדרה 2

אשמח להגדרות פורמליות מפורטות עבור המשפט. תודה רבה
מאת: ילדה

תודה רבה!

תודה על ההסבר המצוין
מאת: אני

תודה

מברוק! תודה
מאת: ברק

יש לכם טעות

בסגור הטרנזיטיבי שהתקבל אצלכם, קיימים הזוגות <4,1> ו-<1,4>, אבל מתוקף היותו טרנזיטיבי הוא חייב גם להכיל את <1,1> ו-<4,4>. ההגדרה של טרנזיטיביות לא מחייבית a,b,c שונים.

כנ"ל לגבי <2,3> ו-<4,2> - חייב להימצא הזוג הסדור <4,3>.
מצאתי עוד 3 דוגמאות כאלה..
מאת: יואב

מבלבל

היית צריך לתת דוגמאות גם ליחסים לא סימטריים.... התבלבלתי ממש בין X לY בגלל זה...
מאת: יואב

מבלבל

היית צריך לתת דוגמאות גם ליחסים לא סימטריים.... התבלבלתי ממש בין X לY בגלל זה...
מאת: אמיר

קבוצה סופית

מישו יכול להעלות את ההוכחה לכך שכל תת קבוצה של קבוצה סופית היא סופית ? זה ברור אבל אני צריך את ההגדרה הפורמלית לזה ..
מאת: רעות

תודה רבה

תודה רבה ספר מעולה מסביר מצויין שתצליח תמיד :-)
מאת: עומר

סגור טרנזיטיבי

ניר אתה בטוח ש- (4,2) הוא חלק מהסגור הטרנזיטיבי (משפט 3 מלמעלה)?
אני לא סגור על החומר, אבל אני לא חושב שזה נכון...
מאת: אחד שלומד

יפה מאוד אך ישנן כמה טעויות

ישנן כמה טעויות (קריטיות להוכחה) כשעברתי על החומר,
למשל בהוכחה ש R* טרנזיטיבית (סעיף 2) יש בלבול שלם בין x,y,z אז צריך לתקן את זה.
מאת: אני

כל הכבוד!!!!

כל הכבוד על העבודה שעשית כאן!!!
נורא עוזר!!!!
מאת: אני

תודה רבה רבה רבה רבה!

כל הכבוד על העלאת הסיכום המעולה הזה לטובת כולם!
מאת: אלעד

המון תודה

וואו, חומר כל כך ברור ומסודר!
עברתי על עשרות ספרים ואף אחד לא ברור וענייני כמו זה - פשוט כל הכבוד!
תודה, תודה תודה!
מאת: אולג

תודה רבה!!!!!!!!

אף פעם לא ברור לי מה האינטרס של אנשים כמוך, להעלות חומר ממש מועיל לאינטרנט בחינם...

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

והלוואי ויהיו רבים כמוך...
שיתוף:
| עוד