מתמטיקה בדידה - ארז שיינר
(הופנה מהדף סרטונים:מתמטיקה בדידה)
חומר עזר
- סיכומי ההרצאות של ד״ר ארז שיינר, ע״י אורית חסון, קיץ 2016
- מבחנים בבדידה
- בחנים בבדידה
- מבחנים בקורס בדידה למורים - שימו לב, הקורס למורים מכיל משמעותית פחות חומר, והמבחנים קלים יותר. יחד עם זאת, יש שם כמות גדולה של תרגילים רלוונטיים ברמה נמוכה.
סרטוני ותקציר הרצאות
פרק 1 - מבוא ללוגיקה מתמטית
פסוקים, קשרים, כמתים, פרדיקטים
תרגול
אינדוקציה
- משפט האינדוקציה המתמטית
- תהי סדרת טענות כך שמתקיימים שני התנאים הבאים:
- הטענה הראשונה נכונה.
- לכל [math]\displaystyle{ n\in \mathbb{N} }[/math] אם הטענה הn מתקיימת אז גם הטענה הn+1 מתקיימת.
- אזי כל הטענות בסדרה נכונות
- דוגמא:
- [math]\displaystyle{ \sum_{k=1}^{2^{n-1}}\frac{1}{k} \gt \frac{n}{2} }[/math]
- אינדוקציה שלמה (מלאה)
- תהי סדרת טענות כך ש:
- לכל [math]\displaystyle{ n\in \mathbb{N} }[/math] אם כל הטענות עד ולא כולל הטענה הn מתקיימות, אזי גם הטענה הn מתקיימת.
- אזי כל הטענות בסדרה מתקיימות.
- שימו לב: לפני הטענה הראשונה אין טענות, ולכן כולן מתקיימות באופן ריק. כלומר מנוסח התנאי נובע שצריך להוכיח שהטענה הראשונה מתקיימת.
- פרדוקס הסוסים (או פתיתי השלג)
תרגול
פרק 2 - מבוא לתורת הקבוצות
קבוצות ופעולות על קבוצות
- איבר שייך לקבוצה [math]\displaystyle{ a\in A }[/math] אם הוא אחד האיברים בקבוצה.
- קבוצה מוכלת בקבוצה אחרת [math]\displaystyle{ A\subseteq B }[/math] אם [math]\displaystyle{ \forall a\in A : a\in B }[/math]
- [math]\displaystyle{ \{1,2\}=\{2,1\} }[/math]
- [math]\displaystyle{ \{1,1,2\}=\{1,2\} }[/math]
- תהי קבוצה [math]\displaystyle{ U }[/math] ותהיינה [math]\displaystyle{ A,B\subseteq U }[/math]. נגדיר את:
- קבוצת האיחוד [math]\displaystyle{ A\cup B =\{ x\in U:x\in A \or x\in B\} }[/math]
- קבוצת החיתוך [math]\displaystyle{ A\cap B =\{ x\in U:x\in A \and x\in B\} }[/math]
- קבוצת ההפרש [math]\displaystyle{ A\setminus B =\{ x\in U:x\in A \and x\not\in B\} }[/math]
- קבוצת ההפרש הסימטרי [math]\displaystyle{ A\Delta B = (A\setminus B)\cup (B\setminus A) }[/math]
- קבוצת המשלים [math]\displaystyle{ \overline{A}=\{x\in U:x\not\in A\} }[/math]
שיטות הוכחה בסיסיות
- הוכחת טענות מכומתות - טענות 'לכל' וטענות 'קיים'
- הוכחת הכלה בין קבוצות, ושיוויון בין קבוצות
איחוד וחיתוך כלליים
- תהי S קבוצה של קבוצות, נגדיר:
- [math]\displaystyle{ \cup_{A\in S}A = \{x|\exists A\in S :x\in A\} }[/math]
- [math]\displaystyle{ \cap_{A\in S}A = \{x|\forall A\in S :x\in A\} }[/math]
קבוצת החזקה
- [math]\displaystyle{ X\in P(A) \iff X\subseteq A }[/math]
תרגול
פרק 3 - יחסים
מכפלה קרטזית ויחסים
תכונות של יחסים
- יהי R יחס על A (כלומר [math]\displaystyle{ R\subseteq A\times A }[/math]) אזי:
- R נקרא רפלקסיבי אם לכל [math]\displaystyle{ a\in A }[/math] מתקיים [math]\displaystyle{ aRa }[/math].
- R נקרא סימטרי אם לכל [math]\displaystyle{ a,b\in A }[/math] המקיימים [math]\displaystyle{ aRb }[/math] מתקיים [math]\displaystyle{ bRa }[/math]
- R נקרא אנטי-סימטרי אם לכל [math]\displaystyle{ a,b\in A }[/math] המקיימים [math]\displaystyle{ aRb\and bRa }[/math] מתקיים [math]\displaystyle{ a=b }[/math]
- R נקרא טרנזיטיבי אם לכל [math]\displaystyle{ a,b,c\in A }[/math] המקיימים [math]\displaystyle{ aRb \and bRc }[/math] מתקיים [math]\displaystyle{ aRc }[/math]
- R נקרא מלא אם לכל [math]\displaystyle{ a,b\in A }[/math] מתקיים כי [math]\displaystyle{ aRb\or bRa }[/math]
- יהי R יחס מA לB (כלומר [math]\displaystyle{ R\subseteq A\times B }[/math]) אזי:
- R נקרא חד-ערכי (ח"ע) אם לכל [math]\displaystyle{ a\in A }[/math] ולכל [math]\displaystyle{ b_1,b_2\in B }[/math] המקיימים [math]\displaystyle{ aRb_1 \and aRb_2 }[/math] מתקיים [math]\displaystyle{ b_1=b_2 }[/math]
- R נקרא שלם אם לכל [math]\displaystyle{ a\in A }[/math] קיים [math]\displaystyle{ b\in B }[/math] כך ש [math]\displaystyle{ aRb }[/math]
- R נקרא חד-חד-ערכי (חח"ע) אם לכל [math]\displaystyle{ a_1,a_2\in A }[/math] ולכל [math]\displaystyle{ b\in B }[/math] המקיימים [math]\displaystyle{ a_1Rb\and a_2Rb }[/math] מתקיים [math]\displaystyle{ a_1=a_2 }[/math]
- R נקרא על אם לכל [math]\displaystyle{ b\in B }[/math] קיים [math]\displaystyle{ a\in A }[/math] כך ש [math]\displaystyle{ aRb }[/math]
יחסי שקילות
- יחס R על קבוצה A נקרא יחס שקילות אם הוא רפלקסיבי, סימטרי וטרנזיטיבי.
- יהי R יחס שקילות על A.
- לכל [math]\displaystyle{ a\in A }[/math] מוגדרת קבוצת מחלקת השקילות של a ע"י:
- [math]\displaystyle{ [a]_R=\{x\in A|aRx\} }[/math]
- קבוצת כל קבוצות מחלקות השקילות נקראת קבוצת המנה:
- [math]\displaystyle{ A/R=\{[a]_R:a\in A\} }[/math]
- תהי קבוצה A. קבוצת תתי קבוצות [math]\displaystyle{ U\subseteq P(A) }[/math] נקראת חלוקה של A אם:
- [math]\displaystyle{ \cup_{X\in U}X=A }[/math]
- [math]\displaystyle{ \emptyset\notin U }[/math]
- לכל [math]\displaystyle{ X_1,X_2\in U }[/math] אם [math]\displaystyle{ X_1\cap X_2\neq \emptyset }[/math] אזי [math]\displaystyle{ X_1=X_2 }[/math]
- היחס המושרה מחלוקה:
- תהי קבוצה A ותהי חלוקה שלה U. נגדיר יחס R על A על ידי:
- [math]\displaystyle{ aRb }[/math] אם ורק אם קיימת [math]\displaystyle{ X\in U }[/math] כך ש[math]\displaystyle{ a,b\in X }[/math]
- היחס המושרה מחלוקה הוא יחס שקילות.
- קבוצת המנה היא חלוקה של A.
- היחס המושרה מקבוצת המנה, הוא יחס השקילות המקורי; קבוצת המנה של יחס שקילות מושרה היא החלוקה המקורית.
תרגול
יחסי סדר
- יחס R על קבוצה A נקרא יחס סדר חלקי אם הוא רפלקסיבי, אנטי-סימטרי וטרנזיטיבי
איברים מינימליים ומקסימליים, וחסמים
- יהי R יחס סדר חלקי על קבוצה X, ותהי [math]\displaystyle{ A\subseteq X }[/math] תת קבוצה.
- איבר [math]\displaystyle{ M\in A }[/math] נקרא מקסימלי בA אם לכל [math]\displaystyle{ a\in A }[/math] המקיים [math]\displaystyle{ MRa }[/math] מתקיים כי [math]\displaystyle{ a=M }[/math] (אין גדולים ממנו)
- איבר [math]\displaystyle{ m\in A }[/math] נקרא מינימלי בA אם לכל [math]\displaystyle{ a\in A }[/math] המקיים [math]\displaystyle{ aRm }[/math] מתקיים כי [math]\displaystyle{ a=m }[/math] (אין קטנים ממנו)
- איבר [math]\displaystyle{ M\in A }[/math] נקרא הגדול ביותר (מקסימום) בA אם לכל [math]\displaystyle{ a\in A }[/math] מתקיים [math]\displaystyle{ aRM }[/math] (הוא גדול מכולם)
- איבר [math]\displaystyle{ m\in A }[/math] נקרא הקטן ביותר (מינימום) בA אם לכל [math]\displaystyle{ a\in A }[/math] מתקיים [math]\displaystyle{ mRa }[/math] (הוא קטן מכולם)
- איבר [math]\displaystyle{ M\in X }[/math] נקרא חסם מלעיל של A אם לכל [math]\displaystyle{ a\in A }[/math] מתקיים [math]\displaystyle{ aRM }[/math] (הוא גדול מכל איברי הקבוצה, אבל לאו דווקא נמצא בקבוצה)
- איבר [math]\displaystyle{ m\in X }[/math] נקרא חסם מלרע של A אם לכל [math]\displaystyle{ a\in A }[/math] מתקיים [math]\displaystyle{ mRa }[/math] (הוא קטן מכל איברי הקבוצה, אבל לאו דווקא נמצא בקבוצה)
- אם בקבוצת חסמי המלעיל של A יש איבר קטן ביותר הוא נקרא חסם עליון (supremum) של A.
- אם בקבוצת חסמי המלרע של A יש איבר גדול ביותר הוא נקרא חסם תחתון (infimum) של A.
- איבר גדול ביותר ביותר הוא יחיד.
- אם חסם מלעיל שייך לקבוצה, אז הוא הגדול ביותר.
- האיבר הגדול ביותר בקבוצה הוא איבר מקסימלי, ואין איברים מקסימליים אחרים.
- האם תתכן קבוצה עם איבר מקסימלי יחיד שאינו האיבר הגדול ביותר בקבוצה?
- ביחס ההכלה על קבוצת חזקה, האיחוד הכללי של קבוצת קבוצות הוא החסם העליון שלה, והחיתוך הכללי הוא החסם התחתון.
- ביחס 'מחלק את' על הטבעיים, המחלק המשותף המקסימלי הוא החסם התחתון, והמכפלה המשותפת המינימלית הוא החסם העליון.
שרשראות
- יחס סדר חלקי R על A נקרא מלא (או לינארי, או קווי) אם:
- [math]\displaystyle{ \forall a,b\in A:aRb\or bRa }[/math]
- יהי R יחס סדר חלקי על A, ותהי [math]\displaystyle{ S\subseteq A }[/math].
- אזי [math]\displaystyle{ S }[/math] נקראת שרשרת אם היחס מלא עליה, כלומר [math]\displaystyle{ \forall a,b\in S:aRb\or bRa }[/math]
תרגול
פרק 4 - פונקציות
הגדרת פונקציות
- יחס f מA לB נקרא פונקציה אם הוא ח"ע ושלם, ומסמנים במקרה זה [math]\displaystyle{ f:A\to B }[/math], וכן [math]\displaystyle{ f(a)=b\iff (a,b)\in f }[/math].
- A נקרא תחום הפונקציה (או תחום הגדרה), B נקרא הטווח של הפונקציה.
- שימו לב, הסרטון ישן, ושם פונקציה הוגדרה כיחס ח"ע בלבד, בניגוד להגדרה העדכנית שלנו בקורס.
חח"ע ועל, תמונה ותמונה הפוכה
- תהי [math]\displaystyle{ f:A\to B }[/math] פונקציה. אזי:
- f חח"ע אם לכל [math]\displaystyle{ x_1,x_2\in A }[/math] המקיימים [math]\displaystyle{ f(x_1)=f(x_2) }[/math] מתקיים כי [math]\displaystyle{ x_1=x_2 }[/math]
- f על אם לכל [math]\displaystyle{ y\in B }[/math] קיים [math]\displaystyle{ x\in A }[/math] כך ש[math]\displaystyle{ f(x)=y }[/math]
- תהי [math]\displaystyle{ X\subseteq A }[/math] נגדיר את קבוצת התמונה [math]\displaystyle{ f[X]=\{f(a)|a\in X\} }[/math]
- תהי [math]\displaystyle{ Y\subseteq B }[/math] נגדיר את קבוצת התמונה ההפוכה [math]\displaystyle{ f^{-1}[Y]=\{a\in A|f(a)\in Y\} }[/math]
- [math]\displaystyle{ f[]:P(A)\to P(B) }[/math] היא פונקצית התמונה, השולחת כל תת קבוצה לקבוצת התמונה שלה
- [math]\displaystyle{ f^{-1}[]:P(B)\to P(A) }[/math] היא פונקצית התמונה ההפוכה, השולחת כל תת קבוצה לקבוצת התמונה ההפוכה שלה
- שימו לב
- [math]\displaystyle{ x\in f^{-1}[Y]\iff f(x)\in Y }[/math]
- [math]\displaystyle{ y\in f[X] \iff \exist a\in X :f(a)=y }[/math]
הרכבת פונקציות, פונקציות הפיכות
- תהיינה [math]\displaystyle{ f:A\to B }[/math] וכן [math]\displaystyle{ g:B\to C }[/math] אזי נגדיר את פונקצית ההרכבה [math]\displaystyle{ g\circ f:A\to C }[/math] ע"י [math]\displaystyle{ g\circ f(a)=g(f(a)) }[/math]
- פעולת ההרכבה היא אסוציאטיבית.
- תהי קבוצה A נגדיר את פונקצית הזהות [math]\displaystyle{ I_A:A\to A }[/math] ע"י [math]\displaystyle{ I_A(x)=x }[/math].
- לכל פונקציה [math]\displaystyle{ f:A\to B }[/math] מתקיים כי [math]\displaystyle{ I_B\circ f = f\circ I_A = f }[/math]
- פונקציה [math]\displaystyle{ f:A\to B }[/math] נקראת הפיכה אם קיימות פונקציות [math]\displaystyle{ g,h:B\to A }[/math] כך ש:
- [math]\displaystyle{ g\circ f = I_A }[/math] וכן [math]\displaystyle{ f\circ h = I_B }[/math]
- נשים לב כי
- [math]\displaystyle{ h=I_A\circ h = (g\circ f)\circ h = g\circ (f\circ h)=g\circ I_B = g }[/math]
- לכן אם פונקציה הפיכה, יש פונקציה יחידה שהופכת אותה (ההופכית), נסמנה [math]\displaystyle{ f^{-1}:B\to A }[/math].
- שימו לב: עם סוגריים מרובעים זו פונקצית התמונה ההפוכה שיש לכל פונקציה ופועלת על תתי קבוצות, עם סוגריים עגולים זו הפונקציה ההופכית שיש רק להפיכות ופועלת על איברים.
פונקציה מוגדרת היטב
תרגול
פרק 5 - עוצמות
מבוא
השוואת עוצמות
- A שקולת עוצמה לB או עוצמתה של A שווה לB, אם קיימת פונקציה הפיכה (חח"ע ועל) [math]\displaystyle{ f:A\to B }[/math].
- במקרה זה מסמנים [math]\displaystyle{ A\sim B }[/math] או [math]\displaystyle{ |A|=|B| }[/math].
- כל קבוצה שקולת עוצמה לעצמה
- אם A שקולת עוצמה לB, גם B שקולת עוצמה לA
- אם A שקולת עוצמה לB וB שקולת עוצמה לC אזי A שקולת עוצמה לC
- עוצמתה של A קטנה או שווה לזו של B, אם קיימת פונקציה חח"ע [math]\displaystyle{ f:A\to B }[/math].
- במקרה זה מסמנים [math]\displaystyle{ |A|\leq |B| }[/math]
- כל קבוצה A השקולת עוצמה לקבוצת הטבעיים מסומנת [math]\displaystyle{ |A|=\aleph_0 }[/math]
- כל קבוצה A השקולת עוצמה לקבוצת הממשיים מסומנת [math]\displaystyle{ |A|=\aleph }[/math]
משפט קנטור
- [math]\displaystyle{ |A|\lt |P(A)| }[/math]
קבוצות בנות מנייה
- קבוצה A נקראת בת מנייה אם [math]\displaystyle{ |A|\leq \aleph_0 }[/math]
- כל קבוצה A בת מנייה אינסופית מקיימת [math]\displaystyle{ |A|=\aleph_0 }[/math]
חשבון עוצמות (אריתמטיקה של עוצמות)
חיבור עוצמות
- תהיינה שתי עוצמות a,b ותהיינה שתי נציגות זרות לעוצמות A,B.
- נגדיר [math]\displaystyle{ a+b=|A\cup B| }[/math], הגדרה זו אינה תלוייה בבחירת הנציגות.
כפל עוצמות
- תהיינה שתי עוצמות a,b ותהיינה שתי נציגות לעוצמות A,B.
- נגדיר [math]\displaystyle{ a\cdot b=|A\times B| }[/math], הגדרה זו אינה תלוייה בבחירת הנציגות.
חזקת עוצמות
- תהיינה שתי עוצמות a,b ותהיינה שתי נציגות לעוצמות A,B.
- נגדיר את [math]\displaystyle{ A^B }[/math] להיות אוסף כל הפונקציות מB לA (מהמעריך לבסיס).
- נגדיר [math]\displaystyle{ a^b=|A^B| }[/math], הגדרה זו אינה תלוייה בבחירת הנציגות.
- חוקי חזקות
- תהיינה עוצמות a,b,c אזי
- [math]\displaystyle{ a^b\cdot a^c = a^{b+c} }[/math]
- [math]\displaystyle{ (a^b)^c = a^{b\cdot c} }[/math]
- [math]\displaystyle{ a^b\cdot c^b = (a\cdot c)^b }[/math]
עוצמת קבוצת החזקה
- [math]\displaystyle{ |P(A)|=2^{|A|} }[/math]
השוואת חשבון עוצמות
- תהיינה עוצמות a,b,c,d כך ש [math]\displaystyle{ a\leq c }[/math] וכן [math]\displaystyle{ b\leq d }[/math] אזי:
- [math]\displaystyle{ a+b\leq c+d }[/math]
- [math]\displaystyle{ a\cdot b\leq c\cdot d }[/math]
- אם בנוסף נתון כי [math]\displaystyle{ c\neq 0 }[/math] אזי
- [math]\displaystyle{ a^b\leq c^d }[/math]
משפט קנטור-שרדר-ברנשטיין
- אם [math]\displaystyle{ |A|\leq |B| }[/math] וגם [math]\displaystyle{ |B|\leq |A| }[/math] אזי [math]\displaystyle{ A\sim B }[/math]
למת נקודת השבת
- תהי פונקציה עולה [math]\displaystyle{ h:P(A)\to P(A) }[/math] כלומר המקיימת לכל [math]\displaystyle{ X_1\subseteq X_2 }[/math] כי [math]\displaystyle{ h(X_1)\subseteq h(X_2) }[/math]
- אזי קיימת נק' שבת [math]\displaystyle{ K\subseteq A }[/math] כך ש [math]\displaystyle{ h(K)=K }[/math].
הוכחת המשפט
עוצמות קטעים ממשיים
- [math]\displaystyle{ |\mathbb{R}|=|[a,\infty)|=|[a,b]|=|(a,b)|=\aleph }[/math]
אקסיומת הבחירה ועקרון המקסימום של האוסדורף
אקסיומת הבחירה
- תהי S קבוצת קבוצות לא ריקות, ונסמן את האיחוד הכללי ב [math]\displaystyle{ U=\cup_{X\in S}X }[/math].
- אזי קיימת פונקצית בחירה [math]\displaystyle{ f:S\to U }[/math] הבוחרת איבר מתוך כל קבוצה, כלומר:
- [math]\displaystyle{ \forall X\in S: f(X)\in X }[/math]
- דוגמא:
- תהי פונקציה על [math]\displaystyle{ f:A\to B }[/math] אזי קיימת תת קבוצה [math]\displaystyle{ X\subseteq A }[/math] כך ש [math]\displaystyle{ f:X\to B }[/math] חח"ע ועל.
- תהיינה [math]\displaystyle{ A,B\neq\emptyset }[/math] אזי [math]\displaystyle{ |A|\leq |B| }[/math] אם ורק אם קיימת [math]\displaystyle{ g:B\to A }[/math] על.
- בכיוון ראשון:
- תהי [math]\displaystyle{ f:A\to B }[/math] חח"ע
- כיוון ש[math]\displaystyle{ A\neq \emptyset }[/math] קיים [math]\displaystyle{ a\in A }[/math]
- נגדיר פונקציה [math]\displaystyle{ g:B\to A }[/math] באופן הבא:
- לכל [math]\displaystyle{ b\in B }[/math]
- אם קיים [math]\displaystyle{ x\in A }[/math] כך ש [math]\displaystyle{ f(x)=b }[/math] נגדיר [math]\displaystyle{ f(b)=x }[/math] (בגלל החח"ע זה מוגדר היטב)
- אם [math]\displaystyle{ b\not\in Im(f) }[/math] נגדיר [math]\displaystyle{ f(b)=a }[/math]
- הפונקציה [math]\displaystyle{ g }[/math] שהגדרנו היא אכן על, כי לכל [math]\displaystyle{ x\in A }[/math] מתקיים כי [math]\displaystyle{ g(f(x))=x }[/math]
- בכיוון שני:
- תהי [math]\displaystyle{ g:B\to A }[/math] על, אזי כל הקבוצות באוסף [math]\displaystyle{ U=\left\{g^{-1}[\{a\}]|a\in A\right\} }[/math] אינן ריקות.
- ניקח פונקצית בחירה [math]\displaystyle{ h:U\to B }[/math] ונגדיר [math]\displaystyle{ f:A\to B }[/math] ע"י [math]\displaystyle{ f(a)=h(g^{-1}[\{a\}]) }[/math]
- אכן [math]\displaystyle{ f }[/math] חח"ע כי אם [math]\displaystyle{ f(a_1)=f(a_2)=b }[/math] אזי [math]\displaystyle{ b\in g^{-1}[\{a_1\}] }[/math] וכן [math]\displaystyle{ b\in g^{-1}[\{a_2\}] }[/math]
- ולכן [math]\displaystyle{ g(b)=a_1 }[/math] וכן [math]\displaystyle{ g(b)=a_2 }[/math], כלומר [math]\displaystyle{ a_1=a_2 }[/math]
עקרון המקסימום של האוסדורף
- תהי קבוצה A עם יחס סדר חלקי, תת קבוצה [math]\displaystyle{ S\subseteq A }[/math] נקראת שרשרת אם היחס מלא עליה (ניתן להשוות בין כל שני איברים בS).
- שרשרת נקראת מקסימלית בA אם היא אינה מוכלת באף שרשרת אחרת.
- עקרון המקסימום של האוסדורף אומר שכל שרשרת מוכלת בשרשרת מקסימלית.
- דוגמא - אוסף עיגולים במישור שאינם חותכים זה את זה, ולא ניתן להוסיף אפילו עיגול אחד נוסף.
- טענות שימושיות להמשך:
- תהי [math]\displaystyle{ U }[/math] קבוצה של יחסים מ[math]\displaystyle{ A }[/math] ל [math]\displaystyle{ B }[/math], תהי [math]\displaystyle{ M\subseteq U }[/math] שרשרת ביחס ההכלה ונסמן את האיחוד הכללי של השרשרת ב[math]\displaystyle{ f=\cup_{R\in M} R }[/math]
- אזי:
- אם כל היחסים ב[math]\displaystyle{ M }[/math] ח"ע, אז גם [math]\displaystyle{ f }[/math] ח"ע
- אכן, יהיו [math]\displaystyle{ (a,b_1),(a,b_2)\in f }[/math]
- לכן קיימים [math]\displaystyle{ R_1,R_2\in M }[/math] כך ש [math]\displaystyle{ (a,b_1)\in R_1 }[/math] וכן [math]\displaystyle{ (a,b_2)\in R_2 }[/math]
- כיוון ש[math]\displaystyle{ M }[/math] שרשרת, אזי [math]\displaystyle{ R_1\subseteq R_2 }[/math] (או ההפך) ולכן [math]\displaystyle{ (a,b_1),(a,b_2)\in R_2 }[/math]
- כיוון ש[math]\displaystyle{ R_2 }[/math] ח"ע נובע כי [math]\displaystyle{ b_1=b_2 }[/math] כפי שרצינו.
- אם כל היחסים ב[math]\displaystyle{ M }[/math] חח"ע, אזי גם [math]\displaystyle{ f }[/math] חח"ע
- הוכחה דומה לח"ע
- אם כל היחסים ב[math]\displaystyle{ M }[/math] ח"ע, אז גם [math]\displaystyle{ f }[/math] ח"ע
איחוד בן מנייה של קבוצות בנות מנייה
(בהנחת אקסיומת הבחירה)
- תהי S קבוצה בת מנייה של קבוצות בנות מנייה, כלומר:
- [math]\displaystyle{ |S|\leq\aleph_0 }[/math]
- [math]\displaystyle{ \forall X\in S:|X|\leq\aleph_0 }[/math]
- אזי גם האיחוד הכללי הוא בן מנייה:
- [math]\displaystyle{ |\cup_{X\in S}X|\leq \aleph_0 }[/math]
- מסקנה: אוסף תתי הקבוצות הסופיות של המספרים הטבעיים הוא בן מנייה.
- הערה לסרטון: אנחנו משתמשים באקסיומת הבחירה כאשר "בוחרים" את הפונקציות החח"ע מהקבוצות באוסף אל הטבעיים.
השוואת עוצמות
(בהנחת עיקרון המקסימום של האוסדורף)
- תהיינה שתי קבוצות A,B אזי [math]\displaystyle{ |A|\leq|B| }[/math] או [math]\displaystyle{ |A|\geq |B| }[/math]
- נביט ב[math]\displaystyle{ U }[/math] אוסף היחסים הח"ע והחח"ע מ[math]\displaystyle{ A }[/math] ל[math]\displaystyle{ B }[/math], וניקח שרשרת מקסימלית ביחס ההכלה [math]\displaystyle{ M\subseteq U }[/math]
- נסמן ב[math]\displaystyle{ f }[/math] את האיחוד הכללי על השרשרת [math]\displaystyle{ M }[/math]
- ראינו שנובע במקרה זה כי [math]\displaystyle{ f }[/math] יחס ח"ע וחח"ע מ[math]\displaystyle{ A }[/math] ל[math]\displaystyle{ B }[/math].
- אם [math]\displaystyle{ f }[/math] שלם, אזי [math]\displaystyle{ f:A\to B }[/math] פונקציה חח"ע ולכן [math]\displaystyle{ |A|\leq |B| }[/math]
- אם [math]\displaystyle{ f }[/math] על, אזי [math]\displaystyle{ f:X\to B }[/math] פונקציה על עבור [math]\displaystyle{ X\subseteq A }[/math] ולכן [math]\displaystyle{ |B|\leq |X|\leq |A| }[/math]
- אחרת, קיים זוג [math]\displaystyle{ (a,b)\in A\times B }[/math] כך ש [math]\displaystyle{ f\cup\{(a,b)\} }[/math] יחס ח"ע וחח"ע שניתן להוסיף לשרשרת [math]\displaystyle{ M }[/math] בסתירה למקסימליות שלה.
אלף אפס היא העוצמה האינסופית הקטנה ביותר
(בהנחת עקרון המקסימום של האוסדורף)
- תהי A קבוצה אינסופית, אזי [math]\displaystyle{ \aleph_0\leq |A| }[/math]
- דרך נוספת לזו המופיעה בסרטון:
- נוכיח בהמשך כי ניתן להשוות עוצמה בין כל שתי קבוצות
- אם [math]\displaystyle{ |A|\leq |\mathbb{N}| }[/math], כיוון ש[math]\displaystyle{ A }[/math] אינסופית נובע כי [math]\displaystyle{ |A|=\aleph_0 }[/math]
- אחרת, [math]\displaystyle{ |\mathbb{N}|\leq |A| }[/math] ולכן [math]\displaystyle{ \aleph_0\leq |A| }[/math] כפי שרצינו.
- תהי A קבוצה אינסופית, ותהי B קבוצה סופית, אזי:
- [math]\displaystyle{ |A|=|A\cup B|=|A\setminus B| }[/math]
- דרך נוספת לזו המופיעה בסרטון:
- בהמשך נוכיח כי לכל קבוצה אינסופית [math]\displaystyle{ X }[/math] מתקיים כי [math]\displaystyle{ |X|+|X|=|X| }[/math]
- לכן [math]\displaystyle{ |A|\leq |A\cup B|=|A|+|B\setminus A|\leq |A|+|A|=|A| }[/math] ולפי ק.ש.ב [math]\displaystyle{ |A|=|A\cup B| }[/math].
- שימו לב כי [math]\displaystyle{ B\setminus A }[/math] סופית ולכן קטנה יותר מהקבוצה האינסופית [math]\displaystyle{ A }[/math].
- כמו כן [math]\displaystyle{ |A|=|A\setminus B|+|B\cap A| }[/math]
- כעת [math]\displaystyle{ |A\setminus B|\leq|A\setminus B|+|B\cap A|\leq |A\setminus B|+|A\setminus B|=|A\setminus B| }[/math].
- שימו לב כי [math]\displaystyle{ B\cap A }[/math] סופית ולכן קטנה יותר מהקבוצה האינסופית [math]\displaystyle{ A\setminus B }[/math].
- לכן לפי ק.ש.ב [math]\displaystyle{ |A|=|A\setminus B|+|B\cap A|=|A\setminus B| }[/math]
סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות
- תהיינה עוצמות [math]\displaystyle{ a\leq b }[/math] אזי:
- [math]\displaystyle{ b\leq a+b }[/math]
- נניח בנוסף כי [math]\displaystyle{ 2\leq a\leq b }[/math] אזי:
- [math]\displaystyle{ a+b\leq a\cdot b }[/math]
- נניח בנוסף כי b אינסופית, ונקבל ביחד
- [math]\displaystyle{ b\leq a+b \leq a\cdot b\leq b\cdot b =b }[/math] (המעבר [math]\displaystyle{ b\cdot b=b }[/math] מוכח בסרטון השני).
- ולכן לפי משפט ק.ש.ב נקבל כי
- [math]\displaystyle{ a+b=a\cdot b = b }[/math]
- דוגמא - מה היא עוצמת קבוצת המספרים האי-רציונאליים?
- [math]\displaystyle{ \mathbb{R}=\mathbb{Q}\cup (\mathbb{R}\setminus\mathbb{Q}) }[/math] (איחוד זר כמובן)
- לכן [math]\displaystyle{ |\mathbb{R}|=|\mathbb{Q}|+ |(\mathbb{R}\setminus\mathbb{Q})| }[/math]
- לכן [math]\displaystyle{ \aleph=\aleph_0 +|(\mathbb{R}\setminus\mathbb{Q})| }[/math]
- לפי המשפט לעיל, סכום העוצמות הוא העוצמה הגדולה מבין השתיים.
- כיוון ש [math]\displaystyle{ \aleph\neq \aleph_0 }[/math] נקבל כי [math]\displaystyle{ |(\mathbb{R}\setminus\mathbb{Q})|=\aleph }[/math]
עוצמה כפול עצמה
- תהי קבוצה אינסופית [math]\displaystyle{ B }[/math] אזי [math]\displaystyle{ B\times B\sim B }[/math]
- הוכחה:
- תהי [math]\displaystyle{ S }[/math] קבוצת כל היחסים [math]\displaystyle{ R\subseteq (B\times B)\times B }[/math], כך שקיימת תת קבוצה [math]\displaystyle{ X\subseteq B }[/math] כך ש [math]\displaystyle{ R:X\times X\to X }[/math] פונקציה הפיכה.
- כיוון ש[math]\displaystyle{ B }[/math] אינסופית, יש לה תת קבוצה [math]\displaystyle{ Y\subseteq B }[/math] כך ש [math]\displaystyle{ |Y|=\aleph_0 }[/math].
- כיוון ש [math]\displaystyle{ \aleph_0\times\aleph_0=\aleph_0 }[/math] קיימת פונקציה הפיכה [math]\displaystyle{ R:Y\times Y\to Y }[/math].
- נביט ביחס ההכלה על [math]\displaystyle{ S }[/math]. לפי עקרון המקסימום של האוסדורף, קיימת שרשרת מקסימלית [math]\displaystyle{ \{R\}\subseteq M\subseteq S }[/math].
- נסמן ב[math]\displaystyle{ f }[/math] את האיחוד הכללי של השרשרת [math]\displaystyle{ f=\cup_{T\in M} T }[/math].
- נוכיח כי קיימת [math]\displaystyle{ D\subseteq B }[/math] כך ש [math]\displaystyle{ f:D\times D\to D }[/math] פונקציה הפיכה, ואף [math]\displaystyle{ |D|=|B| }[/math] וכך נסיים את ההוכחה.
- הוכחה כי [math]\displaystyle{ f\in S }[/math] פונקציה הפיכה [math]\displaystyle{ f:D\times D\to D }[/math] עבור תת קבוצה [math]\displaystyle{ D\subseteq B }[/math]:
- ראשית, נגדיר את [math]\displaystyle{ D=\{d\in B | \exists a,b\in B:((a,b),d)\in f\} }[/math]
- נוכיח כי [math]\displaystyle{ f\subseteq (D\times D)\times D }[/math]:
- יהי זוג [math]\displaystyle{ ((a,b),d)\in f }[/math], לפי ההגדרה [math]\displaystyle{ d\in D }[/math]
- כמו כן, לפי הגדרת האיחוד קיים [math]\displaystyle{ T\in M }[/math] כך ש [math]\displaystyle{ ((a,b),d)\in T }[/math].
- קיימת [math]\displaystyle{ X\subseteq B }[/math] כך ש [math]\displaystyle{ T:X\times X\to X }[/math] פונקציה הפיכה.
- כיוון ש [math]\displaystyle{ T }[/math] על, לכל [math]\displaystyle{ x\in X }[/math] קיימים [math]\displaystyle{ p,q\in X }[/math] כך ש [math]\displaystyle{ ((p,q),x)\in T }[/math] ולכן [math]\displaystyle{ ((p,q),x)\in f }[/math] ולכן [math]\displaystyle{ x\in D }[/math]
- ביחד עם העובדה ש [math]\displaystyle{ a,b\in X }[/math] נובע כי [math]\displaystyle{ a,b\in D }[/math]
- כיוון שכל איברי השרשרת הם יחסים ח"ע, גם [math]\displaystyle{ f }[/math] ח"ע.
- כיוון שכל איברי השרשרת הם יחסים חח"ע, גם [math]\displaystyle{ f }[/math] חח"ע.
- כעת נוכיח כי [math]\displaystyle{ f:D\times D\to D }[/math] יחס שלם:
- יהיו [math]\displaystyle{ d_1,d_2\in D }[/math].
- ראינו כי קיימים [math]\displaystyle{ T_1,T_2\in M }[/math] ואיברים [math]\displaystyle{ a_1,b_1,a_2,b_2\in D }[/math] כך ש [math]\displaystyle{ ((a_1,b_1),d_1)\in T_1 }[/math] וכן [math]\displaystyle{ ((a_2,b_2),d_2)\in T_2 }[/math]
- כיוון ש[math]\displaystyle{ M }[/math] שרשרת, [math]\displaystyle{ T_1\subseteq T_2 }[/math] (או ההפך) ולכן [math]\displaystyle{ a_1,a_2,b_1,b_2\in X }[/math] עבור תת קבוצה [math]\displaystyle{ X\subseteq D }[/math] כך ש [math]\displaystyle{ T_2:X\times X\to X }[/math] פונקציה הפיכה.
- לכן קיים [math]\displaystyle{ d_3\in X\subseteq D }[/math] כך ש [math]\displaystyle{ ((d_1,d_2),d_3)\in T_2 }[/math] ולכן [math]\displaystyle{ ((d_1,d_2),d_3)\in f }[/math] כלומר [math]\displaystyle{ f }[/math] שלם.
- הוכחנו כי [math]\displaystyle{ f:D\times D\to D }[/math] היא פונקציה (יחס ח"ע ושלם) חח"ע, נותר להוכיח כי היא על:
- יהי [math]\displaystyle{ d\in D }[/math]. ראינו כי קיים [math]\displaystyle{ T\in M }[/math] וקיימים [math]\displaystyle{ a,b\in D }[/math] כך ש [math]\displaystyle{ ((a,b),d)\in T }[/math] ולכן [math]\displaystyle{ ((a,b),d)\in f }[/math] ולכן הפונקציה על.
- הוכחה כי [math]\displaystyle{ |D|=|B| }[/math]:
- ראשית, נשים לב כי [math]\displaystyle{ Y\subseteq D }[/math] כיוון ש [math]\displaystyle{ R:Y\times Y\to Y }[/math] פונקציה הפיכה וכן [math]\displaystyle{ R\in M }[/math], ולכן [math]\displaystyle{ D }[/math] אינסופית.
- כעת, נזכור שהוכחנו כי [math]\displaystyle{ |D\times D|=|D| }[/math].
- נביט ב [math]\displaystyle{ B\setminus D }[/math] ונחלק למקרים:
- אם [math]\displaystyle{ |B\setminus D|\leq D }[/math] אזי:
- [math]\displaystyle{ |B|=|D|+|B\setminus D|\leq |D|+|D|\leq |D|\times |D| =|D| }[/math]
- כמובן ש [math]\displaystyle{ |D|\leq |B| }[/math] ולפי ק.ש.ב נסיק כי במקרה זה [math]\displaystyle{ |B|=|D| }[/math] וסיימנו.
- אם [math]\displaystyle{ |B\setminus D|\geq |D| }[/math] נראה כי נגיע לסתירה, ולכן מקרה זה בלתי אפשרי:
- ניקח תת קבוצה [math]\displaystyle{ U\subseteq B\setminus D }[/math] כך ש [math]\displaystyle{ |U|=|D| }[/math].
- לכן [math]\displaystyle{ |(U\times D) \cup (D\times U) \cup (U\times U)|=|D|+|D|+|D|=|D| }[/math] (הרי ראינו מקודם כי [math]\displaystyle{ |D|+|D|=|D| }[/math])
- לכן קיימת פונקציה הפיכה [math]\displaystyle{ g:(U\times D) \cup (D\times U) \cup (U\times U)\to U }[/math].
- האיחוד [math]\displaystyle{ h=f\cup g }[/math] הוא פונקציה הפיכה [math]\displaystyle{ h:(U\cup D)\times (U\cup D)\to (U\cup D) }[/math], ולכן [math]\displaystyle{ h\in S }[/math].
- ניתן להוסיף את [math]\displaystyle{ h }[/math] לשרשרת [math]\displaystyle{ M }[/math] ולהגדיל אותה, בסתירה למקסימליות שלה.
הקשר בין עוצמת הטבעיים לעוצמת הממשיים
- [math]\displaystyle{ 2^{\aleph_0}=\aleph }[/math] כלומר [math]\displaystyle{ P(\mathbb{N})\sim\mathbb{R} }[/math]