(←אלף אפס היא העוצמה האינסופית הקטנה ביותר) |
(←חומר עזר) |
||
(23 גרסאות ביניים של 2 משתמשים אינן מוצגות) | |||
שורה 2: | שורה 2: | ||
*[[מדיה:16BdidaOrit.pdf|סיכומי ההרצאות של ד״ר ארז שיינר, ע״י אורית חסון, קיץ 2016]] | *[[מדיה:16BdidaOrit.pdf|סיכומי ההרצאות של ד״ר ארז שיינר, ע״י אורית חסון, קיץ 2016]] | ||
*[[מבחנים בבדידה]] | *[[מבחנים בבדידה]] | ||
+ | *[[בחנים בבדידה]] | ||
*[[מבחנים בקורס בדידה למורים]] - שימו לב, הקורס למורים מכיל משמעותית פחות חומר, והמבחנים קלים יותר. יחד עם זאת, יש שם כמות גדולה של תרגילים רלוונטיים ברמה נמוכה. | *[[מבחנים בקורס בדידה למורים]] - שימו לב, הקורס למורים מכיל משמעותית פחות חומר, והמבחנים קלים יותר. יחד עם זאת, יש שם כמות גדולה של תרגילים רלוונטיים ברמה נמוכה. | ||
=סרטוני ותקציר הרצאות= | =סרטוני ותקציר הרצאות= | ||
+ | |||
+ | |||
+ | [https://www.youtube.com/playlist?list=PLHinTfsAOC-vhY2xtz4MJzkm5tefKT3Dg פלייליסט של כל הסרטונים] | ||
+ | |||
==פרק 1 - מבוא ללוגיקה מתמטית== | ==פרק 1 - מבוא ללוגיקה מתמטית== | ||
+ | |||
+ | |||
===פסוקים, קשרים, כמתים, פרדיקטים=== | ===פסוקים, קשרים, כמתים, פרדיקטים=== | ||
שורה 29: | שורה 36: | ||
<videoflash>n6xkPhKmhQo</videoflash> | <videoflash>n6xkPhKmhQo</videoflash> | ||
+ | |||
+ | |||
+ | *דוגמא: | ||
+ | *<math>\sum_{k=1}^{2^{n-1}}\frac{1}{k} > \frac{n}{2}</math> | ||
+ | |||
*אינדוקציה שלמה (מלאה) | *אינדוקציה שלמה (מלאה) | ||
שורה 139: | שורה 151: | ||
**<math>\cup_{X\in U}X=A</math> | **<math>\cup_{X\in U}X=A</math> | ||
**<math>\emptyset\notin U</math> | **<math>\emptyset\notin U</math> | ||
− | **לכל <math>X_1,X_2\in U</math> אם <math>X_1\cap X_2\neq \emptyset</math> אזי <math>X_1= | + | **לכל <math>X_1,X_2\in U</math> אם <math>X_1\cap X_2\neq \emptyset</math> אזי <math>X_1=X_2</math> |
שורה 367: | שורה 379: | ||
<videoflash>qDGHoXKOpzk</videoflash> | <videoflash>qDGHoXKOpzk</videoflash> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
===אקסיומת הבחירה ועקרון המקסימום של האוסדורף=== | ===אקסיומת הבחירה ועקרון המקסימום של האוסדורף=== | ||
====אקסיומת הבחירה==== | ====אקסיומת הבחירה==== | ||
− | *תהי S קבוצת | + | *תהי 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> | ||
שורה 394: | שורה 395: | ||
*תהיינה <math>A,B\neq\emptyset</math> אזי <math>|A|\leq |B|</math> אם ורק אם קיימת <math>g:B\to A</math> על. | *תהיינה <math>A,B\neq\emptyset</math> אזי <math>|A|\leq |B|</math> אם ורק אם קיימת <math>g:B\to A</math> על. | ||
+ | |||
+ | |||
+ | *בכיוון ראשון: | ||
+ | **תהי <math>f:A\to B</math> חח"ע | ||
+ | **כיוון ש<math>A\neq \emptyset</math> קיים <math>a\in A</math> | ||
+ | **נגדיר פונקציה <math>g:B\to A</math> באופן הבא: | ||
+ | ***לכל <math>b\in B</math> | ||
+ | ***אם קיים <math>x\in A</math> כך ש <math>f(x)=b</math> נגדיר <math>f(b)=x</math> (בגלל החח"ע זה מוגדר היטב) | ||
+ | ***אם <math>b\not\in Im(f)</math> נגדיר <math>f(b)=a</math> | ||
+ | **הפונקציה <math>g</math> שהגדרנו היא אכן על, כי לכל <math>x\in A</math> מתקיים כי <math>g(f(x))=x</math> | ||
+ | *בכיוון שני: | ||
+ | **תהי <math>g:B\to A</math> על, אזי כל הקבוצות באוסף <math>U=\left\{g^{-1}[\{a\}]|a\in A\right\}</math> אינן ריקות. | ||
+ | **ניקח פונקצית בחירה <math>h:U\to B</math> ונגדיר <math>f:A\to B</math> ע"י <math>f(a)=h(g^{-1}[\{a\}])</math> | ||
+ | **אכן <math>f</math> חח"ע כי אם <math>f(a_1)=f(a_2)=b</math> אזי <math>b\in g^{-1}[\{a_1\}]</math> וכן <math>b\in g^{-1}[\{a_2\}]</math> | ||
+ | **ולכן <math>g(b)=a_1</math> וכן <math>g(b)=a_2</math>, כלומר <math>a_1=a_2</math> | ||
+ | |||
<videoflash>Dl6sgVGZksk</videoflash> | <videoflash>Dl6sgVGZksk</videoflash> | ||
שורה 408: | שורה 425: | ||
<videoflash>O_uDtoDRRZ8</videoflash> | <videoflash>O_uDtoDRRZ8</videoflash> | ||
− | |||
− | |||
− | *תהי | + | *טענות שימושיות להמשך: |
+ | *תהי <math>U</math> קבוצה של יחסים מ<math>A</math> ל <math>B</math>, תהי <math>M\subseteq U</math> שרשרת ביחס ההכלה ונסמן את האיחוד הכללי של השרשרת ב<math>f=\cup_{R\in M} R</math> | ||
+ | *אזי: | ||
+ | **אם כל היחסים ב<math>M</math> ח"ע, אז גם <math>f</math> ח"ע | ||
+ | ***אכן, יהיו <math>(a,b_1),(a,b_2)\in f</math> | ||
+ | ***לכן קיימים <math>R_1,R_2\in M</math> כך ש <math>(a,b_1)\in R_1</math> וכן <math>(a,b_2)\in R_2</math> | ||
+ | ***כיוון ש<math>M</math> שרשרת, אזי <math>R_1\subseteq R_2</math> (או ההפך) ולכן <math>(a,b_1),(a,b_2)\in R_2</math> | ||
+ | ***כיוון ש<math>R_2</math> ח"ע נובע כי <math>b_1=b_2</math> כפי שרצינו. | ||
+ | **אם כל היחסים ב<math>M</math> חח"ע, אזי גם <math>f</math> חח"ע | ||
+ | ***הוכחה דומה לח"ע | ||
− | |||
+ | ===איחוד בן מנייה של קבוצות בנות מנייה=== | ||
+ | (בהנחת אקסיומת הבחירה) | ||
− | *תהי | + | *תהי S קבוצה בת מנייה של קבוצות בנות מנייה, כלומר: |
− | **<math>| | + | **<math>|S|\leq\aleph_0</math> |
+ | **<math>\forall X\in S:|X|\leq\aleph_0</math> | ||
+ | *אזי גם האיחוד הכללי הוא בן מנייה: | ||
+ | **<math>|\cup_{X\in S}X|\leq \aleph_0</math> | ||
− | <videoflash> | + | *מסקנה: אוסף תתי הקבוצות הסופיות של המספרים הטבעיים הוא בן מנייה. |
+ | |||
+ | |||
+ | *הערה לסרטון: אנחנו משתמשים באקסיומת הבחירה כאשר "בוחרים" את הפונקציות החח"ע מהקבוצות באוסף אל הטבעיים. | ||
+ | |||
+ | |||
+ | <videoflash>0S6r0s2SnNc</videoflash> | ||
===השוואת עוצמות=== | ===השוואת עוצמות=== | ||
שורה 426: | שורה 460: | ||
*תהיינה שתי קבוצות A,B אזי <math>|A|\leq|B|</math> או <math>|A|\geq |B|</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> | <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> | ||
===סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות=== | ===סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות=== | ||
שורה 440: | שורה 514: | ||
*ולכן לפי משפט ק.ש.ב נקבל כי | *ולכן לפי משפט ק.ש.ב נקבל כי | ||
**<math>a+b=a\cdot b = b</math> | **<math>a+b=a\cdot b = b</math> | ||
+ | |||
+ | |||
+ | *דוגמא - מה היא עוצמת קבוצת המספרים האי-רציונאליים? | ||
+ | *<math>\mathbb{R}=\mathbb{Q}\cup (\mathbb{R}\setminus\mathbb{Q})</math> (איחוד זר כמובן) | ||
+ | *לכן <math>|\mathbb{R}|=|\mathbb{Q}|+ |(\mathbb{R}\setminus\mathbb{Q})|</math> | ||
+ | *לכן <math>\aleph=\aleph_0 +|(\mathbb{R}\setminus\mathbb{Q})|</math> | ||
+ | *לפי המשפט לעיל, סכום העוצמות הוא העוצמה הגדולה מבין השתיים. | ||
+ | *כיוון ש <math>\aleph\neq \aleph_0</math> נקבל כי <math>|(\mathbb{R}\setminus\mathbb{Q})|=\aleph</math> | ||
שורה 445: | שורה 527: | ||
− | *תהי | + | ====עוצמה כפול עצמה==== |
+ | *תהי קבוצה אינסופית <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> ולהגדיל אותה, בסתירה למקסימליות שלה. | ||
+ | |||
+ | |||
גרסה אחרונה מ־07:35, 18 ביולי 2023
חומר עזר
- סיכומי ההרצאות של ד״ר ארז שיינר, ע״י אורית חסון, קיץ 2016
- מבחנים בבדידה
- בחנים בבדידה
- מבחנים בקורס בדידה למורים - שימו לב, הקורס למורים מכיל משמעותית פחות חומר, והמבחנים קלים יותר. יחד עם זאת, יש שם כמות גדולה של תרגילים רלוונטיים ברמה נמוכה.
סרטוני ותקציר הרצאות
פרק 1 - מבוא ללוגיקה מתמטית
פסוקים, קשרים, כמתים, פרדיקטים
תרגול
אינדוקציה
- משפט האינדוקציה המתמטית
- תהי סדרת טענות כך שמתקיימים שני התנאים הבאים:
- הטענה הראשונה נכונה.
- לכל
אם הטענה הn מתקיימת אז גם הטענה הn+1 מתקיימת.
- אזי כל הטענות בסדרה נכונות
- דוגמא:
- אינדוקציה שלמה (מלאה)
- תהי סדרת טענות כך ש:
- לכל
אם כל הטענות עד ולא כולל הטענה הn מתקיימות, אזי גם הטענה הn מתקיימת.
- לכל
- אזי כל הטענות בסדרה מתקיימות.
- שימו לב: לפני הטענה הראשונה אין טענות, ולכן כולן מתקיימות באופן ריק. כלומר מנוסח התנאי נובע שצריך להוכיח שהטענה הראשונה מתקיימת.
- פרדוקס הסוסים (או פתיתי השלג)
תרגול
פרק 2 - מבוא לתורת הקבוצות
קבוצות ופעולות על קבוצות
- איבר שייך לקבוצה
אם הוא אחד האיברים בקבוצה.
- קבוצה מוכלת בקבוצה אחרת
אם
- תהי קבוצה
ותהיינה
. נגדיר את:
- קבוצת האיחוד
- קבוצת החיתוך
- קבוצת ההפרש
- קבוצת ההפרש הסימטרי
- קבוצת המשלים
- קבוצת האיחוד
שיטות הוכחה בסיסיות
- הוכחת טענות מכומתות - טענות 'לכל' וטענות 'קיים'
- הוכחת הכלה בין קבוצות, ושיוויון בין קבוצות
איחוד וחיתוך כלליים
- תהי S קבוצה של קבוצות, נגדיר:
קבוצת החזקה
תרגול
פרק 3 - יחסים
מכפלה קרטזית ויחסים
תכונות של יחסים
- יהי R יחס על A (כלומר
) אזי:
- R נקרא רפלקסיבי אם לכל
מתקיים
.
- R נקרא סימטרי אם לכל
המקיימים
מתקיים
- R נקרא אנטי-סימטרי אם לכל
המקיימים
מתקיים
- R נקרא טרנזיטיבי אם לכל
המקיימים
מתקיים
- R נקרא מלא אם לכל
מתקיים כי
- R נקרא רפלקסיבי אם לכל
- יהי R יחס מA לB (כלומר
) אזי:
- R נקרא חד-ערכי (ח"ע) אם לכל
ולכל
המקיימים
מתקיים
- R נקרא שלם אם לכל
קיים
כך ש
- R נקרא חד-חד-ערכי (חח"ע) אם לכל
ולכל
המקיימים
מתקיים
- R נקרא על אם לכל
קיים
כך ש
- R נקרא חד-ערכי (ח"ע) אם לכל
יחסי שקילות
- יחס R על קבוצה A נקרא יחס שקילות אם הוא רפלקסיבי, סימטרי וטרנזיטיבי.
- יהי R יחס שקילות על A.
- לכל
מוגדרת קבוצת מחלקת השקילות של a ע"י:
- קבוצת כל קבוצות מחלקות השקילות נקראת קבוצת המנה:
- תהי קבוצה A. קבוצת תתי קבוצות
נקראת חלוקה של A אם:
- לכל
אם
אזי
- היחס המושרה מחלוקה:
- תהי קבוצה A ותהי חלוקה שלה U. נגדיר יחס R על A על ידי:
אם ורק אם קיימת
כך ש
- היחס המושרה מחלוקה הוא יחס שקילות.
- קבוצת המנה היא חלוקה של A.
- היחס המושרה מקבוצת המנה, הוא יחס השקילות המקורי; קבוצת המנה של יחס שקילות מושרה היא החלוקה המקורית.
תרגול
יחסי סדר
- יחס R על קבוצה A נקרא יחס סדר חלקי אם הוא רפלקסיבי, אנטי-סימטרי וטרנזיטיבי
איברים מינימליים ומקסימליים, וחסמים
- יהי R יחס סדר חלקי על קבוצה X, ותהי
תת קבוצה.
- איבר
נקרא מקסימלי בA אם לכל
המקיים
מתקיים כי
(אין גדולים ממנו)
- איבר
נקרא מינימלי בA אם לכל
המקיים
מתקיים כי
(אין קטנים ממנו)
- איבר
נקרא הגדול ביותר (מקסימום) בA אם לכל
מתקיים
(הוא גדול מכולם)
- איבר
נקרא הקטן ביותר (מינימום) בA אם לכל
מתקיים
(הוא קטן מכולם)
- איבר
נקרא חסם מלעיל של A אם לכל
מתקיים
(הוא גדול מכל איברי הקבוצה, אבל לאו דווקא נמצא בקבוצה)
- איבר
נקרא חסם מלרע של A אם לכל
מתקיים
(הוא קטן מכל איברי הקבוצה, אבל לאו דווקא נמצא בקבוצה)
- אם בקבוצת חסמי המלעיל של A יש איבר קטן ביותר הוא נקרא חסם עליון (supremum) של A.
- אם בקבוצת חסמי המלרע של A יש איבר גדול ביותר הוא נקרא חסם תחתון (infimum) של A.
- איבר
- איבר גדול ביותר ביותר הוא יחיד.
- אם חסם מלעיל שייך לקבוצה, אז הוא הגדול ביותר.
- האיבר הגדול ביותר בקבוצה הוא איבר מקסימלי, ואין איברים מקסימליים אחרים.
- האם תתכן קבוצה עם איבר מקסימלי יחיד שאינו האיבר הגדול ביותר בקבוצה?
- ביחס ההכלה על קבוצת חזקה, האיחוד הכללי של קבוצת קבוצות הוא החסם העליון שלה, והחיתוך הכללי הוא החסם התחתון.
- ביחס 'מחלק את' על הטבעיים, המחלק המשותף המקסימלי הוא החסם התחתון, והמכפלה המשותפת המינימלית הוא החסם העליון.
שרשראות
- יחס סדר חלקי R על A נקרא מלא (או לינארי, או קווי) אם:
- יהי R יחס סדר חלקי על A, ותהי
.
- אזי
נקראת שרשרת אם היחס מלא עליה, כלומר
תרגול
פרק 4 - פונקציות
הגדרת פונקציות
- יחס f מA לB נקרא פונקציה אם הוא ח"ע ושלם, ומסמנים במקרה זה
, וכן
.
- A נקרא תחום הפונקציה (או תחום הגדרה), B נקרא הטווח של הפונקציה.
- שימו לב, הסרטון ישן, ושם פונקציה הוגדרה כיחס ח"ע בלבד, בניגוד להגדרה העדכנית שלנו בקורס.
חח"ע ועל, תמונה ותמונה הפוכה
- תהי
פונקציה. אזי:
- f חח"ע אם לכל
המקיימים
מתקיים כי
- f על אם לכל
קיים
כך ש
- תהי
נגדיר את קבוצת התמונה
- תהי
נגדיר את קבוצת התמונה ההפוכה
היא פונקצית התמונה, השולחת כל תת קבוצה לקבוצת התמונה שלה
היא פונקצית התמונה ההפוכה, השולחת כל תת קבוצה לקבוצת התמונה ההפוכה שלה
- f חח"ע אם לכל
- שימו לב
הרכבת פונקציות, פונקציות הפיכות
- תהיינה
וכן
אזי נגדיר את פונקצית ההרכבה
ע"י
- פעולת ההרכבה היא אסוציאטיבית.
- תהי קבוצה A נגדיר את פונקצית הזהות
ע"י
.
- לכל פונקציה
מתקיים כי
- פונקציה
נקראת הפיכה אם קיימות פונקציות
כך ש:
וכן
- נשים לב כי
- לכן אם פונקציה הפיכה, יש פונקציה יחידה שהופכת אותה (ההופכית), נסמנה
.
- שימו לב: עם סוגריים מרובעים זו פונקצית התמונה ההפוכה שיש לכל פונקציה ופועלת על תתי קבוצות, עם סוגריים עגולים זו הפונקציה ההופכית שיש רק להפיכות ופועלת על איברים.
פונקציה מוגדרת היטב
תרגול
פרק 5 - עוצמות
מבוא
השוואת עוצמות
- A שקולת עוצמה לB או עוצמתה של A שווה לB, אם קיימת פונקציה הפיכה (חח"ע ועל)
.
- במקרה זה מסמנים
או
.
- כל קבוצה שקולת עוצמה לעצמה
- אם A שקולת עוצמה לB, גם B שקולת עוצמה לA
- אם A שקולת עוצמה לB וB שקולת עוצמה לC אזי A שקולת עוצמה לC
- עוצמתה של A קטנה או שווה לזו של B, אם קיימת פונקציה חח"ע
.
- במקרה זה מסמנים
- כל קבוצה A השקולת עוצמה לקבוצת הטבעיים מסומנת
- כל קבוצה A השקולת עוצמה לקבוצת הממשיים מסומנת
משפט קנטור
קבוצות בנות מנייה
- קבוצה A נקראת בת מנייה אם
- כל קבוצה A בת מנייה אינסופית מקיימת
חשבון עוצמות (אריתמטיקה של עוצמות)
חיבור עוצמות
- תהיינה שתי עוצמות a,b ותהיינה שתי נציגות זרות לעוצמות A,B.
- נגדיר
, הגדרה זו אינה תלוייה בבחירת הנציגות.
כפל עוצמות
- תהיינה שתי עוצמות a,b ותהיינה שתי נציגות לעוצמות A,B.
- נגדיר
, הגדרה זו אינה תלוייה בבחירת הנציגות.
חזקת עוצמות
- תהיינה שתי עוצמות a,b ותהיינה שתי נציגות לעוצמות A,B.
- נגדיר את
להיות אוסף כל הפונקציות מB לA (מהמעריך לבסיס).
- נגדיר
, הגדרה זו אינה תלוייה בבחירת הנציגות.
- חוקי חזקות
- תהיינה עוצמות a,b,c אזי
עוצמת קבוצת החזקה
השוואת חשבון עוצמות
- תהיינה עוצמות a,b,c,d כך ש
וכן
אזי:
- אם בנוסף נתון כי
אזי
משפט קנטור-שרדר-ברנשטיין
- אם
וגם
אזי
למת נקודת השבת
- תהי פונקציה עולה
כלומר המקיימת לכל
כי
- אזי קיימת נק' שבת
כך ש
.
הוכחת המשפט
עוצמות קטעים ממשיים
אקסיומת הבחירה ועקרון המקסימום של האוסדורף
אקסיומת הבחירה
- תהי S קבוצת קבוצות לא ריקות, ונסמן את האיחוד הכללי ב
.
- אזי קיימת פונקצית בחירה
הבוחרת איבר מתוך כל קבוצה, כלומר:
- דוגמא:
- תהי פונקציה על
אזי קיימת תת קבוצה
כך ש
חח"ע ועל.
- תהי פונקציה על
- תהיינה
אזי
אם ורק אם קיימת
על.
- בכיוון ראשון:
- תהי
חח"ע
- כיוון ש
קיים
- נגדיר פונקציה
באופן הבא:
- לכל
- אם קיים
כך ש
נגדיר
(בגלל החח"ע זה מוגדר היטב)
- אם
נגדיר
- לכל
- הפונקציה
שהגדרנו היא אכן על, כי לכל
מתקיים כי
- תהי
- בכיוון שני:
- תהי
על, אזי כל הקבוצות באוסף
אינן ריקות.
- ניקח פונקצית בחירה
ונגדיר
ע"י
- אכן
חח"ע כי אם
אזי
וכן
- ולכן
וכן
, כלומר
- תהי
עקרון המקסימום של האוסדורף
- תהי קבוצה A עם יחס סדר חלקי, תת קבוצה
נקראת שרשרת אם היחס מלא עליה (ניתן להשוות בין כל שני איברים בS).
- שרשרת נקראת מקסימלית בA אם היא אינה מוכלת באף שרשרת אחרת.
- עקרון המקסימום של האוסדורף אומר שכל שרשרת מוכלת בשרשרת מקסימלית.
- דוגמא - אוסף עיגולים במישור שאינם חותכים זה את זה, ולא ניתן להוסיף אפילו עיגול אחד נוסף.
- טענות שימושיות להמשך:
- תהי
קבוצה של יחסים מ
ל
, תהי
שרשרת ביחס ההכלה ונסמן את האיחוד הכללי של השרשרת ב
- אזי:
- אם כל היחסים ב
ח"ע, אז גם
ח"ע
- אכן, יהיו
- לכן קיימים
כך ש
וכן
- כיוון ש
שרשרת, אזי
(או ההפך) ולכן
- כיוון ש
ח"ע נובע כי
כפי שרצינו.
- אכן, יהיו
- אם כל היחסים ב
חח"ע, אזי גם
חח"ע
- הוכחה דומה לח"ע
- אם כל היחסים ב
איחוד בן מנייה של קבוצות בנות מנייה
(בהנחת אקסיומת הבחירה)
- תהי S קבוצה בת מנייה של קבוצות בנות מנייה, כלומר:
- אזי גם האיחוד הכללי הוא בן מנייה:
- מסקנה: אוסף תתי הקבוצות הסופיות של המספרים הטבעיים הוא בן מנייה.
- הערה לסרטון: אנחנו משתמשים באקסיומת הבחירה כאשר "בוחרים" את הפונקציות החח"ע מהקבוצות באוסף אל הטבעיים.
השוואת עוצמות
(בהנחת עיקרון המקסימום של האוסדורף)
- תהיינה שתי קבוצות A,B אזי
או
- נביט ב
אוסף היחסים הח"ע והחח"ע מ
ל
, וניקח שרשרת מקסימלית ביחס ההכלה
- נסמן ב
את האיחוד הכללי על השרשרת
- ראינו שנובע במקרה זה כי
יחס ח"ע וחח"ע מ
ל
.
- אם
שלם, אזי
פונקציה חח"ע ולכן
- אם
על, אזי
פונקציה על עבור
ולכן
- אחרת, קיים זוג
כך ש
יחס ח"ע וחח"ע שניתן להוסיף לשרשרת
בסתירה למקסימליות שלה.
- אם
אלף אפס היא העוצמה האינסופית הקטנה ביותר
(בהנחת עקרון המקסימום של האוסדורף)
- תהי A קבוצה אינסופית, אזי
- דרך נוספת לזו המופיעה בסרטון:
- נוכיח בהמשך כי ניתן להשוות עוצמה בין כל שתי קבוצות
- אם
, כיוון ש
אינסופית נובע כי
- אחרת,
ולכן
כפי שרצינו.
- תהי A קבוצה אינסופית, ותהי B קבוצה סופית, אזי:
- דרך נוספת לזו המופיעה בסרטון:
- בהמשך נוכיח כי לכל קבוצה אינסופית
מתקיים כי
- לכן
ולפי ק.ש.ב
.
- שימו לב כי
סופית ולכן קטנה יותר מהקבוצה האינסופית
.
- שימו לב כי
- כמו כן
- כעת
.
- שימו לב כי
סופית ולכן קטנה יותר מהקבוצה האינסופית
.
- שימו לב כי
- לכן לפי ק.ש.ב
- בהמשך נוכיח כי לכל קבוצה אינסופית
סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות
- תהיינה עוצמות
אזי:
- נניח בנוסף כי
אזי:
- נניח בנוסף כי b אינסופית, ונקבל ביחד
(המעבר
מוכח בסרטון השני).
- ולכן לפי משפט ק.ש.ב נקבל כי
- דוגמא - מה היא עוצמת קבוצת המספרים האי-רציונאליים?
(איחוד זר כמובן)
- לכן
- לכן
- לפי המשפט לעיל, סכום העוצמות הוא העוצמה הגדולה מבין השתיים.
- כיוון ש
נקבל כי
עוצמה כפול עצמה
- תהי קבוצה אינסופית
אזי
- הוכחה:
- תהי
קבוצת כל היחסים
, כך שקיימת תת קבוצה
כך ש
פונקציה הפיכה.
- כיוון ש
אינסופית, יש לה תת קבוצה
כך ש
.
- כיוון ש
קיימת פונקציה הפיכה
.
- נביט ביחס ההכלה על
. לפי עקרון המקסימום של האוסדורף, קיימת שרשרת מקסימלית
.
- נסמן ב
את האיחוד הכללי של השרשרת
.
- נוכיח כי קיימת
כך ש
פונקציה הפיכה, ואף
וכך נסיים את ההוכחה.
- הוכחה כי
פונקציה הפיכה
עבור תת קבוצה
:
- ראשית, נגדיר את
- נוכיח כי
:
- יהי זוג
, לפי ההגדרה
- כמו כן, לפי הגדרת האיחוד קיים
כך ש
.
- קיימת
כך ש
פונקציה הפיכה.
- כיוון ש
על, לכל
קיימים
כך ש
ולכן
ולכן
- ביחד עם העובדה ש
נובע כי
- יהי זוג
- כיוון שכל איברי השרשרת הם יחסים ח"ע, גם
ח"ע.
- כיוון שכל איברי השרשרת הם יחסים חח"ע, גם
חח"ע.
- כעת נוכיח כי
יחס שלם:
- יהיו
.
- ראינו כי קיימים
ואיברים
כך ש
וכן
- כיוון ש
שרשרת,
(או ההפך) ולכן
עבור תת קבוצה
כך ש
פונקציה הפיכה.
- לכן קיים
כך ש
ולכן
כלומר
שלם.
- יהיו
- הוכחנו כי
היא פונקציה (יחס ח"ע ושלם) חח"ע, נותר להוכיח כי היא על:
- יהי
. ראינו כי קיים
וקיימים
כך ש
ולכן
ולכן הפונקציה על.
- יהי
- הוכחה כי
:
- ראשית, נשים לב כי
כיוון ש
פונקציה הפיכה וכן
, ולכן
אינסופית.
- כעת, נזכור שהוכחנו כי
.
- נביט ב
ונחלק למקרים:
- אם
אזי:
- כמובן ש
ולפי ק.ש.ב נסיק כי במקרה זה
וסיימנו.
- אם
נראה כי נגיע לסתירה, ולכן מקרה זה בלתי אפשרי:
- ניקח תת קבוצה
כך ש
.
- לכן
(הרי ראינו מקודם כי
)
- לכן קיימת פונקציה הפיכה
.
- האיחוד
הוא פונקציה הפיכה
, ולכן
.
- ניתן להוסיף את
לשרשרת
ולהגדיל אותה, בסתירה למקסימליות שלה.
- ניקח תת קבוצה
הקשר בין עוצמת הטבעיים לעוצמת הממשיים
כלומר