תורת הקבוצות

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

5.1. הקדמה לעוצמות

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

עבור קבוצה סופית $plot:\[A\]$ גודל הקבוצה הינו $plot:\[\left| A \right|\]$ . עוצמת הקבוצה היא הגודל של $plot:\[A\]$ .

גודל במקרה זה הוא מספר האיברים בקבוצה.

משפט

תהינה $plot:\[A\]$ ו- $plot:\[B\]$ קבוצות סופיות. מתקיים כי $plot:\[\left| A \right| = \left| B \right|\]$ אמ"מ קיימת התאמה חד חד ערכית $plot:\[f:A \to B\]$ .

הוכחה:

תהינה הקבוצות $plot:\[A = \left\{ {{a_1},...,{a_k}} \right\},B = \left\{ {{b_1},...,{b_n}} \right\}\]$ .

כיוון $plot:\[ \Leftarrow \]$ : נניח כי $plot:\[n = k\]$ . נגדיר $plot:\[f:A \to B\]$ כך: $plot:\[f\left( {{a_i}} \right) = {b_i},1 \leqslant i \leqslant n\]$ . קל לראות ש- $plot:\[f\]$ התאמה חד חד ערכית.

כיוון $plot:\[ \Rightarrow \]$ : נניח כי קיימת התאמה חח"ע – מאחר ו- $plot:\[f\]$ חח"ע מתקיים כי $plot:\[f\left( {{a_1}} \right),...,f\left( {{a_k}} \right)\]$ הם $plot:\[k\]$ איברים שונים ב- $plot:\[B\]$ , ולכן $plot:\[n \geqslant k\]$ . מאחר ו- $plot:\[f\]$ ל, אז אלו הם כל האיברים, ולכן $plot:\[n = k\]$ .

הגדרה

נאמר ששתי קבוצות A ו-B הן בעלות עוצמה שווה, בעלות אותה קרדינליות, אם קיימת ביניהם התאמה חח"ע, כלומר אם קיימת פונקציה $plot:\[f:A \to B\]$ שהיא פונקציה של A על B וחח"ע.

נאמר ש-A ו-B שקולות ונסמן A~B,

דוגמאות

תהי הקבוצה $plot:\[B = \left\{ {\left. {{n^2}} \right|n \in \mathbb{N}} \right\}\]$ . נטען כי $plot:\[B\~\mathbb{N}\]$ .

ניקח $plot:\[f:\mathbb{N} \to B\]$ כך ש- $plot:\[f(n) = {n^2}\]$ . זוהי התאמה חח"ע ומכאן $plot:\[\left| \mathbb{N} \right| = \left| B \right|\]$ .

נגדיר את הקבוצה $plot:\[\left( {a,b} \right) = \left\{ {x|x \in \mathbb{R},a < x < b} \right\}\]$ . נטען: $plot:\[\mathbb{R}\~\left( {0,1} \right)\]$ .

כדי להוכיח זאת נשתמש בעובדה כי $plot:\[\tan :\left( { - \frac{\pi }{2},\frac{\pi }{2}} \right) \to \mathbb{R}\]$ הינה חח"ע ועל.

השלבים:

$plot:\[\begin{gathered} 1) & \left( {0,1} \right) \to \left( { - 1.1} \right), & {f_1} = 2x - 1 \hfill \\ 2) & \left( { - 1,1} \right) \to \left( { - \frac{\pi }{2},\frac{\pi }{2}} \right), & {f_2} = \frac{\pi }{2}x \hfill \\ 3) & \left( { - \frac{\pi }{2},\frac{\pi }{2}} \right) \to \mathbb{R}, & {f_3} = \frac{\pi }{2}\left( {2x - 1} \right) \hfill \\ \end{gathered} \]$

כל הפונקציות הן חח"ע ועל.

על ידי הרכבת פונקציות נקבל:

$plot:\[f\left( {0,1} \right) \to \mathbb{R},f(x) = \tan \left( {\frac{\pi }{2}\left( {2x - 1} \right)} \right)\]$

טענה

היחס R המוגדר כך: $plot:\[R = \left\{ {\left. {\left\langle {A,B} \right\rangle } \right|\left| A \right| = \left| B \right|} \right\}\]$ הוא יחס שקילות.

הוכחה:

רפלקסיביות: צ"ל להוכיח לכל $plot:\[A\]$ כי מתקיים $plot:\[\left\langle {A,A} \right\rangle \in R\]$ , כלומר $plot:\[\left| A \right| = \left| A \right|\]$ . ניתן להשתמש בפונקצית הזהות.

סימטריות: אם $plot:\[f:A \to R\]$ התאמה חח"ע אזי גם $plot:\[{f^{ - 1}}:B \to A\]$ התאמה חח"ע, לכן אם $plot:\[\left\langle {A,B} \right\rangle \in R\]$ אזי גם $plot:\[\left\langle {B,A} \right\rangle \in R\]$ .

טרנזיטיביות: אם $plot:\[\left\langle {A,B} \right\rangle \in R\]$ ו- $plot:\[\left\langle {B,C} \right\rangle \in R\]$ אזי גם $plot:\[\left\langle {A,C} \right\rangle \in R\]$ , וזאת מכיוון שהרכבה של שתי פונקציות חח"ע ועל הינה גם חח"ע ועל.

מחלקות השקילות של היחס נקראות המספרים הקרדינלים (עוצמות).

המספר הקרדינאלי $plot:\[n \in \mathbb{N}\]$ הוא כל הקבוצות שעוצמתן שווה לעוצמה של $plot:\[\left\{ {1,...,n} \right\}\]$ .

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

לפרק הקודם5. עוצמות

לפרק הבא5.2. הגדרה 1 לקבוצה אינסופית

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

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

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

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

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

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

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