מתמטיקה בדידה - ארז שיינר - היסטוריית גרסאות

ארז שיינר: /* חומר עזר */

2023-07-18T07:35:08Z

חומר עזר

→ הגרסה הקודמת		גרסה מ־07:35, 18 ביולי 2023
שורה 2:		שורה 2:
	*[[מדיה:16BdidaOrit.pdf\|סיכומי ההרצאות של ד״ר ארז שיינר, ע״י אורית חסון, קיץ 2016]]		*[[מדיה:16BdidaOrit.pdf\|סיכומי ההרצאות של ד״ר ארז שיינר, ע״י אורית חסון, קיץ 2016]]
	*[[מבחנים בבדידה]]		*[[מבחנים בבדידה]]
			*[[בחנים בבדידה]]
	*[[מבחנים בקורס בדידה למורים]] - שימו לב, הקורס למורים מכיל משמעותית פחות חומר, והמבחנים קלים יותר. יחד עם זאת, יש שם כמות גדולה של תרגילים רלוונטיים ברמה נמוכה.		*[[מבחנים בקורס בדידה למורים]] - שימו לב, הקורס למורים מכיל משמעותית פחות חומר, והמבחנים קלים יותר. יחד עם זאת, יש שם כמות גדולה של תרגילים רלוונטיים ברמה נמוכה.

ארז שיינר: /* אקסיומת הבחירה */

2022-08-21T13:09:45Z

אקסיומת הבחירה

→ הגרסה הקודמת		גרסה מ־13:09, 21 באוגוסט 2022
שורה 382:		שורה 382:
	===אקסיומת הבחירה ועקרון המקסימום של האוסדורף===		===אקסיומת הבחירה ועקרון המקסימום של האוסדורף===
	====אקסיומת הבחירה====		====אקסיומת הבחירה====
	*תהי S קבוצת ~~קבוצת~~ לא ריקות, ונסמן את האיחוד הכללי ב <math>U=\cup_{X\in S}X</math>.		*תהי S קבוצת קבוצות לא ריקות, ונסמן את האיחוד הכללי ב <math>U=\cup_{X\in S}X</math>.
	*אזי קיימת פונקצית בחירה <math>f:S\to U</math> הבוחרת איבר מתוך כל קבוצה, כלומר:		*אזי קיימת פונקצית בחירה <math>f:S\to U</math> הבוחרת איבר מתוך כל קבוצה, כלומר:
	**<math>\forall X\in S: f(X)\in X</math>		**<math>\forall X\in S: f(X)\in X</math>

ארז שיינר: /* אלף אפס היא העוצמה האינסופית הקטנה ביותר */

2022-08-16T18:05:56Z

אלף אפס היא העוצמה האינסופית הקטנה ביותר

→ הגרסה הקודמת		גרסה מ־18:05, 16 באוגוסט 2022
שורה 492:		שורה 492:

	*דרך נוספת לזו המופיעה בסרטון:		*דרך נוספת לזו המופיעה בסרטון:
	**בהמשך נוכיח כי לכל קבוצה אינסופית <math>B</math> מתקיים כי <math>\|B\|+\|B\|=\|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>\|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\|=\|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>\|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>		**לכן לפי ק.ש.ב <math>\|A\|=\|A\setminus B\|+\|B\cap A\|=\|A\setminus B\|</math>

ארז שיינר: /* אלף אפס היא העוצמה האינסופית הקטנה ביותר */

2022-08-16T18:03:49Z

אלף אפס היא העוצמה האינסופית הקטנה ביותר

→ הגרסה הקודמת		גרסה מ־18:03, 16 באוגוסט 2022
שורה 475:		שורה 475:

	*תהי A קבוצה אינסופית, אזי <math>\aleph_0\leq \|A\|</math>		*תהי A קבוצה אינסופית, אזי <math>\aleph_0\leq \|A\|</math>


	*דרך נוספת לזו המופיעה בסרטון:		*דרך נוספת לזו המופיעה בסרטון:
שורה 488:		שורה 489:
	*תהי A קבוצה אינסופית, ותהי B קבוצה סופית, אזי:		*תהי A קבוצה אינסופית, ותהי B קבוצה סופית, אזי:
	**<math>\|A\|=\|A\cup B\|=\|A\setminus B\|</math>		**<math>\|A\|=\|A\cup B\|=\|A\setminus B\|</math>


			*דרך נוספת לזו המופיעה בסרטון:
			**בהמשך נוכיח כי לכל קבוצה אינסופית <math>B</math> מתקיים כי <math>\|B\|+\|B\|=\|B\|</math>
			**לכן <math>\|A\|\leq \|A\cup B\|=\|A\|+\|B\setminus A\|\leq \|A\|+\|A\|=\|A\|</math> ולפי ק.ש.ב <math>\|A\|=\|A\cup B\|</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>\|A\|=\|A\setminus B\|+\|B\cap A\|=\|A\setminus B\|</math>

ארז שיינר: /* עוצמה כפול עצמה */

2022-08-16T17:55:31Z

