הבדלים בין גרסאות בדף "מתמטיקה בדידה - ארז שיינר"

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(חח"ע ועל, תמונה ותמונה הפוכה)
(חח"ע ועל, תמונה ותמונה הפוכה)
שורה 155: שורה 155:
  
 
*שימו לב
 
*שימו לב
 +
**<math>x\in f^{-1}[Y]\iff f(x)\in Y</math>
 
**<math>y\in f[X] \iff \exist a\in X :f(a)=y \</math>
 
**<math>y\in f[X] \iff \exist a\in X :f(a)=y \</math>
 +
 +
 
<videoflash>BgCrOeJEjDo</videoflash>
 
<videoflash>BgCrOeJEjDo</videoflash>
  

גרסה מ־09:54, 9 ביוני 2020

תוכן עניינים

חומר עזר

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

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

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


תרגול

אינדוקציה

תרגול

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

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

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


  • תהי קבוצה 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\}
    • קבוצת המשלים \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\}



תרגול

יחסי סדר

  • יחס 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.


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


תרגול

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


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

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

תרגול

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

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

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



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


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

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


תרגול