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

תורת הקבוצות

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

5.5.2. קבוצות שאינן בנות מניה – שיטת הליכסון של קנטור

תהי plot:\[f\] פונקציה plot:\[f:A \to P\left( A \right)\]. נראה כי קיימת קבוצה plot:\[{B_f} \in P\left( A \right)\] שאינה מתקבלת כתמונה של אחד מאיברי plot:\[A\], כלומר plot:\[{B_f} \notin f(A)\], ומכאן שכל פונקציה plot:\[f:A \to P(A)\] איננה על.

ניתן להציג את plot:\[f\] בצורת הטבלה הבאה:

plot:\[f\left( {{a_1}} \right)\]

plot:\[f\left( {{a_2}} \right)\]

plot:\[f\left( {{a_3}} \right)\]

plot:\[f\left( {{a_4}} \right)\]

...

...

plot:\[{a_1}\]

plot:\[{a_2}\]

plot:\[{a_3}\]

plot:\[{a_4}\]

...

...

(מניחים כי הקבוצה plot:\[A\] בת מניה כי אחרת לא ניתן לרשום אותה בטבלה כנ"ל).

במקום ה-plot:\[\left( {{a_1},f\left( {{a_1}} \right)} \right)\] נרשום plot:\[1\] אם plot:\[{a_1} \in f\left( {{a_1}} \right)\] או plot:\[0\] אחרת. באופן כללי: במקום ה-plot:\[\left( {{a_j},f\left( {{a_k}} \right)} \right)\] נרשום 1 אם plot:\[{a_j} \in f\left( {{a_k}} \right)\] ו-0 אחרת.

דוגמא

תהי plot:\[A\] הקבוצה plot:\[A = \left\{ {{a_1},{a_2},{a_3},{a_4}} \right\}\] ותהי plot:\[f\] שמוגדרת כך:

plot:\[\begin{gathered}   f\left( {{a_1}} \right) = \phi , &  & f\left( {{a_2}} \right) = \left\{ {{a_1},{a_3}} \right\} \hfill \\   f\left( {{a_3}} \right) = \left\{ {{a_1},{a_2},{a_3}} \right\} & f\left( {{a_4}} \right) = \phi  \hfill \\ \end{gathered} \]



נכתוב את plot:\[f\] בטבלה:

plot:\[f\left( {{a_1}} \right)\]

plot:\[f\left( {{a_2}} \right)\]

plot:\[f\left( {{a_3}} \right)\]

plot:\[f\left( {{a_4}} \right)\]

plot:\[{a_1}\]

0

1

1

0

plot:\[{a_2}\]

0

0

1

0

plot:\[{a_3}\]

0

1

1

0

plot:\[{a_4}\]

0

0

0

0

כל עמודה בטבלה מגדירה תת קבוצה של plot:\[A\].

מציאת plot:\[{B_f} \subseteq A\] שאיננה מתקבלת על ידי plot:\[f\] שקולה למציאת עמודה שאיננה מופיעה בטבלה – נמצא עמודה שתהיה שונה מכל עמודה אחרת.

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

כלומר, אם plot:\[{a_1} \not\subset f\left( {{a_1}} \right)\] נרשום plot:\[1\] אחרת נרשום plot:\[0\] וכך הלאה:

plot:\[f\left( {{a_1}} \right)\]

plot:\[f\left( {{a_2}} \right)\]

plot:\[f\left( {{a_3}} \right)\]

plot:\[f\left( {{a_4}} \right)\]

plot:\[{a_1}\]

1

1

0

plot:\[{a_2}\]

0

1

0

plot:\[{a_3}\]

0

1

0

plot:\[{a_4}\]

0

0

0

באופן כללי, העמודה השונה מכל עמודה אחרת בעמודה ה-plot:\[i\] היא שונה לפחות באיבר ה-plot:\[i\].

טכניקה זו שימושית – בעזרתה מוכיחים שקבוצות אינן בנות מניה.



תגיות המסמך:

לפרק הקודם5.5.1. הגדרות
לפרק הבא5.5.3. משפט קנטור
מאת: סטודנטית

הוכחות להגדרה 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 אז צריך לתקן את זה.
מאת: אני

כל הכבוד!!!!

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

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

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

המון תודה

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

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

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

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

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