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

מתוך Math-Wiki
הגרסה להדפסה אינה נתמכת עוד וייתכן שיש בה שגיאות תיצוג. נא לעדכן את הסימניות בדפדפן שלך ולהשתמש בפעולת ההדפסה הרגילה של הדפדפן במקום זה.

חומר עזר

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

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

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


תרגול

אינדוקציה

תרגול

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



תרגול

יחסי סדר

  • יחס R על קבוצה A נקרא יחס סדר חלקי אם הוא רפלקסיבי, אנטי-סימטרי וטרנזיטיבי

איברים מינימליים ומקסימליים, וחסמים

תרגול

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


השוואת עוצמות

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

  • תהיינה שתי קבוצות A,B אזי [math]\displaystyle{ |A|\leq|B| }[/math] או [math]\displaystyle{ |A|\geq |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]



  • תהי עוצמה אינסופית b אזי [math]\displaystyle{ b\cdot b=b }[/math]


הקשר בין עוצמת הטבעיים לעוצמת הממשיים

  • [math]\displaystyle{ 2^{\aleph_0}=\aleph }[/math] כלומר [math]\displaystyle{ P(\mathbb{N})\sim\mathbb{R} }[/math]


תרגול