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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(←‏אקסיומת הבחירה)
(←‏אקסיומת הבחירה)
שורה 213: שורה 213:
 
*אזי קיימת פונקצית בחירה <math>f:S\to U</math> הבוחרת איבר מתוך כל קבוצה, כלומר:
 
*אזי קיימת פונקצית בחירה <math>f:S\to U</math> הבוחרת איבר מתוך כל קבוצה, כלומר:
 
**<math>\forall X\in S: f(X)\in X</math>
 
**<math>\forall X\in S: f(X)\in X</math>
 +
 +
 +
*דוגמא:
 +
**תהי פונקציה על <math>f:A\to B</math> אזי קיימת תת קבוצה <math>X\subseteq A</math> כך ש <math>f:X\to B</math> חח"ע ועל.
 +
  
 
<videoflash>q2OP1NCWKHU</videoflash>
 
<videoflash>q2OP1NCWKHU</videoflash>

גרסה מ־07:57, 9 ביוני 2020

תוכן עניינים

חומר עזר

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

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

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


תרגול

אינדוקציה

תרגול

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

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

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

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

קבוצת החזקה

תרגול

פרק 3 - יחסים

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

יחסי שקילות

תרגול

יחסי סדר

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

תרגול

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

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

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

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

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

תרגול

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

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

פרק 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 על.

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

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

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




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

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


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

תרגול

מקור: https://math-wiki.com/index.php?title=מתמטיקה_בדידה_-_ארז_שיינר&oldid=84529