תורת הקבוצות

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

5.6.2. עוצמת הרצף

הבחנה

$plot:\[{2^\mathbb{N}}\]$ איננה קבוצת בת מניה. הבחנה זו נכונה לפי משפט קנטור.

$plot:\[{2^\mathbb{N}}\]$ היא קבוצת החזקה של המספרים הטבעיים. כמו כן, ניתן לזהות אותה עם קבוצת הווקטורים הבינאריים האינסופיים.

הגדרה

עוצמת קבוצת החזקה של הטבעיים, $plot:\[{2^\mathbb{N}}\]$ , תכונה עוצמת רצף.

הגדרה חלופית

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

סימון

סימון לעוצמת רצף: $plot:\[\left| A \right| = \neg \]$

מספרים ממשיים

נסתכל על הקטע [0,1]. נטען כי קבוצת המספרים בקטע זה איננה בת מניה.

כל מספר בקטע בין 0 ל-1 יכול להיות מיוצג בצורה הבאה: $plot:\[0.{x_1}{x_2}{x_3}...\]$ כאשר $plot:\[0 \leqslant {x_i} \leqslant 9\]$ .

נניח שקיימת $plot:\[g:N \to [0,1]\]$ . נכתוב אותה:

$plot:\[\begin{gathered} g(0) = 0.{x_{00}}{x_{01}}{x_{02}}... \hfill \\ g(1) = 0.{x_{10}}{x_{11}}{x_{12}}... \hfill \\ ... \hfill \\ g(i) = 0.{x_{i0}}{x_{i1}}{x_{i2}}... \hfill \\ \end{gathered} \]$

נבנה את המספר y:

$plot:\[\begin{gathered} y = 0.{y_0}{y_1}{y_2}... \hfill \\ {y_i} \ne {x_{ii}} \hfill \\ \end{gathered} \]$

המספר הזה לא יתקבל על ידי $plot:\[g\]$ . מ.ש.ל.

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

יש מספרים שיש להם יותר מייצוג אחד. המספר $plot:\[0.399\dot 9 = 0.400\dot 0\]$ . למשל, 0.9999...=1.

זוהי בעייה שלא הייתה לנו במילים הבינריות האינסופיות.

לכן נוסיף דרישה נוספת למספר y.

$plot:\[y = {y_0}{y_1}{y_2}..., & {y_i} \ne {x_{ii}},{y_i} \ne \{ 0,9\} \]$

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

טענה

נטען: $plot:\[\left| {[a,b]} \right| = \left| {(a,b)} \right| = \left| {(a,b]} \right|\]$

נפצל את ההוכחה למספר חלקים.

טענה: עוצמת הקטע [0,a] היא עוצמת הרצף.

$plot:\[\begin{gathered} f:[0,1] \to [0,a] \hfill \\ f(x) = ax \hfill \\ \end{gathered} \]$

טענה: עוצמת הקטע $plot:\[\left[ {x,x + a} \right]\]$ היא רצף.

$plot:\[\begin{gathered} f:[0,a] \to [x,x + a] \hfill \\ f(y) = x + y \hfill \\ \end{gathered} \]$

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

עכשיו נרצה לעבור לקטע אינסופי.

$plot:\[\begin{gathered} f:(0,1) \to (1,\infty ) \hfill \\ f(x) = \frac{1}{x} \hfill \\ \end{gathered} \]$

מכאן העוצמה של הקטע (0,1) זהה לעוצמה של הקטע $plot:\[(1,\infty )\]$ .

ברור וטריויאלי כי $plot:\[\left| {(0,2)} \right| = \left| {(0,\infty )} \right|\]$ . ומכאן $plot:\[\left| {( - 2,2)} \right| = \left| {( - \infty ,\infty )} \right|\]$ שזה זהה לפי הטענה ההתחלתית

ל- $plot:\[\left| {(0,1)} \right| = \left| {( - \infty ,\infty )} \right|\]$ .

תרגיל

תהא $plot:\[B\]$ הקבוצה הבאה: { $plot:\[b\]$ ווקטור בינארי אינסופי | $plot:\[b\]$ } = $plot:\[B\]$ . הוכח: $plot:\[B\~B \times B\]$ .

צ"ל קיומה של פונקציה חח"ע ועל $plot:\[f:B \to B \times B\]$ .

