5.5.3. משפט קנטור

לכל קבוצה A , A אינה שקולה ל-P(A).  כלומר: לכל קבוצה plot:\[A\] מתקיים כי plot:\[A \prec P(A)\].

הוכחה

ההוכחה צריכה לכלול שני מרכיבים: ראשית עלינו לראות כי plot:\[A\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{
 \prec } P(A)\] ולאחר מכן אנו צריכים להוכיח כי הקבוצות אינן שקולות.

ראינו קודם במסמך זה כי plot:\[A\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{
 \prec } P(A)\] ולכן נותר להוכיח רק את השקילות.

לשם כך נראה שלכל פונקציה 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:A \to P\left( A \right)\] פונקציה. נגדיר את plot:\[{B_f}\] באופן הבא:

לכל plot:\[a \in A\], מתקיים plot:\[a \notin f(a) \Leftrightarrow
 a \in {B_f}\].

נראה כי plot:\[{B_f} \notin f\left( A \right)\], כלומר לא קיים plot:\[x \in A\] כך ש-plot:\[f\left( x \right) = {B_f}\].

נבחין בין שני מקרים:

1. plot:\[{B_f} \ne f\left( x \right) \Leftarrow x \notin {B_f} \Leftarrow x \in
 f\left( x \right)\]

2. plot:\[{B_f} \ne f\left( x \right) \Leftarrow x \in {B_f} \Leftarrow x \notin
 f\left( x \right)\]

לכן לכל פונקציה plot:\[f\] קיימת plot:\[{B_f}\] שאיננה מתקבלת על ידי plot:\[f\] ומכאן ש-plot:\[f\] איננה על.

מסקנה ממשפט קנטור

הקבוצה plot:\[P\left( \mathbb{N} \right)\] איננה בת מניה.



מסקנה 2

אנו יכולים לקבל סידרה אינסופית עולה של עוצמות: plot:\[\mathbb{N} \prec P\left( \mathbb{N}
 \right) \prec P\left( {P\left( \mathbb{N} \right)} \right) \prec ...\].

מכאן נובע שיש מספר אינסופי של עוצמות.

תגיות:

תגיות המסמך:

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

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

כל הכבוד!!!!

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

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

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

המון תודה

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

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

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

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

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