הצגת המקור של מתמטיקה בדידה - ארז שיינר

=חומר עזר=
*[[מדיה:16BdidaOrit.pdf|סיכומי ההרצאות של  ד״ר ארז שיינר, ע״י אורית חסון, קיץ 2016]]
*[[מבחנים בבדידה]]

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

==פרק 1 - מבוא ללוגיקה מתמטית==
===פסוקים, קשרים, כמתים, פרדיקטים===

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

<videoflash>syqox1IXghE</videoflash>


<videoflash>1Zo7vEsnFgA</videoflash>

====תרגול====
*[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 0|תרגול בנושא לוגיקה]]

===אינדוקציה===

<videoflash>n6xkPhKmhQo</videoflash>

<videoflash>BBUxvnjuA04</videoflash>

<videoflash>E0rf-Cg3IVM</videoflash>

<videoflash>C0_36P2kOPI</videoflash>

====תרגול====
*[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 1.5|תרגול בנושא אינדוקציה]]
*[[מכינה למתמטיקה קיץ תשעב/תרגילים/4|תרגילי אינדוקציה נוספים]] ו[[מכינה למתמטיקה קיץ תשעב/תרגילים/4/פתרון 4|פתרונם]]

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

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

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


*תהי קבוצה <math>U</math> ותהיינה <math>A,B\subseteq U</math>. נגדיר את:
**קבוצת האיחוד <math>A\cup B =\{ x\in U:x\in A \or x\in B\}</math>
**קבוצת החיתוך <math>A\cap B =\{ x\in U:x\in A \and x\in B\}</math>
**קבוצת ההפרש <math>A\setminus B =\{ x\in U:x\in A \and x\not\in B\}</math>
**קבוצת המשלים <math>\overline{A}=\{x\in U:x\not\in A\}</math>


<videoflash>UgNl63BrzCM</videoflash>

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

*[[שיטות הוכחה בסיסיות]]

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

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


<videoflash>xP9VIaCCH7A</videoflash>

===קבוצת החזקה===

*<math>X\in P(A) \iff X\subseteq A</math>

<videoflash>uZVMvwbs5kw</videoflash>

===תרגול===
*[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 1|תרגול בנושא קבוצות]]

==פרק 3 - יחסים==
===מכפלה קרטזית ויחסים===
<videoflash>wyDw5XXmPp8</videoflash>


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


*יהי R יחס מA לB (כלומר <math>R\subseteq A\times B</math>) אזי:
**R

===יחסי שקילות===
<videoflash>jKprPSfRysE</videoflash>

====תרגול====
*[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 2|תרגול מכפלה קרטזית ויחסי שקילות]]

===יחסי סדר===
<videoflash>6X0OGf5CJrU</videoflash>

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

<videoflash>EX6sPaiiu3k</videoflash>

====תרגול====
*[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 3|תרגול יחסי סדר]]

==פרק 4 - פונקציות==
===הגדרת פונקציות===
<videoflash>XP-SwmSlTUc</videoflash>

===חח"ע ועל, תמונה ותמונה הפוכה===
<videoflash>BgCrOeJEjDo</videoflash>

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

<videoflash>t5QyDk-Mo2g</videoflash>

===פונקציה מוגדרת היטב===
<videoflash>HVOJmfHJmT4</videoflash>

===תרגול===

[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 4| תרגול בנושא פונקציות]]

[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 5| תרגול נוסף בנושא פונקציות]]

==פרק 5 - עוצמות==

===מבוא===
<videoflash>TG97scv77QI</videoflash>

<videoflash>Wh9MuSOLF2Q</videoflash>

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

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


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


*כל קבוצה A השקולת עוצמה לקבוצת הטבעיים מסומנת <math>|A|=\aleph_0</math>

*כל קבוצה A השקולת עוצמה לקבוצת הממשיים מסומנת <math>|A|=\aleph</math>


<videoflash>Zu0tX3VcZbg</videoflash>

===משפט קנטור===
*<math>|A|<|P(A)|</math>
<videoflash>H4IwZiUCUvM</videoflash>

