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

חומר עזר

• סיכומי ההרצאות של ד״ר ארז שיינר, ע״י אורית חסון, קיץ 2016
• מבחנים בבדידה

סרטוני ותקציר הרצאות

פרק 1 - מבוא ללוגיקה מתמטית

פסוקים, קשרים, כמתים, פרדיקטים

• 88-101 חשיבה מתמטית - טקסט מבוא ללוגיקה מתמטית שנכתב ע"י פרופ' עוזי וישנה

תרגול

• תרגול בנושא לוגיקה

אינדוקציה

תרגול

• תרגול בנושא אינדוקציה
• תרגילי אינדוקציה נוספים ופתרונם

פרק 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]

• מסקנה: אוסף תתי הקבוצות הסופיות של המספרים הטבעיים הוא בן מנייה.

אקסיומת הבחירה ועקרון המקסימום של האוסדורף

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

• תהיינה [math]\displaystyle{ A,B\neq\emptyset }[/math] אזי [math]\displaystyle{ |A|\leq |B| }[/math] אם ורק אם קיימת [math]\displaystyle{ g:B\to A }[/math] על.

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

(בהנחת עקרון המקסימום של האוסדורף)

תרגול

• תרגול בנושא עוצמות
• חשבון (אריתמטיקה) של עוצמות