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

מתוך 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 נקרא יחס סדר חלקי אם הוא רפלקסיבי, אנטי-סימטרי וטרנזיטיבי



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

  • יהי 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.


  • איבר גדול ביותר ביותר הוא יחיד.
  • אם חסם מלעיל שייך לקבוצה, אז הוא הגדול ביותר.
  • האיבר הגדול ביותר בקבוצה הוא איבר מקסימלי, ואין איברים מקסימליים אחרים.


תרגול

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


תרגול