===קבוצות בנות מנייה===
*קבוצה A נקראת בת מנייה אם <math>|A|\leq \aleph_0</math>

*כל קבוצה A בת מנייה אינסופית מקיימת <math>|A|=\aleph_0</math>

<videoflash>7TyjNpInOsc</videoflash>

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

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


<videoflash>eDpiO50cDmI</videoflash>

====כפל עוצמות====
*תהיינה שתי עוצמות a,b ותהיינה שתי נציגות לעוצמות A,B.
*נגדיר <math>a\cdot b=|A\times B|</math>, הגדרה זו אינה תלוייה בבחירת הנציגות.


<videoflash>AQNIw1ys8B4</videoflash>

====חזקת עוצמות====

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


<videoflash>aBV5Vt1eMG4</videoflash>

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


<videoflash>KUTIHDhwjsE</videoflash>


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

*<math>|P(A)|=2^{|A|}</math>


<videoflash>pPG6BgSY_Wg</videoflash>

====השוואת חשבון עוצמות====
*תהיינה עוצמות a,b,c,d כך ש <math>a\leq c</math> וכן <math>b\leq d</math> אזי:
**<math>a+b\leq c+d</math>
**<math>a\cdot b\leq c\cdot d</math>
*אם בנוסף נתון כי <math>c\neq 0</math> אזי
**<math>a^b\leq c^d</math>

<videoflash>i07f9wwcjtU</videoflash>

===משפט קנטור-שרדר-ברנשטיין===
*אם <math>|A|\leq |B|</math> וגם <math>|B|\leq |A|</math> אזי <math>A\sim B</math>
====למת נקודת השבת====
*תהי פונקציה עולה <math>h:P(A)\to P(A)</math> כלומר המקיימת לכל <math>X_1\subseteq X_2</math> כי <math>h(X_1)\subseteq h(X_2)</math>
*אזי קיימת נק' שבת <math>K\subseteq A</math> כך ש <math>h(K)=K</math>.
<videoflash>csJJBPs9NaI</videoflash>
====הוכחת המשפט====
<videoflash>KlZHXHxkzJk</videoflash>


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

*<math>|\mathbb{R}|=|[a,\infty)|=|[a,b]|=|(a,b)|=\aleph</math>


<videoflash>qDGHoXKOpzk</videoflash>

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


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


<videoflash>0S6r0s2SnNc</videoflash>

===אקסיומת הבחירה ועקרון המקסימום של האוסדורף===
====אקסיומת הבחירה====
*תהי S קבוצת קבוצת לא ריקות, ונסמן את האיחוד הכללי ב <math>U=\cup_{X\in S}X</math>.
*אזי קיימת פונקצית בחירה <math>f:S\to U</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>

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

<videoflash>Dl6sgVGZksk</videoflash>

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


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


<videoflash>O_uDtoDRRZ8</videoflash>

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

*תהי A קבוצה אינסופית, אזי <math>\aleph_0\leq A</math>

<videoflash>W4see8tTArk</videoflash>


*תהי A קבוצה אינסופית, ותהי B קבוצה סופית, אזי:
**<math>|A|=|A\cup B|=|A\setminus B|</math>


<videoflash>eaonM-yfR3w</videoflash>

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

*תהיינה שתי קבוצות A,B אזי <math>|A|\leq|B|</math> או <math>|A|\geq |B|</math>


<videoflash>XZkMt26fQyE</videoflash>

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

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


<videoflash>Ty-lY6-uRPo</videoflash>


*תהי עוצמה אינסופית b אזי <math>b\cdot b=b</math>


<videoflash>e6cBpbJzs2A</videoflash>

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

*<math>2^{\aleph_0}=\aleph</math> כלומר <math> P(\mathbb{N})\sim\mathbb{R}</math>


<videoflash>dhrT0edcmJE</videoflash>

===תרגול===

*[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 6|תרגול בנושא עוצמות]]
*[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 7|חשבון (אריתמטיקה) של עוצמות]]