נבחר את הפונקציה הבאה: $plot:\[f\left( b \right) = \left( {b',b''} \right)\]$ , כאשר: $plot:\[b = {b_0}{b_1}{b_2}..., & b \in {\left\{ {0,1} \right\}^*}\]$ ונגדיר:

$plot:\[b' = {b_0}{b_2}{b_4}..., & b'' = {b_1}{b_3}{b_5}...\]$

נראה כי פונקציה זו הינה חח"ע: יהיו $plot:\[b,x \in B\]$ כך ש- $plot:\[x \ne b\]$ . צ"ל: $plot:\[f\left( b \right) \ne f\left( x \right)\]$ .

מהנתון: קיים $plot:\[i\]$ כך ש $plot:\[{b_i} \ne {x_i}\]$ . אם $plot:\[i\]$ זוגי אזי $plot:\[{b'_{i/2}} \ne {x'_{i/2}}\]$ ואז $plot:\[b' \ne x'\]$ ולכן $plot:\[f\left( b \right) \ne f\left( x \right)\]$ .

אם $plot:\[i\]$ אי זוגי אזי $plot:\[{b''_{\left( {i - 1} \right)/2}} \ne {x''_{\left( {i - 1} \right)/2}}\]$ ואז $plot:\[b'' \ne x''\]$ ולכן $plot:\[f\left( b \right) \ne f\left( x \right)\]$ .

נראה כי $plot:\[f\]$ הינה על. יהי $plot:\[\left( {c,d} \right) \in B \times B\]$ . צריך למצוא $plot:\[b \in B\]$ כך שיתקיים $plot:\[f\left( b \right) = \left( {c,d} \right)\]$ .

נבחר את $plot:\[b\]$ להיות הווקטור הבא: $plot:\[b = {c_0}{d_0}{c_1}{d_1}...\]$ . לפי הגדרת $plot:\[f\]$ מתקיים: $plot:\[f\left( b \right) = \left( {c,d} \right)\]$ .

סימון

נסמן ב- $plot:\[{B^A}\]$ את אוסף הפונקציות מ- $plot:\[A\]$ אל $plot:\[B\]$ : $plot:\[{B^A} = \left\{ {f \subseteq A \times B{\text{ and }}f{\text{ is function}}} \right\}\]$ .

את $plot:\[{\left\{ {0,1} \right\}^\mathbb{N}}\]$ נסמן לעתים ב- $plot:\[{2^\mathbb{N}}\]$ . ניתן להסתכל על $plot:\[{\left\{ {0,1} \right\}^\mathbb{N}}\]$ כאוסף כל הווקטורים הבינאריים האינסופיים.

משפט

לכל קבוצה $plot:\[B\]$ מתקיים כי $plot:\[P\left( B \right)\~{2^B}\]$ .

ניתן להסתכל על הטענה כהתאמת אוסף כל הפונקציות מ- $plot:\[B\]$ אל $plot:\[\left\{ {0,1} \right\}\]$ .

נראה פונקציה חח"ע ועל מ- $plot:\[P\left( B \right)\]$ ל- $plot:\[{2^B}\]$ : עבור כל $plot:\[\left( {A \subseteq B} \right),A \in P\left( B \right)\]$ נגדיר $plot:\[f\left( A \right) = {g_A}\]$ .

$plot:\[{g_A}\]$ היא פונקציה מ- $plot:\[B\]$ אל $plot:\[\left\{ {0,1} \right\}\]$ המוגדרת כך: $plot:\[{g_A}\left( x \right) = \left\{ {\begin{array}{*{20}{c}} 1 \hfill & {x \in A} \hfill \\ 0 \hfill & {else} \hfill \\ \end{array} } \right.\]$ .

פונקציה זו נקראת הפונקציה האופיינית של $plot:\[A\]$ . היא מסומנת לעתים גם $plot:\[{\chi _A}\]$ .

ניתן לראות בקלות כי $plot:\[f\]$ הינה חח"ע ועל.

לפרק הקודם5.6.1. השערת הרצף

לפרק הבא5.7. משפט קנטור ברנשטיין

מאת: סטודנטית

15/12/2020 19:15

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

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

מאת: ילדה

17/4/2018 19:45

תודה רבה!

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

מאת: אני

24/12/2017 13:48

תודה

מברוק! תודה

מאת: ברק

22/12/2017 18:24

יש לכם טעות

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

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

מאת: יואב

10/12/2017 22:33

מבלבל

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

מאת: יואב

10/12/2017 22:32

מבלבל

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

מאת: אמיר

11/1/2017 13:15

קבוצה סופית

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

מאת: רעות

26/11/2016 22:48

תודה רבה

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

מאת: עומר

1/6/2013 21:30

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

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

מאת: אחד שלומד

8/3/2013 11:34

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

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

מאת: אני

26/11/2011 12:01

כל הכבוד!!!!

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

מאת: אני

20/11/2011 20:01

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

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

מאת: אלעד

8/7/2011 20:08

המון תודה

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

מאת: אולג

6/4/2010 21:54

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

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

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

והלוואי ויהיו רבים כמוך...

דיווח על הפרת זכויות יוצרים