הבדלים בין גרסאות בדף "מתמטיקה בדידה - ארז שיינר"
מתוך Math-Wiki
(←סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות) |
(←סרטוני ותקציר הרצאות) |
||
(38 גרסאות ביניים של 2 משתמשים אינן מוצגות) | |||
שורה 2: | שורה 2: | ||
*[[מדיה:16BdidaOrit.pdf|סיכומי ההרצאות של ד״ר ארז שיינר, ע״י אורית חסון, קיץ 2016]] | *[[מדיה:16BdidaOrit.pdf|סיכומי ההרצאות של ד״ר ארז שיינר, ע״י אורית חסון, קיץ 2016]] | ||
*[[מבחנים בבדידה]] | *[[מבחנים בבדידה]] | ||
+ | *[[מבחנים בקורס בדידה למורים]] - שימו לב, הקורס למורים מכיל משמעותית פחות חומר, והמבחנים קלים יותר. יחד עם זאת, יש שם כמות גדולה של תרגילים רלוונטיים ברמה נמוכה. | ||
=סרטוני ותקציר הרצאות= | =סרטוני ותקציר הרצאות= | ||
+ | |||
+ | |||
+ | [https://www.youtube.com/playlist?list=PLHinTfsAOC-vhY2xtz4MJzkm5tefKT3Dg פלייליסט של כל הסרטונים] | ||
+ | |||
==פרק 1 - מבוא ללוגיקה מתמטית== | ==פרק 1 - מבוא ללוגיקה מתמטית== | ||
+ | |||
+ | |||
===פסוקים, קשרים, כמתים, פרדיקטים=== | ===פסוקים, קשרים, כמתים, פרדיקטים=== | ||
שורה 19: | שורה 26: | ||
===אינדוקציה=== | ===אינדוקציה=== | ||
+ | |||
+ | *משפט האינדוקציה המתמטית | ||
+ | *תהי סדרת טענות כך שמתקיימים שני התנאים הבאים: | ||
+ | **הטענה הראשונה נכונה. | ||
+ | **לכל <math>n\in \mathbb{N}</math> אם הטענה הn מתקיימת אז גם הטענה הn+1 מתקיימת. | ||
+ | *אזי כל הטענות בסדרה נכונות | ||
+ | |||
<videoflash>n6xkPhKmhQo</videoflash> | <videoflash>n6xkPhKmhQo</videoflash> | ||
+ | |||
+ | *אינדוקציה שלמה (מלאה) | ||
+ | *תהי סדרת טענות כך ש: | ||
+ | **לכל <math>n\in \mathbb{N}</math> אם כל הטענות עד ולא כולל הטענה הn מתקיימות, אזי גם הטענה הn מתקיימת. | ||
+ | *אזי כל הטענות בסדרה מתקיימות. | ||
+ | *שימו לב: לפני הטענה הראשונה אין טענות, ולכן כולן מתקיימות באופן ריק. כלומר מנוסח התנאי נובע שצריך להוכיח שהטענה הראשונה מתקיימת. | ||
+ | |||
<videoflash>BBUxvnjuA04</videoflash> | <videoflash>BBUxvnjuA04</videoflash> | ||
+ | |||
+ | |||
+ | *פרדוקס הסוסים (או פתיתי השלג) | ||
+ | |||
<videoflash>E0rf-Cg3IVM</videoflash> | <videoflash>E0rf-Cg3IVM</videoflash> | ||
שורה 30: | שורה 55: | ||
====תרגול==== | ====תרגול==== | ||
*[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 1.5|תרגול בנושא אינדוקציה]] | *[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 1.5|תרגול בנושא אינדוקציה]] | ||
− | *[[מכינה למתמטיקה קיץ תשעב/תרגילים/4|תרגילי אינדוקציה נוספים]] ו[[מכינה למתמטיקה קיץ תשעב/תרגילים/4/פתרון 4| | + | *[[מכינה למתמטיקה קיץ תשעב/תרגילים/4|תרגילי אינדוקציה נוספים]] ו[[מכינה למתמטיקה קיץ תשעב/תרגילים/4/פתרון 4|פתרונותיהם]] |
==פרק 2 - מבוא לתורת הקבוצות== | ==פרק 2 - מבוא לתורת הקבוצות== | ||
===קבוצות ופעולות על קבוצות=== | ===קבוצות ופעולות על קבוצות=== | ||
+ | |||
+ | *איבר שייך לקבוצה <math>a\in A</math> אם הוא אחד האיברים בקבוצה. | ||
+ | *קבוצה מוכלת בקבוצה אחרת <math>A\subseteq B</math> אם <math>\forall a\in A : a\in B</math> | ||
+ | |||
+ | |||
+ | *<math>\{1,2\}=\{2,1\}</math> | ||
+ | *<math>\{1,1,2\}=\{1,2\}</math> | ||
+ | |||
+ | |||
+ | *תהי קבוצה <math>U</math> ותהיינה <math>A,B\subseteq U</math>. נגדיר את: | ||
+ | **קבוצת האיחוד <math>A\cup B =\{ x\in U:x\in A \or x\in B\}</math> | ||
+ | **קבוצת החיתוך <math>A\cap B =\{ x\in U:x\in A \and x\in B\}</math> | ||
+ | **קבוצת ההפרש <math>A\setminus B =\{ x\in U:x\in A \and x\not\in B\}</math> | ||
+ | **קבוצת ההפרש הסימטרי <math>A\Delta B = (A\setminus B)\cup (B\setminus A)</math> | ||
+ | **קבוצת המשלים <math>\overline{A}=\{x\in U:x\not\in A\}</math> | ||
+ | |||
+ | |||
<videoflash>UgNl63BrzCM</videoflash> | <videoflash>UgNl63BrzCM</videoflash> | ||
שורה 40: | שורה 82: | ||
*[[שיטות הוכחה בסיסיות]] | *[[שיטות הוכחה בסיסיות]] | ||
+ | |||
+ | *הוכחת טענות מכומתות - טענות 'לכל' וטענות 'קיים' | ||
+ | |||
+ | |||
+ | <videoflash>QIwz6eyrcuI</videoflash> | ||
+ | |||
+ | |||
+ | *הוכחת הכלה בין קבוצות, ושיוויון בין קבוצות | ||
+ | |||
+ | |||
+ | <videoflash>Dts0NamGWbE</videoflash> | ||
===איחוד וחיתוך כלליים=== | ===איחוד וחיתוך כלליים=== | ||
+ | |||
+ | *תהי S קבוצה של קבוצות, נגדיר: | ||
+ | **<math>\cup_{A\in S}A = \{x|\exists A\in S :x\in A\}</math> | ||
+ | **<math>\cap_{A\in S}A = \{x|\forall A\in S :x\in A\}</math> | ||
+ | |||
+ | |||
<videoflash>xP9VIaCCH7A</videoflash> | <videoflash>xP9VIaCCH7A</videoflash> | ||
+ | |||
===קבוצת החזקה=== | ===קבוצת החזקה=== | ||
+ | |||
+ | *<math>X\in P(A) \iff X\subseteq A</math> | ||
+ | |||
<videoflash>uZVMvwbs5kw</videoflash> | <videoflash>uZVMvwbs5kw</videoflash> | ||
שורה 52: | שורה 115: | ||
===מכפלה קרטזית ויחסים=== | ===מכפלה קרטזית ויחסים=== | ||
<videoflash>wyDw5XXmPp8</videoflash> | <videoflash>wyDw5XXmPp8</videoflash> | ||
+ | |||
+ | |||
+ | ====תכונות של יחסים==== | ||
+ | *יהי R יחס על A (כלומר <math>R\subseteq A\times A</math>) אזי: | ||
+ | **R נקרא רפלקסיבי אם לכל <math>a\in A</math> מתקיים <math>aRa</math>. | ||
+ | **R נקרא סימטרי אם לכל <math>a,b\in A</math> המקיימים <math>aRb</math> מתקיים <math>bRa</math> | ||
+ | **R נקרא אנטי-סימטרי אם לכל <math>a,b\in A</math> המקיימים <math>aRb\and bRa</math> מתקיים <math>a=b</math> | ||
+ | **R נקרא טרנזיטיבי אם לכל <math>a,b,c\in A</math> המקיימים <math>aRb \and bRc</math> מתקיים <math>aRc</math> | ||
+ | **R נקרא מלא אם לכל <math>a,b\in A</math> מתקיים כי <math>aRb\or bRa</math> | ||
+ | |||
+ | |||
+ | *יהי R יחס מA לB (כלומר <math>R\subseteq A\times B</math>) אזי: | ||
+ | **R נקרא חד-ערכי (ח"ע) אם לכל <math>a\in A</math> ולכל <math>b_1,b_2\in B</math> המקיימים <math>aRb_1 \and aRb_2</math> מתקיים <math>b_1=b_2</math> | ||
+ | **R נקרא שלם אם לכל <math>a\in A</math> קיים <math>b\in B</math> כך ש <math>aRb</math> | ||
+ | **R נקרא חד-חד-ערכי (חח"ע) אם לכל <math>a_1,a_2\in A</math> ולכל <math>b\in B</math> המקיימים <math>a_1Rb\and a_2Rb</math> מתקיים <math>a_1=a_2</math> | ||
+ | **R נקרא על אם לכל <math>b\in B</math> קיים <math>a\in A</math> כך ש <math>aRb</math> | ||
===יחסי שקילות=== | ===יחסי שקילות=== | ||
+ | *יחס R על קבוצה A נקרא '''יחס שקילות''' אם הוא רפלקסיבי, סימטרי וטרנזיטיבי. | ||
+ | |||
+ | *יהי R יחס שקילות על A. | ||
+ | *לכל <math>a\in A</math> מוגדרת קבוצת '''מחלקת השקילות של a''' ע"י: | ||
+ | **<math>[a]_R=\{x\in A|aRx\}</math> | ||
+ | *קבוצת כל קבוצות מחלקות השקילות נקראת '''קבוצת המנה''': | ||
+ | **<math>A/R=\{[a]_R:a\in A\}</math> | ||
+ | |||
+ | |||
+ | *תהי קבוצה A. קבוצת תתי קבוצות <math>U\subseteq P(A)</math> נקראת '''חלוקה''' של A אם: | ||
+ | **<math>\cup_{X\in U}X=A</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=x_2</math> | ||
+ | |||
+ | |||
+ | *היחס המושרה מחלוקה: | ||
+ | *תהי קבוצה A ותהי חלוקה שלה U. נגדיר יחס R על A על ידי: | ||
+ | **<math>aRb</math> אם ורק אם קיימת <math>X\in U</math> כך ש<math>a,b\in X</math> | ||
+ | |||
+ | |||
+ | *היחס המושרה מחלוקה הוא יחס שקילות. | ||
+ | *קבוצת המנה היא חלוקה של A. | ||
+ | *היחס המושרה מקבוצת המנה, הוא יחס השקילות המקורי; קבוצת המנה של יחס שקילות מושרה היא החלוקה המקורית. | ||
+ | |||
+ | |||
<videoflash>jKprPSfRysE</videoflash> | <videoflash>jKprPSfRysE</videoflash> | ||
+ | |||
====תרגול==== | ====תרגול==== | ||
שורה 60: | שורה 165: | ||
===יחסי סדר=== | ===יחסי סדר=== | ||
+ | *יחס R על קבוצה A נקרא '''יחס סדר חלקי''' אם הוא רפלקסיבי, אנטי-סימטרי וטרנזיטיבי | ||
+ | |||
+ | |||
<videoflash>6X0OGf5CJrU</videoflash> | <videoflash>6X0OGf5CJrU</videoflash> | ||
+ | |||
====איברים מינימליים ומקסימליים, וחסמים==== | ====איברים מינימליים ומקסימליים, וחסמים==== | ||
+ | *יהי R יחס סדר חלקי על קבוצה X, ותהי <math>A\subseteq X</math> תת קבוצה. | ||
+ | **איבר <math>M\in A</math> נקרא '''מקסימלי''' בA אם לכל <math>a\in A</math> המקיים <math>MRa</math> מתקיים כי <math>a=M</math> (אין גדולים ממנו) | ||
+ | **איבר <math>m\in A</math> נקרא '''מינימלי''' בA אם לכל <math>a\in A</math> המקיים <math>aRm</math> מתקיים כי <math>a=m</math> (אין קטנים ממנו) | ||
+ | **איבר <math>M\in A</math> נקרא '''הגדול ביותר''' (מקסימום) בA אם לכל <math>a\in A</math> מתקיים <math>aRM</math> (הוא גדול מכולם) | ||
+ | **איבר <math>m\in A</math> נקרא '''הקטן ביותר''' (מינימום) בA אם לכל <math>a\in A</math> מתקיים <math>mRa</math> (הוא קטן מכולם) | ||
+ | **איבר <math>M\in X</math> נקרא '''חסם מלעיל''' של A אם לכל <math>a\in A</math> מתקיים <math>aRM</math> (הוא גדול מכל איברי הקבוצה, אבל לאו דווקא נמצא בקבוצה) | ||
+ | **איבר <math>m\in X</math> נקרא '''חסם מלרע''' של A אם לכל <math>a\in A</math> מתקיים <math>mRa</math> (הוא קטן מכל איברי הקבוצה, אבל לאו דווקא נמצא בקבוצה) | ||
+ | **אם בקבוצת חסמי המלעיל של A יש איבר קטן ביותר הוא נקרא '''חסם עליון''' (supremum) של A. | ||
+ | **אם בקבוצת חסמי המלרע של A יש איבר גדול ביותר הוא נקרא '''חסם תחתון''' (infimum) של A. | ||
+ | |||
+ | |||
+ | *איבר גדול ביותר ביותר הוא יחיד. | ||
+ | *אם חסם מלעיל שייך לקבוצה, אז הוא הגדול ביותר. | ||
+ | *האיבר הגדול ביותר בקבוצה הוא איבר מקסימלי, ואין איברים מקסימליים אחרים. | ||
+ | |||
+ | |||
+ | |||
+ | *האם תתכן קבוצה עם איבר מקסימלי יחיד שאינו האיבר הגדול ביותר בקבוצה? | ||
+ | |||
+ | |||
+ | *ביחס ההכלה על קבוצת חזקה, האיחוד הכללי של קבוצת קבוצות הוא החסם העליון שלה, והחיתוך הכללי הוא החסם התחתון. | ||
+ | *ביחס 'מחלק את' על הטבעיים, המחלק המשותף המקסימלי הוא החסם התחתון, והמכפלה המשותפת המינימלית הוא החסם העליון. | ||
+ | |||
<videoflash>EX6sPaiiu3k</videoflash> | <videoflash>EX6sPaiiu3k</videoflash> | ||
+ | |||
+ | ====שרשראות==== | ||
+ | |||
+ | *יחס סדר חלקי R על A נקרא '''מלא''' (או לינארי, או קווי) אם: | ||
+ | **<math>\forall a,b\in A:aRb\or bRa</math> | ||
+ | |||
+ | |||
+ | *יהי R יחס סדר חלקי על A, ותהי <math>S\subseteq A</math>. | ||
+ | *אזי <math>S</math> נקראת '''שרשרת''' אם היחס מלא עליה, כלומר <math>\forall a,b\in S:aRb\or bRa</math> | ||
====תרגול==== | ====תרגול==== | ||
שורה 71: | שורה 212: | ||
==פרק 4 - פונקציות== | ==פרק 4 - פונקציות== | ||
===הגדרת פונקציות=== | ===הגדרת פונקציות=== | ||
+ | *יחס f מA לB נקרא פונקציה אם הוא ח"ע ושלם, ומסמנים במקרה זה <math>f:A\to B</math>, וכן <math>f(a)=b\iff (a,b)\in f</math>. | ||
+ | *A נקרא תחום הפונקציה (או תחום הגדרה), B נקרא הטווח של הפונקציה. | ||
+ | |||
+ | |||
+ | *שימו לב, הסרטון ישן, ושם פונקציה הוגדרה כיחס ח"ע בלבד, בניגוד להגדרה העדכנית שלנו בקורס. | ||
+ | |||
+ | |||
<videoflash>XP-SwmSlTUc</videoflash> | <videoflash>XP-SwmSlTUc</videoflash> | ||
===חח"ע ועל, תמונה ותמונה הפוכה=== | ===חח"ע ועל, תמונה ותמונה הפוכה=== | ||
+ | *תהי <math>f:A\to B</math> פונקציה. אזי: | ||
+ | **f חח"ע אם לכל <math>x_1,x_2\in A</math> המקיימים <math>f(x_1)=f(x_2)</math> מתקיים כי <math>x_1=x_2</math> | ||
+ | **f על אם לכל <math>y\in B</math> קיים <math>x\in A</math> כך ש<math>f(x)=y</math> | ||
+ | **תהי <math>X\subseteq A</math> נגדיר את קבוצת התמונה <math>f[X]=\{f(a)|a\in X\}</math> | ||
+ | **תהי <math>Y\subseteq B</math> נגדיר את קבוצת התמונה ההפוכה <math>f^{-1}[Y]=\{a\in A|f(a)\in Y\}</math> | ||
+ | **<math>f[]:P(A)\to P(B)</math> היא פונקצית התמונה, השולחת כל תת קבוצה לקבוצת התמונה שלה | ||
+ | **<math>f^{-1}[]:P(B)\to P(A)</math> היא פונקצית התמונה ההפוכה, השולחת כל תת קבוצה לקבוצת התמונה ההפוכה שלה | ||
+ | |||
+ | |||
+ | *שימו לב | ||
+ | **<math>x\in f^{-1}[Y]\iff f(x)\in Y</math> | ||
+ | **<math>y\in f[X] \iff \exist a\in X :f(a)=y </math> | ||
+ | |||
+ | |||
<videoflash>BgCrOeJEjDo</videoflash> | <videoflash>BgCrOeJEjDo</videoflash> | ||
===הרכבת פונקציות, פונקציות הפיכות=== | ===הרכבת פונקציות, פונקציות הפיכות=== | ||
+ | |||
+ | *תהיינה <math>f:A\to B</math> וכן <math>g:B\to C</math> אזי נגדיר את פונקצית ההרכבה <math>g\circ f:A\to C</math> ע"י <math>g\circ f(a)=g(f(a))</math> | ||
+ | *פעולת ההרכבה היא אסוציאטיבית. | ||
+ | |||
+ | |||
+ | *תהי קבוצה A נגדיר את '''פונקצית הזהות''' <math>I_A:A\to A</math> ע"י <math>I_A(x)=x</math>. | ||
+ | *לכל פונקציה <math>f:A\to B</math> מתקיים כי <math>I_B\circ f = f\circ I_A = f</math> | ||
+ | |||
+ | |||
+ | *פונקציה <math>f:A\to B</math> נקראת הפיכה אם קיימות פונקציות <math>g,h:B\to A</math> כך ש: | ||
+ | **<math>g\circ f = I_A</math> וכן <math>f\circ h = I_B</math> | ||
+ | *נשים לב כי | ||
+ | **<math>h=I_A\circ h = (g\circ f)\circ h = g\circ (f\circ h)=g\circ I_B = g</math> | ||
+ | *לכן אם פונקציה הפיכה, יש פונקציה יחידה שהופכת אותה (ההופכית), נסמנה <math>f^{-1}:B\to A</math>. | ||
+ | *שימו לב: עם סוגריים מרובעים זו פונקצית התמונה ההפוכה שיש לכל פונקציה ופועלת על תתי קבוצות, עם סוגריים עגולים זו הפונקציה ההופכית שיש רק להפיכות ופועלת על איברים. | ||
+ | |||
<videoflash>t5QyDk-Mo2g</videoflash> | <videoflash>t5QyDk-Mo2g</videoflash> | ||
שורה 239: | שורה 417: | ||
(בהנחת עקרון המקסימום של האוסדורף) | (בהנחת עקרון המקסימום של האוסדורף) | ||
− | *תהי A קבוצה אינסופית, אזי <math>\aleph_0\leq A</math> | + | *תהי A קבוצה אינסופית, אזי <math>\aleph_0\leq |A|</math> |
<videoflash>W4see8tTArk</videoflash> | <videoflash>W4see8tTArk</videoflash> | ||
שורה 268: | שורה 446: | ||
*ולכן לפי משפט ק.ש.ב נקבל כי | *ולכן לפי משפט ק.ש.ב נקבל כי | ||
**<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> | ||
<videoflash>Ty-lY6-uRPo</videoflash> | <videoflash>Ty-lY6-uRPo</videoflash> | ||
+ | |||
שורה 279: | שורה 466: | ||
===הקשר בין עוצמת הטבעיים לעוצמת הממשיים=== | ===הקשר בין עוצמת הטבעיים לעוצמת הממשיים=== | ||
+ | |||
+ | *<math>2^{\aleph_0}=\aleph</math> כלומר <math> P(\mathbb{N})\sim\mathbb{R}</math> | ||
+ | |||
+ | |||
<videoflash>dhrT0edcmJE</videoflash> | <videoflash>dhrT0edcmJE</videoflash> | ||
+ | |||
===תרגול=== | ===תרגול=== | ||
*[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 6|תרגול בנושא עוצמות]] | *[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 6|תרגול בנושא עוצמות]] | ||
*[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 7|חשבון (אריתמטיקה) של עוצמות]] | *[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 7|חשבון (אריתמטיקה) של עוצמות]] |
גרסה מ־14:37, 22 באוגוסט 2020
תוכן עניינים
- 1 חומר עזר
- 2 סרטוני ותקציר הרצאות
- 2.1 פרק 1 - מבוא ללוגיקה מתמטית
- 2.2 פרק 2 - מבוא לתורת הקבוצות
- 2.3 פרק 3 - יחסים
- 2.4 פרק 4 - פונקציות
- 2.5 פרק 5 - עוצמות
- 2.5.1 מבוא
- 2.5.2 השוואת עוצמות
- 2.5.3 משפט קנטור
- 2.5.4 קבוצות בנות מנייה
- 2.5.5 חשבון עוצמות (אריתמטיקה של עוצמות)
- 2.5.6 משפט קנטור-שרדר-ברנשטיין
- 2.5.7 איחוד בן מנייה של קבוצות בנות מנייה
- 2.5.8 אקסיומת הבחירה ועקרון המקסימום של האוסדורף
- 2.5.9 השוואת עוצמות
- 2.5.10 סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות
- 2.5.11 הקשר בין עוצמת הטבעיים לעוצמת הממשיים
- 2.5.12 תרגול
חומר עזר
- סיכומי ההרצאות של ד״ר ארז שיינר, ע״י אורית חסון, קיץ 2016
- מבחנים בבדידה
- מבחנים בקורס בדידה למורים - שימו לב, הקורס למורים מכיל משמעותית פחות חומר, והמבחנים קלים יותר. יחד עם זאת, יש שם כמות גדולה של תרגילים רלוונטיים ברמה נמוכה.
סרטוני ותקציר הרצאות
פרק 1 - מבוא ללוגיקה מתמטית
פסוקים, קשרים, כמתים, פרדיקטים
תרגול
אינדוקציה
- משפט האינדוקציה המתמטית
- תהי סדרת טענות כך שמתקיימים שני התנאים הבאים:
- הטענה הראשונה נכונה.
- לכל אם הטענה הn מתקיימת אז גם הטענה הn+1 מתקיימת.
- אזי כל הטענות בסדרה נכונות
- אינדוקציה שלמה (מלאה)
- תהי סדרת טענות כך ש:
- לכל אם כל הטענות עד ולא כולל הטענה הn מתקיימות, אזי גם הטענה הn מתקיימת.
- אזי כל הטענות בסדרה מתקיימות.
- שימו לב: לפני הטענה הראשונה אין טענות, ולכן כולן מתקיימות באופן ריק. כלומר מנוסח התנאי נובע שצריך להוכיח שהטענה הראשונה מתקיימת.
- פרדוקס הסוסים (או פתיתי השלג)
תרגול
פרק 2 - מבוא לתורת הקבוצות
קבוצות ופעולות על קבוצות
- איבר שייך לקבוצה אם הוא אחד האיברים בקבוצה.
- קבוצה מוכלת בקבוצה אחרת אם
- תהי קבוצה ותהיינה . נגדיר את:
- קבוצת האיחוד
- קבוצת החיתוך
- קבוצת ההפרש
- קבוצת ההפרש הסימטרי
- קבוצת המשלים
שיטות הוכחה בסיסיות
- הוכחת טענות מכומתות - טענות 'לכל' וטענות 'קיים'
- הוכחת הכלה בין קבוצות, ושיוויון בין קבוצות
איחוד וחיתוך כלליים
- תהי S קבוצה של קבוצות, נגדיר:
קבוצת החזקה
תרגול
פרק 3 - יחסים
מכפלה קרטזית ויחסים
תכונות של יחסים
- יהי R יחס על A (כלומר ) אזי:
- R נקרא רפלקסיבי אם לכל מתקיים .
- R נקרא סימטרי אם לכל המקיימים מתקיים
- R נקרא אנטי-סימטרי אם לכל המקיימים מתקיים
- R נקרא טרנזיטיבי אם לכל המקיימים מתקיים
- R נקרא מלא אם לכל מתקיים כי
- יהי R יחס מA לB (כלומר ) אזי:
- 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 על אם לכל קיים כך ש
- תהי נגדיר את קבוצת התמונה
- תהי נגדיר את קבוצת התמונה ההפוכה
- היא פונקצית התמונה, השולחת כל תת קבוצה לקבוצת התמונה שלה
- היא פונקצית התמונה ההפוכה, השולחת כל תת קבוצה לקבוצת התמונה ההפוכה שלה
- שימו לב
הרכבת פונקציות, פונקציות הפיכות
- תהיינה וכן אזי נגדיר את פונקצית ההרכבה ע"י
- פעולת ההרכבה היא אסוציאטיבית.
- תהי קבוצה 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 קבוצה בת מנייה של קבוצות בנות מנייה, כלומר:
- אזי גם האיחוד הכללי הוא בן מנייה:
- מסקנה: אוסף תתי הקבוצות הסופיות של המספרים הטבעיים הוא בן מנייה.
אקסיומת הבחירה ועקרון המקסימום של האוסדורף
אקסיומת הבחירה
- תהי S קבוצת קבוצת לא ריקות, ונסמן את האיחוד הכללי ב .
- אזי קיימת פונקצית בחירה הבוחרת איבר מתוך כל קבוצה, כלומר:
- דוגמא:
- תהי פונקציה על אזי קיימת תת קבוצה כך ש חח"ע ועל.
- תהיינה אזי אם ורק אם קיימת על.
עקרון המקסימום של האוסדורף
- תהי קבוצה A עם יחס סדר חלקי, תת קבוצה נקראת שרשרת אם היחס מלא עליה (ניתן להשוות בין כל שני איברים בS).
- שרשרת נקראת מקסימלית בA אם היא אינה מוכלת באף שרשרת אחרת.
- עקרון המקסימום של האוסדורף אומר שכל שרשרת מוכלת בשרשרת מקסימלית.
- דוגמא - אוסף עיגולים במישור שאינם חותכים זה את זה, ולא ניתן להוסיף אפילו עיגול אחד נוסף.
אלף אפס היא העוצמה האינסופית הקטנה ביותר
(בהנחת עקרון המקסימום של האוסדורף)
- תהי A קבוצה אינסופית, אזי
- תהי A קבוצה אינסופית, ותהי B קבוצה סופית, אזי:
השוואת עוצמות
(בהנחת עיקרון המקסימום של האוסדורף)
- תהיינה שתי קבוצות A,B אזי או
סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות
- תהיינה עוצמות אזי:
- נניח בנוסף כי אזי:
- נניח בנוסף כי b אינסופית, ונקבל ביחד
- (המעבר מוכח בסרטון השני).
- ולכן לפי משפט ק.ש.ב נקבל כי
- דוגמא - מה היא עוצמת קבוצת המספרים האי-רציונאליים?
- (איחוד זר כמובן)
- לכן
- לכן
- לפי המשפט לעיל, סכום העוצמות הוא העוצמה הגדולה מבין השתיים.
- כיוון ש נקבל כי
- תהי עוצמה אינסופית b אזי
הקשר בין עוצמת הטבעיים לעוצמת הממשיים
- כלומר