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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש

תוכן עניינים

חומר עזר

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

פלייליסט של כל הסרטונים


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

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


תרגול

אינדוקציה

  • משפט האינדוקציה המתמטית
  • תהי סדרת טענות כך שמתקיימים שני התנאים הבאים:
    • הטענה הראשונה נכונה.
    • לכל n\in \mathbb{N} אם הטענה הn מתקיימת אז גם הטענה הn+1 מתקיימת.
  • אזי כל הטענות בסדרה נכונות


  • אינדוקציה שלמה (מלאה)
  • תהי סדרת טענות כך ש:
    • לכל n\in \mathbb{N} אם כל הטענות עד ולא כולל הטענה הn מתקיימות, אזי גם הטענה הn מתקיימת.
  • אזי כל הטענות בסדרה מתקיימות.
  • שימו לב: לפני הטענה הראשונה אין טענות, ולכן כולן מתקיימות באופן ריק. כלומר מנוסח התנאי נובע שצריך להוכיח שהטענה הראשונה מתקיימת.



  • פרדוקס הסוסים (או פתיתי השלג)


תרגול

פרק 2 - מבוא לתורת הקבוצות

קבוצות ופעולות על קבוצות

  • איבר שייך לקבוצה a\in A אם הוא אחד האיברים בקבוצה.
  • קבוצה מוכלת בקבוצה אחרת A\subseteq B אם \forall a\in A : a\in B


  • \{1,2\}=\{2,1\}
  • \{1,1,2\}=\{1,2\}


  • תהי קבוצה U ותהיינה A,B\subseteq U. נגדיר את:
    • קבוצת האיחוד A\cup B =\{ x\in U:x\in A \or x\in B\}
    • קבוצת החיתוך A\cap B =\{ x\in U:x\in A \and x\in B\}
    • קבוצת ההפרש A\setminus B =\{ x\in U:x\in A \and x\not\in B\}
    • קבוצת ההפרש הסימטרי A\Delta B = (A\setminus B)\cup (B\setminus A)
    • קבוצת המשלים \overline{A}=\{x\in U:x\not\in A\}


שיטות הוכחה בסיסיות

  • הוכחת טענות מכומתות - טענות 'לכל' וטענות 'קיים'



  • הוכחת הכלה בין קבוצות, ושיוויון בין קבוצות


איחוד וחיתוך כלליים

  • תהי S קבוצה של קבוצות, נגדיר:
    • \cup_{A\in S}A = \{x|\exists A\in S :x\in A\}
    • \cap_{A\in S}A = \{x|\forall A\in S :x\in A\}


קבוצת החזקה

  • X\in P(A) \iff X\subseteq A

תרגול

פרק 3 - יחסים

מכפלה קרטזית ויחסים


