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

חומר עזר

• סיכומי ההרצאות של ד״ר ארז שיינר, ע״י אורית חסון, קיץ 2016
• מבחנים בבדידה

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

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

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

• 88-101 חשיבה מתמטית - טקסט מבוא ללוגיקה מתמטית שנכתב ע"י פרופ' עוזי וישנה

תרגול

• תרגול בנושא לוגיקה

אינדוקציה

תרגול

• תרגול בנושא אינדוקציה
• תרגילי אינדוקציה נוספים ופתרונם

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

יחסי שקילות

תרגול

• תרגול מכפלה קרטזית ויחסי שקילות

יחסי סדר

תרגול

• תרגול יחסי סדר

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

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

• תהי קבוצה 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}$

תרגול

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