מתמטיקה בדידה - ארז שיינר
חומר עזר
סרטוני ותקציר הרצאות
פרק 1 - מבוא ללוגיקה מתמטית
פסוקים, קשרים, כמתים, פרדיקטים
תרגול
אינדוקציה
תרגול
פרק 2 - מבוא לתורת הקבוצות
קבוצות ופעולות על קבוצות
שיטות הוכחה בסיסיות
איחוד וחיתוך כלליים
קבוצת החזקה
תרגול
פרק 3 - יחסים
מכפלה קרטזית ויחסים
יחסי שקילות
תרגול
יחסי סדר
איברים מינימליים ומקסימליים, וחסמים
תרגול
פרק 4 - פונקציות
הגדרת פונקציות
חח"ע ועל, תמונה ותמונה הפוכה
הרכבת פונקציות, פונקציות הפיכות
פונקציה מוגדרת היטב
תרגול
פרק 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{ |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]
- מסקנה: אוסף תתי הקבוצות הסופיות של המספרים הטבעיים הוא בן מנייה.
אקסיומת הבחירה ועקרון המקסימום של האוסדורף
אקסיומת הבחירה
- תהי 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] על.
עקרון המקסימום של האוסדורף
- תהי קבוצה A עם יחס סדר חלקי, תת קבוצה [math]\displaystyle{ S\subseteq A }[/math] נקראת שרשרת אם היחס מלא עליה (ניתן להשוות בין כל שני איברים בS).
- שרשרת נקראת מקסימלית בA אם היא אינה מוכלת באף שרשרת אחרת.
- עקרון המקסימום של האוסדורף אומר שכל שרשרת מוכלת בשרשרת מקסימלית.
- דוגמא - אוסף עיגולים במישור שאינם חותכים זה את זה, ולא ניתן להוסיף אפילו עיגול אחד נוסף.
אלף אפס היא העוצמה האינסופית הקטנה ביותר
(בהנחת עקרון המקסימום של האוסדורף)
- תהי A קבוצה אינסופית, אזי [math]\displaystyle{ \aleph_0\leq A }[/math]
- תהי A קבוצה אינסופית, ותהי B קבוצה סופית, אזי:
- [math]\displaystyle{ |A|=|A\cup B|=|A\setminus B| }[/math]
השוואת עוצמות
סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות
הקשר בין עוצמת הטבעיים לעוצמת הממשיים