שינויים
/* חומר עזר */
*[[מדיה:16BdidaOrit.pdf|סיכומי ההרצאות של ד״ר ארז שיינר, ע״י אורית חסון, קיץ 2016]]
*[[מבחנים בבדידה]]
*[[בחנים בבדידה]]
*[[מבחנים בקורס בדידה למורים]] - שימו לב, הקורס למורים מכיל משמעותית פחות חומר, והמבחנים קלים יותר. יחד עם זאת, יש שם כמות גדולה של תרגילים רלוונטיים ברמה נמוכה.
===אקסיומת הבחירה ועקרון המקסימום של האוסדורף===
====אקסיומת הבחירה====
*תהי S קבוצת קבוצת קבוצות לא ריקות, ונסמן את האיחוד הכללי ב <math>U=\cup_{X\in S}X</math>.
*אזי קיימת פונקצית בחירה <math>f:S\to U</math> הבוחרת איבר מתוך כל קבוצה, כלומר:
**<math>\forall X\in S: f(X)\in X</math>
***הוכחה דומה לח"ע
===איחוד בן מנייה של קבוצות בנות מנייה===
*תהיינה שתי קבוצות A,B אזי <math>|A|\leq|B|</math> או <math>|A|\geq |B|</math>
*נביט ב<math>U</math> אוסף היחסים הח"ע והחח"ע מ<math>A</math> ל<math>B</math>, וניקח שרשרת מקסימלית ביחס ההכלה <math>M\subseteq U</math>
*נסמן ב<math>f</math> את האיחוד הכללי על השרשרת <math>M</math>
*ראינו שנובע במקרה זה כי <math>f</math> יחס ח"ע וחח"ע מ<math>A</math> ל<math>B</math>.
**אם <math>f</math> שלם, אזי <math>f:A\to B</math> פונקציה חח"ע ולכן <math>|A|\leq |B|</math>
**אם <math>f</math> על, אזי <math>f:X\to B</math> פונקציה על עבור <math>X\subseteq A</math> ולכן <math>|B|\leq |X|\leq |A|</math>
**אחרת, קיים זוג <math>(a,b)\in A\times B</math> כך ש <math>f\cup\{(a,b)\}</math> יחס ח"ע וחח"ע שניתן להוסיף לשרשרת <math>M</math> בסתירה למקסימליות שלה.
<videoflash>XZkMt26fQyE</videoflash>
====אלף אפס היא העוצמה האינסופית הקטנה ביותר====
(בהנחת עקרון המקסימום של האוסדורף)
*תהי A קבוצה אינסופית, אזי <math>\aleph_0\leq |A|</math>
*דרך נוספת לזו המופיעה בסרטון:
**נוכיח בהמשך כי ניתן להשוות עוצמה בין כל שתי קבוצות
**אם <math>|A|\leq |\mathbb{N}|</math>, כיוון ש<math>A</math> אינסופית נובע כי <math>|A|=\aleph_0</math>
**אחרת, <math>|\mathbb{N}|\leq |A|</math> ולכן <math>\aleph_0\leq |A|</math> כפי שרצינו.
<videoflash>W4see8tTArk</videoflash>
*תהי A קבוצה אינסופית, ותהי B קבוצה סופית, אזי:
**<math>|A|=|A\cup B|=|A\setminus B|</math>
*דרך נוספת לזו המופיעה בסרטון:
**בהמשך נוכיח כי לכל קבוצה אינסופית <math>X</math> מתקיים כי <math>|X|+|X|=|X|</math>
**לכן <math>|A|\leq |A\cup B|=|A|+|B\setminus A|\leq |A|+|A|=|A|</math> ולפי ק.ש.ב <math>|A|=|A\cup B|</math>.
***שימו לב כי <math>B\setminus A</math> סופית ולכן קטנה יותר מהקבוצה האינסופית <math>A</math>.
**כמו כן <math>|A|=|A\setminus B|+|B\cap A|</math>
**כעת <math>|A\setminus B|\leq|A\setminus B|+|B\cap A|\leq |A\setminus B|+|A\setminus B|=|A\setminus B|</math>.
***שימו לב כי <math>B\cap A</math> סופית ולכן קטנה יותר מהקבוצה האינסופית <math>A\setminus B</math>.
**לכן לפי ק.ש.ב <math>|A|=|A\setminus B|+|B\cap A|=|A\setminus B|</math>
<videoflash>eaonM-yfR3w</videoflash>
===סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות===
<videoflash>Ty-lY6-uRPo</videoflash>
====עוצמה כפול עצמה====
*תהי קבוצה אינסופית <math>B</math> אזי <math>B\times B\sim B</math>
*הוכחה:
*תהי <math>S</math> קבוצת כל היחסים <math>R\subseteq (B\times B)\times B</math>, כך שקיימת תת קבוצה <math>X\subseteq B</math> כך ש <math>R:X\times X\to X</math> פונקציה הפיכה.
*כיוון ש<math>B</math> אינסופית, יש לה תת קבוצה <math>Y\subseteq B</math> כך ש <math>|Y|=\aleph_0</math>.
*כיוון ש <math>\aleph_0\times\aleph_0=\aleph_0</math> קיימת פונקציה הפיכה <math>R:Y\times Y\to Y</math>.
*נביט ביחס ההכלה על <math>S</math>. לפי עקרון המקסימום של האוסדורף, קיימת שרשרת מקסימלית <math>\{R\}\subseteq M\subseteq S</math>.
*נסמן ב<math>f</math> את האיחוד הכללי של השרשרת <math>f=\cup_{T\in M} T</math>.
*נוכיח כי קיימת <math>D\subseteq B</math> כך ש <math>f:D\times D\to D</math> פונקציה הפיכה, ואף <math>|D|=|B|</math> וכך נסיים את ההוכחה.
*הוכחה כי <math>f\in S</math> פונקציה הפיכה <math>f:D\times D\to D</math> עבור תת קבוצה <math>D\subseteq B</math>:
*ראשית, נגדיר את <math>D=\{d\in B | \exists a,b\in B:((a,b),d)\in f\}</math>
*נוכיח כי <math>f\subseteq (D\times D)\times D</math>:
**יהי זוג <math>((a,b),d)\in f</math>, לפי ההגדרה <math>d\in D</math>
**כמו כן, לפי הגדרת האיחוד קיים <math>T\in M</math> כך ש <math>((a,b),d)\in T</math>.
**קיימת <math>X\subseteq B</math> כך ש <math>T:X\times X\to X</math> פונקציה הפיכה.
**כיוון ש <math>T</math> על, לכל <math>x\in X</math> קיימים <math>p,q\in X</math> כך ש <math>((p,q),x)\in T</math> ולכן <math>((p,q),x)\in f</math> ולכן <math>x\in D</math>
**ביחד עם העובדה ש <math>a,b\in X</math> נובע כי <math>a,b\in D</math>
*כיוון שכל איברי השרשרת הם יחסים ח"ע, גם <math>f</math> ח"ע.
*כיוון שכל איברי השרשרת הם יחסים חח"ע, גם <math>f</math> חח"ע.
*כעת נוכיח כי <math>f:D\times D\to D</math> יחס שלם:
**יהיו <math>d_1,d_2\in D</math>.
**ראינו כי קיימים <math>T_1,T_2\in M</math> ואיברים <math>a_1,b_1,a_2,b_2\in D</math> כך ש <math>((a_1,b_1),d_1)\in T_1</math> וכן <math>((a_2,b_2),d_2)\in T_2</math>
**כיוון ש<math>M</math> שרשרת, <math>T_1\subseteq T_2</math> (או ההפך) ולכן <math>a_1,a_2,b_1,b_2\in X</math> עבור תת קבוצה <math>X\subseteq D</math> כך ש <math>T_2:X\times X\to X</math> פונקציה הפיכה.
**לכן קיים <math>d_3\in X\subseteq D</math> כך ש <math>((d_1,d_2),d_3)\in T_2</math> ולכן <math>((d_1,d_2),d_3)\in f</math> כלומר <math>f</math> שלם.
*הוכחנו כי <math>f:D\times D\to D</math> היא פונקציה (יחס ח"ע ושלם) חח"ע, נותר להוכיח כי היא על:
**יהי <math>d\in D</math>. ראינו כי קיים <math>T\in M</math> וקיימים <math>a,b\in D</math> כך ש <math>((a,b),d)\in T</math> ולכן <math>((a,b),d)\in f</math> ולכן הפונקציה על.
*הוכחה כי <math>|D|=|B|</math>:
*ראשית, נשים לב כי <math>Y\subseteq D</math> כיוון ש <math>R:Y\times Y\to Y</math> פונקציה הפיכה וכן <math>R\in M</math>, ולכן <math>D</math> אינסופית.
*כעת, נזכור שהוכחנו כי <math>|D\times D|=|D|</math>.
*נביט ב <math>B\setminus D</math> ונחלק למקרים:
*אם <math>|B\setminus D|\leq D</math> אזי:
**<math>|B|=|D|+|B\setminus D|\leq |D|+|D|\leq |D|\times |D| =|D|</math>
**כמובן ש <math>|D|\leq |B|</math> ולפי ק.ש.ב נסיק כי במקרה זה <math>|B|=|D|</math> וסיימנו.
*אם <math>|B\setminus D|\geq |D|</math> נראה כי נגיע לסתירה, ולכן מקרה זה בלתי אפשרי:
**ניקח תת קבוצה <math>U\subseteq B\setminus D</math> כך ש <math>|U|=|D|</math>.
**לכן <math>|(U\times D) \cup (D\times U) \cup (U\times U)|=|D|+|D|+|D|=|D|</math> (הרי ראינו מקודם כי <math>|D|+|D|=|D|</math>)
**לכן קיימת פונקציה הפיכה <math>g:(U\times D) \cup (D\times U) \cup (U\times U)\to U</math>.
**האיחוד <math>h=f\cup g</math> הוא פונקציה הפיכה <math>h:(U\cup D)\times (U\cup D)\to (U\cup D)</math>, ולכן <math>h\in S</math>.
**ניתן להוסיף את <math>h</math> לשרשרת <math>M</math> ולהגדיל אותה, בסתירה למקסימליות שלה.