תכונות של יחסים

  • יהי R יחס על A (כלומר R\subseteq A\times A) אזי:
    • R נקרא רפלקסיבי אם לכל a\in A מתקיים aRa.
    • R נקרא סימטרי אם לכל a,b\in A המקיימים aRb מתקיים bRa
    • R נקרא אנטי-סימטרי אם לכל a,b\in A המקיימים aRb\and bRa מתקיים a=b
    • R נקרא טרנזיטיבי אם לכל a,b,c\in A המקיימים aRb \and bRc מתקיים aRc
    • R נקרא מלא אם לכל a,b\in A מתקיים כי aRb\or bRa


  • יהי R יחס מA לB (כלומר R\subseteq A\times B) אזי:
    • R נקרא חד-ערכי (ח"ע) אם לכל a\in A ולכל b_1,b_2\in B המקיימים aRb_1 \and aRb_2 מתקיים b_1=b_2
    • R נקרא שלם אם לכל a\in A קיים b\in B כך ש aRb
    • R נקרא חד-חד-ערכי (חח"ע) אם לכל a_1,a_2\in A ולכל b\in B המקיימים a_1Rb\and a_2Rb מתקיים a_1=a_2
    • R נקרא על אם לכל b\in B קיים a\in A כך ש aRb

יחסי שקילות

  • יחס R על קבוצה A נקרא יחס שקילות אם הוא רפלקסיבי, סימטרי וטרנזיטיבי.
  • יהי R יחס שקילות על A.
  • לכל a\in A מוגדרת קבוצת מחלקת השקילות של a ע"י:
    • [a]_R=\{x\in A|aRx\}
  • קבוצת כל קבוצות מחלקות השקילות נקראת קבוצת המנה:
    • A/R=\{[a]_R:a\in A\}


  • תהי קבוצה A. קבוצת תתי קבוצות U\subseteq P(A) נקראת חלוקה של A אם:
    • \cup_{X\in U}X=A
    • \emptyset\notin U
    • לכל X_1,X_2\in U אם X_1\cap X_2\neq \emptyset אזי X_1=x_2


  • היחס המושרה מחלוקה:
  • תהי קבוצה A ותהי חלוקה שלה U. נגדיר יחס R על A על ידי:
    • aRb אם ורק אם קיימת X\in U כך שa,b\in X


  • היחס המושרה מחלוקה הוא יחס שקילות.
  • קבוצת המנה היא חלוקה של A.
  • היחס המושרה מקבוצת המנה, הוא יחס השקילות המקורי; קבוצת המנה של יחס שקילות מושרה היא החלוקה המקורית.



תרגול

יחסי סדר

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



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

  • יהי R יחס סדר חלקי על קבוצה X, ותהי A\subseteq X תת קבוצה.
    • איבר M\in A נקרא מקסימלי בA אם לכל a\in A המקיים MRa מתקיים כי a=M (אין גדולים ממנו)
    • איבר m\in A נקרא מינימלי בA אם לכל a\in A המקיים aRm מתקיים כי a=m (אין קטנים ממנו)
    • איבר M\in A נקרא הגדול ביותר (מקסימום) בA אם לכל a\in A מתקיים aRM (הוא גדול מכולם)
    • איבר m\in A נקרא הקטן ביותר (מינימום) בA אם לכל a\in A מתקיים mRa (הוא קטן מכולם)
    • איבר M\in X נקרא חסם מלעיל של A אם לכל a\in A מתקיים aRM (הוא גדול מכל איברי הקבוצה, אבל לאו דווקא נמצא בקבוצה)
    • איבר m\in X נקרא חסם מלרע של A אם לכל a\in A מתקיים mRa (הוא קטן מכל איברי הקבוצה, אבל לאו דווקא נמצא בקבוצה)
    • אם בקבוצת חסמי המלעיל של A יש איבר קטן ביותר הוא נקרא חסם עליון (supremum) של A.
    • אם בקבוצת חסמי המלרע של A יש איבר גדול ביותר הוא נקרא חסם תחתון (infimum) של A.


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


  • האם תתכן קבוצה עם איבר מקסימלי יחיד שאינו האיבר הגדול ביותר בקבוצה?


  • ביחס ההכלה על קבוצת חזקה, האיחוד הכללי של קבוצת קבוצות הוא החסם העליון שלה, והחיתוך הכללי הוא החסם התחתון.
  • ביחס 'מחלק את' על הטבעיים, המחלק המשותף המקסימלי הוא החסם התחתון, והמכפלה המשותפת המינימלית הוא החסם העליון.


שרשראות

  • יחס סדר חלקי R על A נקרא מלא (או לינארי, או קווי) אם:
    • \forall a,b\in A:aRb\or bRa


  • יהי R יחס סדר חלקי על A, ותהי S\subseteq A.
  • אזי S נקראת שרשרת אם היחס מלא עליה, כלומר \forall a,b\in S:aRb\or bRa

תרגול

פרק 4 - פונקציות

הגדרת פונקציות

  • יחס f מA לB נקרא פונקציה אם הוא ח"ע ושלם, ומסמנים במקרה זה f:A\to B, וכן f(a)=b\iff (a,b)\in f.
  • A נקרא תחום הפונקציה (או תחום הגדרה), B נקרא הטווח של הפונקציה.


  • שימו לב, הסרטון ישן, ושם פונקציה הוגדרה כיחס ח"ע בלבד, בניגוד להגדרה העדכנית שלנו בקורס.


חח"ע ועל, תמונה ותמונה הפוכה

  • תהי f:A\to B פונקציה. אזי:
    • f חח"ע אם לכל x_1,x_2\in A המקיימים f(x_1)=f(x_2) מתקיים כי x_1=x_2
    • f על אם לכל y\in B קיים x\in A כך שf(x)=y
    • תהי X\subseteq A נגדיר את קבוצת התמונה f[X]=\{f(a)|a\in X\}
    • תהי Y\subseteq B נגדיר את קבוצת התמונה ההפוכה f^{-1}[Y]=\{a\in A|f(a)\in Y\}
    • f[]:P(A)\to P(B) היא פונקצית התמונה, השולחת כל תת קבוצה לקבוצת התמונה שלה
    • f^{-1}[]:P(B)\to P(A) היא פונקצית התמונה ההפוכה, השולחת כל תת קבוצה לקבוצת התמונה ההפוכה שלה


  • שימו לב
    • x\in f^{-1}[Y]\iff f(x)\in Y
    • y\in f[X] \iff \exist a\in X :f(a)=y


הרכבת פונקציות, פונקציות הפיכות

  • תהיינה f:A\to B וכן g:B\to C אזי נגדיר את פונקצית ההרכבה g\circ f:A\to C ע"י g\circ f(a)=g(f(a))
  • פעולת ההרכבה היא אסוציאטיבית.


  • תהי קבוצה A נגדיר את פונקצית הזהות I_A:A\to A ע"י I_A(x)=x.
  • לכל פונקציה f:A\to B מתקיים כי I_B\circ f = f\circ I_A = f


  • פונקציה f:A\to B נקראת הפיכה אם קיימות פונקציות g,h:B\to A כך ש:
    • g\circ f = I_A וכן f\circ h = I_B
  • נשים לב כי
    • h=I_A\circ h = (g\circ f)\circ h = g\circ (f\circ h)=g\circ I_B = g
  • לכן אם פונקציה הפיכה, יש פונקציה יחידה שהופכת אותה (ההופכית), נסמנה f^{-1}:B\to A.
  • שימו לב: עם סוגריים מרובעים זו פונקצית התמונה ההפוכה שיש לכל פונקציה ופועלת על תתי קבוצות, עם סוגריים עגולים זו הפונקציה ההופכית שיש רק להפיכות ופועלת על איברים.


פונקציה מוגדרת היטב

תרגול

תרגול בנושא פונקציות

תרגול נוסף בנושא פונקציות

פרק 5 - עוצמות

מבוא

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

  • A שקולת עוצמה לB או עוצמתה של A שווה לB, אם קיימת פונקציה הפיכה (חח"ע ועל) f:A\to B.
  • במקרה זה מסמנים A\sim B או |A|=|B|.
    • כל קבוצה שקולת עוצמה לעצמה
    • אם A שקולת עוצמה לB, גם B שקולת עוצמה לA
    • אם A שקולת עוצמה לB וB שקולת עוצמה לC אזי A שקולת עוצמה לC


  • עוצמתה של A קטנה או שווה לזו של B, אם קיימת פונקציה חח"ע f:A\to B.
  • במקרה זה מסמנים |A|\leq |B|


  • כל קבוצה A השקולת עוצמה לקבוצת הטבעיים מסומנת |A|=\aleph_0
  • כל קבוצה A השקולת עוצמה לקבוצת הממשיים מסומנת |A|=\aleph


משפט קנטור

  • |A|<|P(A)|

קבוצות בנות מנייה

  • קבוצה A נקראת בת מנייה אם |A|\leq \aleph_0
  • כל קבוצה A בת מנייה אינסופית מקיימת |A|=\aleph_0

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

חיבור עוצמות

  • תהיינה שתי עוצמות a,b ותהיינה שתי נציגות זרות לעוצמות A,B.
  • נגדיר a+b=|A\cup B|, הגדרה זו אינה תלוייה בבחירת הנציגות.


כפל עוצמות

  • תהיינה שתי עוצמות a,b ותהיינה שתי נציגות לעוצמות A,B.
  • נגדיר a\cdot b=|A\times B|, הגדרה זו אינה תלוייה בבחירת הנציגות.


חזקת עוצמות

  • תהיינה שתי עוצמות a,b ותהיינה שתי נציגות לעוצמות A,B.
  • נגדיר את A^B להיות אוסף כל הפונקציות מB לA (מהמעריך לבסיס).
  • נגדיר a^b=|A^B|, הגדרה זו אינה תלוייה בבחירת הנציגות.


  • חוקי חזקות
  • תהיינה עוצמות a,b,c אזי
    • a^b\cdot a^c = a^{b+c}
    • (a^b)^c = a^{b\cdot c}
    • a^b\cdot c^b = (a\cdot c)^b



עוצמת קבוצת החזקה

  • |P(A)|=2^{|A|}


השוואת חשבון עוצמות

  • תהיינה עוצמות a,b,c,d כך ש a\leq c וכן b\leq d אזי:
    • a+b\leq c+d
    • a\cdot b\leq c\cdot d
  • אם בנוסף נתון כי c\neq 0 אזי
    • a^b\leq c^d

משפט קנטור-שרדר-ברנשטיין

  • אם |A|\leq |B| וגם |B|\leq |A| אזי A\sim B

למת נקודת השבת

  • תהי פונקציה עולה h:P(A)\to P(A) כלומר המקיימת לכל X_1\subseteq X_2 כי h(X_1)\subseteq h(X_2)
  • אזי קיימת נק' שבת K\subseteq A כך ש h(K)=K.

הוכחת המשפט


עוצמות קטעים ממשיים

  • |\mathbb{R}|=|[a,\infty)|=|[a,b]|=|(a,b)|=\aleph


איחוד בן מנייה של קבוצות בנות מנייה

  • תהי S קבוצה בת מנייה של קבוצות בנות מנייה, כלומר:
    • |S|\leq\aleph_0
    • \forall X\in S:|X|\leq\aleph_0
  • אזי גם האיחוד הכללי הוא בן מנייה:
    • |\cup_{X\in S}X|\leq \aleph_0


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


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

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

  • תהי S קבוצת קבוצת לא ריקות, ונסמן את האיחוד הכללי ב U=\cup_{X\in S}X.
  • אזי קיימת פונקצית בחירה f:S\to U הבוחרת איבר מתוך כל קבוצה, כלומר:
    • \forall X\in S: f(X)\in X


  • דוגמא:
    • תהי פונקציה על f:A\to B אזי קיימת תת קבוצה X\subseteq A כך ש f:X\to B חח"ע ועל.


  • תהיינה A,B\neq\emptyset אזי |A|\leq |B| אם ורק אם קיימת g:B\to A על.

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

  • תהי קבוצה A עם יחס סדר חלקי, תת קבוצה S\subseteq A נקראת שרשרת אם היחס מלא עליה (ניתן להשוות בין כל שני איברים בS).
  • שרשרת נקראת מקסימלית בA אם היא אינה מוכלת באף שרשרת אחרת.
  • עקרון המקסימום של האוסדורף אומר שכל שרשרת מוכלת בשרשרת מקסימלית.


  • דוגמא - אוסף עיגולים במישור שאינם חותכים זה את זה, ולא ניתן להוסיף אפילו עיגול אחד נוסף.


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

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

  • תהי A קבוצה אינסופית, אזי \aleph_0\leq |A|


  • תהי A קבוצה אינסופית, ותהי B קבוצה סופית, אזי:
    • |A|=|A\cup B|=|A\setminus B|


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

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

  • תהיינה שתי קבוצות A,B אזי |A|\leq|B| או |A|\geq |B|


סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות

  • תהיינה עוצמות a\leq b אזי:
    • b\leq a+b
  • נניח בנוסף כי 2\leq a\leq b אזי:
    • a+b\leq a\cdot b
  • נניח בנוסף כי b אינסופית, ונקבל ביחד
    • b\leq a+b \leq a\cdot b\leq b\cdot b =b (המעבר b\cdot b=b מוכח בסרטון השני).
  • ולכן לפי משפט ק.ש.ב נקבל כי
    • a+b=a\cdot b = b


  • דוגמא - מה היא עוצמת קבוצת המספרים האי-רציונאליים?
  • \mathbb{R}=\mathbb{Q}\cup (\mathbb{R}\setminus\mathbb{Q}) (איחוד זר כמובן)
  • לכן |\mathbb{R}|=|\mathbb{Q}|+ |(\mathbb{R}\setminus\mathbb{Q})|
  • לכן \aleph=\aleph_0 +|(\mathbb{R}\setminus\mathbb{Q})|
  • לפי המשפט לעיל, סכום העוצמות הוא העוצמה הגדולה מבין השתיים.
  • כיוון ש \aleph\neq \aleph_0 נקבל כי |(\mathbb{R}\setminus\mathbb{Q})|=\aleph



  • תהי עוצמה אינסופית b אזי b\cdot b=b


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

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


תרגול