עוצמה כפול עצמה

→ הגרסה הקודמת		גרסה מ־17:55, 16 באוגוסט 2022
שורה 556:		שורה 556:
	*אם <math>\|B\setminus D\|\geq \|D\|</math> נראה כי נגיע לסתירה, ולכן מקרה זה בלתי אפשרי:		*אם <math>\|B\setminus D\|\geq \|D\|</math> נראה כי נגיע לסתירה, ולכן מקרה זה בלתי אפשרי:
	**ניקח תת קבוצה <math>U\subseteq B\setminus D</math> כך ש <math>\|U\|=\|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>\|(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>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=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> ולהגדיל אותה, בסתירה למקסימליות שלה.		**ניתן להוסיף את <math>h</math> לשרשרת <math>M</math> ולהגדיל אותה, בסתירה למקסימליות שלה.

ארז שיינר: /* עוצמה כפול עצמה */

2022-08-16T17:52:37Z

עוצמה כפול עצמה

→ הגרסה הקודמת		גרסה מ־17:52, 16 באוגוסט 2022
שורה 521:		שורה 521:
	*הוכחה:		*הוכחה:
	*תהי <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>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>X\subseteq B</math> כך ש <math>\|X\|=\aleph_0</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:X\times X\to X</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>S</math>. לפי עקרון המקסימום של האוסדורף, קיימת שרשרת מקסימלית <math>\{R\}\subseteq M\subseteq S</math>.
	*נסמן ב<math>f</math> את האיחוד הכללי של השרשרת <math>f=\cup_{T\in M} T</math>.		*נסמן ב<math>f</math> את האיחוד הכללי של השרשרת <math>f=\cup_{T\in M} T</math>.
שורה 544:		שורה 544:
	**לכן קיים <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>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>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> ולהגדיל אותה, בסתירה למקסימליות שלה.

ארז שיינר: /* סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות */

2022-08-16T17:39:38Z

סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות

→ הגרסה הקודמת		גרסה מ־17:39, 16 באוגוסט 2022
שורה 514:		שורה 514:
	<videoflash>Ty-lY6-uRPo</videoflash>		<videoflash>Ty-lY6-uRPo</videoflash>


			====עוצמה כפול עצמה====
			*תהי קבוצה אינסופית <math>B</math> אזי <math>B\times B\sim B</math>


	*תהי קבוצה אינסופית <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>S</math> קבוצת כל היחסים <math>R\subseteq (B\times B)\times B</math>, כך שקיימת תת קבוצה <math>X\subseteq B</math> כך ש <math>R:X\times X\to X</math> פונקציה הפיכה.
שורה 524:		שורה 526:
	*נסמן ב<math>f</math> את האיחוד הכללי של השרשרת <math>f=\cup_{T\in M} T</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>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>f\in S</math> פונקציה הפיכה <math>f:D\times D\to D</math> עבור תת קבוצה <math>D\subseteq B</math>:

ארז שיינר: /* סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות */

2022-08-16T17:38:13Z

סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות

→ הגרסה הקודמת		גרסה מ־17:38, 16 באוגוסט 2022
שורה 524:		שורה 524:
	*נסמן ב<math>f</math> את האיחוד הכללי של השרשרת <math>f=\cup_{T\in M} T</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>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> היא פונקציה (יחס ח"ע ושלם) חח"ע, נותר להוכיח כי היא על:
			**

ארז שיינר: /* סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות */

2022-08-16T17:20:05Z

סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות

→ הגרסה הקודמת		גרסה מ־17:20, 16 באוגוסט 2022
שורה 516:		שורה 516:


	*תהי ~~עוצמה~~ אינסופית b אזי <math>b\~~cdot b~~=b</math>		*תהי קבוצה אינסופית <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>X\subseteq B</math> כך ש <math>\|X\|=\aleph_0</math>.
			*כיוון ש <math>\aleph_0\times\aleph_0=\aleph_0</math> קיימת פונקציה הפיכה <math>R:X\times X\to X</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> וכך נסיים את ההוכחה.

ארז שיינר: /* פרק 5 - עוצמות */

2022-08-16T17:06:58Z

פרק 5 - עוצמות

@@ שורה 436: / שורה 436: @@
 ***הוכחה דומה לח"ע
 ===איחוד בן מנייה של קבוצות בנות מנייה===
@@ שורה 490: / שורה 470: @@
 <videoflash>XZkMt26fQyE</videoflash>
 ===סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות===

→ הגרסה הקודמת		גרסה מ־18:05, 16 באוגוסט 2022
שורה 492:		שורה 492:

	*דרך נוספת לזו המופיעה בסרטון:		*דרך נוספת לזו המופיעה בסרטון:
	**בהמשך נוכיח כי לכל קבוצה אינסופית <math>B</math> מתקיים כי <math>\|B\|+\|B\|=\|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>\|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\|=\|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>\|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>		**לכן לפי ק.ש.ב <math>\|A\|=\|A\setminus B\|+\|B\cap A\|=\|A\setminus B\|</math>