שינויים
/* סרטוני ותקציר הרצאות */
*[[מדיה:16BdidaOrit.pdf|סיכומי ההרצאות של ד״ר ארז שיינר, ע״י אורית חסון, קיץ 2016]]
*[[מבחנים בבדידה]]
*[[מבחנים בקורס בדידה למורים]] - שימו לב, הקורס למורים מכיל משמעותית פחות חומר, והמבחנים קלים יותר. יחד עם זאת, יש שם כמות גדולה של תרגילים רלוונטיים ברמה נמוכה.
=סרטוני ותקציר הרצאות=
[https://www.youtube.com/playlist?list=PLHinTfsAOC-vhY2xtz4MJzkm5tefKT3Dg פלייליסט של כל הסרטונים]
==פרק 1 - מבוא ללוגיקה מתמטית==
===פסוקים, קשרים, כמתים, פרדיקטים===
===אינדוקציה===
*משפט האינדוקציה המתמטית
*תהי סדרת טענות כך שמתקיימים שני התנאים הבאים:
**הטענה הראשונה נכונה.
**לכל <math>n\in \mathbb{N}</math> אם הטענה הn מתקיימת אז גם הטענה הn+1 מתקיימת.
*אזי כל הטענות בסדרה נכונות
<videoflash>n6xkPhKmhQo</videoflash>
*אינדוקציה שלמה (מלאה)
*תהי סדרת טענות כך ש:
**לכל <math>n\in \mathbb{N}</math> אם כל הטענות עד ולא כולל הטענה הn מתקיימות, אזי גם הטענה הn מתקיימת.
*אזי כל הטענות בסדרה מתקיימות.
*שימו לב: לפני הטענה הראשונה אין טענות, ולכן כולן מתקיימות באופן ריק. כלומר מנוסח התנאי נובע שצריך להוכיח שהטענה הראשונה מתקיימת.
<videoflash>BBUxvnjuA04</videoflash>
*פרדוקס הסוסים (או פתיתי השלג)
<videoflash>E0rf-Cg3IVM</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>\{1,2\}=\{2,1\}</math>*<math>\{1,1,2\}=\{1,2\}</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>A\Delta B = (A\setminus B)\cup (B\setminus A)</math>
**קבוצת המשלים <math>\overline{A}=\{x\in U:x\not\in A\}</math>
*[[שיטות הוכחה בסיסיות]]
*הוכחת טענות מכומתות - טענות 'לכל' וטענות 'קיים'
<videoflash>QIwz6eyrcuI</videoflash>
*הוכחת הכלה בין קבוצות, ושיוויון בין קבוצות
<videoflash>Dts0NamGWbE</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 נקרא מלא אם לכל <math>a,b\in A</math> מתקיים כי <math>aRb\or bRa</math>
*לכל <math>a\in A</math> מוגדרת קבוצת '''מחלקת השקילות של a''' ע"י:
**<math>[a]_R=\{x\in A|aRx\}</math>
*קבוצת כל קבוצות מחלקות השקילות נקראת '''קבוצת המנה''':
**<math>A/R=\{[a]_R:a\in A\}</math>
*תהי קבוצה A. קבוצת תתי קבוצות <math>U\subseteq P(A)</math> נקראת '''חלוקה''' של A אם:
**<math>\cup_{X\in U}X=A</math>
**<math>\emptyset\notin U</math>
**לכל <math>X_1,X_2\in U</math> אם <math>X_1\cap X_2\neq \emptyset</math> אזי <math>X_1=x_2</math>
*היחס המושרה מחלוקה:
*תהי קבוצה A ותהי חלוקה שלה U. נגדיר יחס R על A על ידי:
**<math>aRb</math> אם ורק אם קיימת <math>X\in U</math> כך ש<math>a,b\in X</math>
*היחס המושרה מחלוקה הוא יחס שקילות.
*קבוצת המנה היא חלוקה של A.
*היחס המושרה מקבוצת המנה, הוא יחס השקילות המקורי; קבוצת המנה של יחס שקילות מושרה היא החלוקה המקורית.
**איבר <math>m\in A</math> נקרא '''מינימלי''' בA אם לכל <math>a\in A</math> המקיים <math>aRm</math> מתקיים כי <math>a=m</math> (אין קטנים ממנו)
**איבר <math>M\in A</math> נקרא '''הגדול ביותר''' (מקסימום) בA אם לכל <math>a\in A</math> מתקיים <math>aRM</math> (הוא גדול מכולם)
**איבר <math>m\in A</math> נקרא '''הקטן ביותר''' (מקסימוםמינימום) בA אם לכל <math>a\in A</math> מתקיים <math>mRa</math> (הוא קטן מכולם)
**איבר <math>M\in X</math> נקרא '''חסם מלעיל''' של A אם לכל <math>a\in A</math> מתקיים <math>aRM</math> (הוא גדול מכל איברי הקבוצה, אבל לאו דווקא נמצא בקבוצה)
**איבר <math>m\in X</math> נקרא '''חסם מלרע''' של A אם לכל <math>a\in A</math> מתקיים <math>mRa</math> (הוא קטן מכל איברי הקבוצה, אבל לאו דווקא נמצא בקבוצה)
*אם חסם מלעיל שייך לקבוצה, אז הוא הגדול ביותר.
*האיבר הגדול ביותר בקבוצה הוא איבר מקסימלי, ואין איברים מקסימליים אחרים.
*האם תתכן קבוצה עם איבר מקסימלי יחיד שאינו האיבר הגדול ביותר בקבוצה?
*ביחס ההכלה על קבוצת חזקה, האיחוד הכללי של קבוצת קבוצות הוא החסם העליון שלה, והחיתוך הכללי הוא החסם התחתון.
*ביחס 'מחלק את' על הטבעיים, המחלק המשותף המקסימלי הוא החסם התחתון, והמכפלה המשותפת המינימלית הוא החסם העליון.
<videoflash>EX6sPaiiu3k</videoflash>
====שרשראות====
*יחס סדר חלקי R על A נקרא '''מלא''' (או לינארי, או קווי) אם:
**<math>\forall a,b\in A:aRb\or bRa</math>
*יהי R יחס סדר חלקי על A, ותהי <math>S\subseteq A</math>.
*אזי <math>S</math> נקראת '''שרשרת''' אם היחס מלא עליה, כלומר <math>\forall a,b\in S:aRb\or bRa</math>
====תרגול====
==פרק 4 - פונקציות==
===הגדרת פונקציות===
*יחס f מA לB נקרא פונקציה אם הוא ח"ע ושלם, ומסמנים במקרה זה <math>f:A\to B</math>, וכן <math>f(a)=b\iff (a,b)\in f</math>.
*A נקרא תחום הפונקציה (או תחום הגדרה), B נקרא הטווח של הפונקציה.
*שימו לב, הסרטון ישן, ושם פונקציה הוגדרה כיחס ח"ע בלבד, בניגוד להגדרה העדכנית שלנו בקורס.
<videoflash>XP-SwmSlTUc</videoflash>
===חח"ע ועל, תמונה ותמונה הפוכה===
*תהי <math>f:A\to B</math> פונקציה. אזי:
**f חח"ע אם לכל <math>x_1,x_2\in A</math> המקיימים <math>f(x_1)=f(x_2)</math> מתקיים כי <math>x_1=x_2</math>
**f על אם לכל <math>y\in B</math> קיים <math>x\in A</math> כך ש<math>f(x)=y</math>
**תהי <math>X\subseteq A</math> נגדיר את קבוצת התמונה <math>f[X]=\{f(a)|a\in X\}</math>
**תהי <math>Y\subseteq B</math> נגדיר את קבוצת התמונה ההפוכה <math>f^{-1}[Y]=\{a\in A|f(a)\in Y\}</math>
**<math>f[]:P(A)\to P(B)</math> היא פונקצית התמונה, השולחת כל תת קבוצה לקבוצת התמונה שלה
**<math>f^{-1}[]:P(B)\to P(A)</math> היא פונקצית התמונה ההפוכה, השולחת כל תת קבוצה לקבוצת התמונה ההפוכה שלה
*שימו לב
**<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>
<videoflash>BgCrOeJEjDo</videoflash>
===הרכבת פונקציות, פונקציות הפיכות===
*תהיינה <math>f:A\to B</math> וכן <math>g:B\to C</math> אזי נגדיר את פונקצית ההרכבה <math>g\circ f:A\to C</math> ע"י <math>g\circ f(a)=g(f(a))</math>
*פעולת ההרכבה היא אסוציאטיבית.
*תהי קבוצה A נגדיר את '''פונקצית הזהות''' <math>I_A:A\to A</math> ע"י <math>I_A(x)=x</math>.
*לכל פונקציה <math>f:A\to B</math> מתקיים כי <math>I_B\circ f = f\circ I_A = f</math>
*פונקציה <math>f:A\to B</math> נקראת הפיכה אם קיימות פונקציות <math>g,h:B\to A</math> כך ש:
**<math>g\circ f = I_A</math> וכן <math>f\circ h = I_B</math>
*נשים לב כי
**<math>h=I_A\circ h = (g\circ f)\circ h = g\circ (f\circ h)=g\circ I_B = g</math>
*לכן אם פונקציה הפיכה, יש פונקציה יחידה שהופכת אותה (ההופכית), נסמנה <math>f^{-1}:B\to A</math>.
*שימו לב: עם סוגריים מרובעים זו פונקצית התמונה ההפוכה שיש לכל פונקציה ופועלת על תתי קבוצות, עם סוגריים עגולים זו הפונקציה ההופכית שיש רק להפיכות ופועלת על איברים.
<videoflash>t5QyDk-Mo2g</videoflash>
(בהנחת עקרון המקסימום של האוסדורף)
*תהי A קבוצה אינסופית, אזי <math>\aleph_0\leq |A|</math>
<videoflash>W4see8tTArk</videoflash>
*ולכן לפי משפט ק.ש.ב נקבל כי
**<math>a+b=a\cdot b = b</math>
*דוגמא - מה היא עוצמת קבוצת המספרים האי-רציונאליים?
*<math>\mathbb{R}=\mathbb{Q}\cup (\mathbb{R}\setminus\mathbb{Q})</math> (איחוד זר כמובן)
*לכן <math>|\mathbb{R}|=|\mathbb{Q}|+ |(\mathbb{R}\setminus\mathbb{Q})|</math>
*לכן <math>\aleph=\aleph_0 +|(\mathbb{R}\setminus\mathbb{Q})|</math>
*לפי המשפט לעיל, סכום העוצמות הוא העוצמה הגדולה מבין השתיים.
*כיוון ש <math>\aleph\neq \aleph_0</math> נקבל כי <math>|(\mathbb{R}\setminus\mathbb{Q})|=\aleph</math>
<videoflash>Ty-lY6-uRPo</videoflash>
