חומר עזר
- סיכומי ההרצאות של ד״ר ארז שיינר, ע״י אורית חסון, קיץ 2016
- מבחנים בבדידה
- מבחנים בקורס בדידה למורים - שימו לב, הקורס למורים מכיל משמעותית פחות חומר, והמבחנים קלים יותר. יחד עם זאת, יש שם כמות גדולה של תרגילים רלוונטיים ברמה נמוכה.
סרטוני ותקציר הרצאות
פרק 1 - מבוא ללוגיקה מתמטית
פסוקים, קשרים, כמתים, פרדיקטים
תרגול
אינדוקציה
- משפט האינדוקציה המתמטית
- תהי סדרת טענות כך שמתקיימים שני התנאים הבאים:
- הטענה הראשונה נכונה.
- לכל
אם הטענה הn מתקיימת אז גם הטענה הn+1 מתקיימת.
- אזי כל הטענות בסדרה נכונות
- דוגמא:
- אינדוקציה שלמה (מלאה)
- תהי סדרת טענות כך ש:
- לכל
אם כל הטענות עד ולא כולל הטענה הn מתקיימות, אזי גם הטענה הn מתקיימת.
- לכל
- אזי כל הטענות בסדרה מתקיימות.
- שימו לב: לפני הטענה הראשונה אין טענות, ולכן כולן מתקיימות באופן ריק. כלומר מנוסח התנאי נובע שצריך להוכיח שהטענה הראשונה מתקיימת.
- פרדוקס הסוסים (או פתיתי השלג)
תרגול
פרק 2 - מבוא לתורת הקבוצות
קבוצות ופעולות על קבוצות
- איבר שייך לקבוצה
אם הוא אחד האיברים בקבוצה.
- קבוצה מוכלת בקבוצה אחרת
אם
- תהי קבוצה
ותהיינה
. נגדיר את:
- קבוצת האיחוד
- קבוצת החיתוך
- קבוצת ההפרש
- קבוצת ההפרש הסימטרי
- קבוצת המשלים
- קבוצת האיחוד
שיטות הוכחה בסיסיות
- הוכחת טענות מכומתות - טענות 'לכל' וטענות 'קיים'
- הוכחת הכלה בין קבוצות, ושיוויון בין קבוצות
איחוד וחיתוך כלליים
- תהי S קבוצה של קבוצות, נגדיר:
קבוצת החזקה
תרגול
פרק 3 - יחסים
מכפלה קרטזית ויחסים
תכונות של יחסים
- יהי R יחס על A (כלומר
) אזי:
- R נקרא רפלקסיבי אם לכל
מתקיים
.
- R נקרא סימטרי אם לכל
המקיימים
מתקיים
- R נקרא אנטי-סימטרי אם לכל
המקיימים
מתקיים
- R נקרא טרנזיטיבי אם לכל
המקיימים
מתקיים
- R נקרא מלא אם לכל
מתקיים כי
- R נקרא רפלקסיבי אם לכל
- יהי R יחס מA לB (כלומר
) אזי:
- R נקרא חד-ערכי (ח"ע) אם לכל
ולכל
המקיימים
מתקיים
- R נקרא שלם אם לכל
קיים
כך ש
- R נקרא חד-חד-ערכי (חח"ע) אם לכל
ולכל
המקיימים
מתקיים
- R נקרא על אם לכל
קיים
כך ש
- R נקרא חד-ערכי (ח"ע) אם לכל
יחסי שקילות
- יחס R על קבוצה A נקרא יחס שקילות אם הוא רפלקסיבי, סימטרי וטרנזיטיבי.
- יהי R יחס שקילות על A.
- לכל
מוגדרת קבוצת מחלקת השקילות של a ע"י:
- קבוצת כל קבוצות מחלקות השקילות נקראת קבוצת המנה:
- תהי קבוצה A. קבוצת תתי קבוצות
נקראת חלוקה של A אם:
- לכל
אם
אזי
- היחס המושרה מחלוקה:
- תהי קבוצה A ותהי חלוקה שלה U. נגדיר יחס R על A על ידי:
אם ורק אם קיימת
כך ש
- היחס המושרה מחלוקה הוא יחס שקילות.
- קבוצת המנה היא חלוקה של A.
- היחס המושרה מקבוצת המנה, הוא יחס השקילות המקורי; קבוצת המנה של יחס שקילות מושרה היא החלוקה המקורית.
תרגול
יחסי סדר
- יחס R על קבוצה A נקרא יחס סדר חלקי אם הוא רפלקסיבי, אנטי-סימטרי וטרנזיטיבי
איברים מינימליים ומקסימליים, וחסמים
- יהי R יחס סדר חלקי על קבוצה X, ותהי
תת קבוצה.
- איבר
נקרא מקסימלי בA אם לכל
המקיים
מתקיים כי
(אין גדולים ממנו)
- איבר
נקרא מינימלי בA אם לכל
המקיים
מתקיים כי
(אין קטנים ממנו)
- איבר
נקרא הגדול ביותר (מקסימום) בA אם לכל
מתקיים
(הוא גדול מכולם)
- איבר
נקרא הקטן ביותר (מינימום) בA אם לכל
מתקיים
(הוא קטן מכולם)
- איבר
נקרא חסם מלעיל של A אם לכל
מתקיים
(הוא גדול מכל איברי הקבוצה, אבל לאו דווקא נמצא בקבוצה)
- איבר
נקרא חסם מלרע של A אם לכל
מתקיים
(הוא קטן מכל איברי הקבוצה, אבל לאו דווקא נמצא בקבוצה)
- אם בקבוצת חסמי המלעיל של A יש איבר קטן ביותר הוא נקרא חסם עליון (supremum) של A.
- אם בקבוצת חסמי המלרע של A יש איבר גדול ביותר הוא נקרא חסם תחתון (infimum) של A.
- איבר
- איבר גדול ביותר ביותר הוא יחיד.
- אם חסם מלעיל שייך לקבוצה, אז הוא הגדול ביותר.
- האיבר הגדול ביותר בקבוצה הוא איבר מקסימלי, ואין איברים מקסימליים אחרים.
- האם תתכן קבוצה עם איבר מקסימלי יחיד שאינו האיבר הגדול ביותר בקבוצה?
- ביחס ההכלה על קבוצת חזקה, האיחוד הכללי של קבוצת קבוצות הוא החסם העליון שלה, והחיתוך הכללי הוא החסם התחתון.
- ביחס 'מחלק את' על הטבעיים, המחלק המשותף המקסימלי הוא החסם התחתון, והמכפלה המשותפת המינימלית הוא החסם העליון.
שרשראות
- יחס סדר חלקי R על A נקרא מלא (או לינארי, או קווי) אם:
- יהי R יחס סדר חלקי על A, ותהי
.
- אזי
נקראת שרשרת אם היחס מלא עליה, כלומר
תרגול
פרק 4 - פונקציות
הגדרת פונקציות
- יחס f מA לB נקרא פונקציה אם הוא ח"ע ושלם, ומסמנים במקרה זה
, וכן
.
- A נקרא תחום הפונקציה (או תחום הגדרה), B נקרא הטווח של הפונקציה.
- שימו לב, הסרטון ישן, ושם פונקציה הוגדרה כיחס ח"ע בלבד, בניגוד להגדרה העדכנית שלנו בקורס.
חח"ע ועל, תמונה ותמונה הפוכה
- תהי
פונקציה. אזי:
- f חח"ע אם לכל
המקיימים
מתקיים כי
- f על אם לכל
קיים
כך ש
- תהי
נגדיר את קבוצת התמונה
- תהי
נגדיר את קבוצת התמונה ההפוכה
היא פונקצית התמונה, השולחת כל תת קבוצה לקבוצת התמונה שלה
היא פונקצית התמונה ההפוכה, השולחת כל תת קבוצה לקבוצת התמונה ההפוכה שלה
- f חח"ע אם לכל
- שימו לב
הרכבת פונקציות, פונקציות הפיכות
- תהיינה
וכן
אזי נגדיר את פונקצית ההרכבה
ע"י
- פעולת ההרכבה היא אסוציאטיבית.
- תהי קבוצה A נגדיר את פונקצית הזהות
ע"י
.
- לכל פונקציה
מתקיים כי
- פונקציה
נקראת הפיכה אם קיימות פונקציות
כך ש:
וכן
- נשים לב כי
- לכן אם פונקציה הפיכה, יש פונקציה יחידה שהופכת אותה (ההופכית), נסמנה
.
- שימו לב: עם סוגריים מרובעים זו פונקצית התמונה ההפוכה שיש לכל פונקציה ופועלת על תתי קבוצות, עם סוגריים עגולים זו הפונקציה ההופכית שיש רק להפיכות ופועלת על איברים.
פונקציה מוגדרת היטב
תרגול
פרק 5 - עוצמות
מבוא
השוואת עוצמות
- A שקולת עוצמה לB או עוצמתה של A שווה לB, אם קיימת פונקציה הפיכה (חח"ע ועל)
.
- במקרה זה מסמנים
או
.
- כל קבוצה שקולת עוצמה לעצמה
- אם A שקולת עוצמה לB, גם B שקולת עוצמה לA
- אם A שקולת עוצמה לB וB שקולת עוצמה לC אזי A שקולת עוצמה לC
- עוצמתה של A קטנה או שווה לזו של B, אם קיימת פונקציה חח"ע
.
- במקרה זה מסמנים
- כל קבוצה A השקולת עוצמה לקבוצת הטבעיים מסומנת
- כל קבוצה A השקולת עוצמה לקבוצת הממשיים מסומנת
משפט קנטור
קבוצות בנות מנייה
- קבוצה A נקראת בת מנייה אם
- כל קבוצה A בת מנייה אינסופית מקיימת
חשבון עוצמות (אריתמטיקה של עוצמות)
חיבור עוצמות
- תהיינה שתי עוצמות a,b ותהיינה שתי נציגות זרות לעוצמות A,B.
- נגדיר
, הגדרה זו אינה תלוייה בבחירת הנציגות.
כפל עוצמות
- תהיינה שתי עוצמות a,b ותהיינה שתי נציגות לעוצמות A,B.
- נגדיר
, הגדרה זו אינה תלוייה בבחירת הנציגות.
חזקת עוצמות
- תהיינה שתי עוצמות a,b ותהיינה שתי נציגות לעוצמות A,B.
- נגדיר את
להיות אוסף כל הפונקציות מB לA (מהמעריך לבסיס).
- נגדיר
, הגדרה זו אינה תלוייה בבחירת הנציגות.
- חוקי חזקות
- תהיינה עוצמות a,b,c אזי
עוצמת קבוצת החזקה
השוואת חשבון עוצמות
- תהיינה עוצמות a,b,c,d כך ש
וכן
אזי:
- אם בנוסף נתון כי
אזי
משפט קנטור-שרדר-ברנשטיין
- אם
וגם
אזי
למת נקודת השבת
- תהי פונקציה עולה
כלומר המקיימת לכל
כי
- אזי קיימת נק' שבת
כך ש
.
הוכחת המשפט
עוצמות קטעים ממשיים
אקסיומת הבחירה ועקרון המקסימום של האוסדורף
אקסיומת הבחירה
- תהי S קבוצת קבוצת לא ריקות, ונסמן את האיחוד הכללי ב
.
- אזי קיימת פונקצית בחירה
הבוחרת איבר מתוך כל קבוצה, כלומר:
- דוגמא:
- תהי פונקציה על
אזי קיימת תת קבוצה
כך ש
חח"ע ועל.
- תהי פונקציה על
- תהיינה
אזי
אם ורק אם קיימת
על.
- בכיוון ראשון:
- תהי
חח"ע
- כיוון ש
קיים
- נגדיר פונקציה
באופן הבא:
- לכל
- אם קיים
כך ש
נגדיר
(בגלל החח"ע זה מוגדר היטב)
- אם
נגדיר
- לכל
- הפונקציה
שהגדרנו היא אכן על, כי לכל
מתקיים כי
- תהי
- בכיוון שני:
- תהי
על, אזי כל הקבוצות באוסף
אינן ריקות.
- ניקח פונקצית בחירה
ונגדיר
ע"י
- אכן
חח"ע כי אם
אזי
וכן
- ולכן
וכן
- תהי
עקרון המקסימום של האוסדורף
- תהי קבוצה A עם יחס סדר חלקי, תת קבוצה
נקראת שרשרת אם היחס מלא עליה (ניתן להשוות בין כל שני איברים בS).
- שרשרת נקראת מקסימלית בA אם היא אינה מוכלת באף שרשרת אחרת.
- עקרון המקסימום של האוסדורף אומר שכל שרשרת מוכלת בשרשרת מקסימלית.
- דוגמא - אוסף עיגולים במישור שאינם חותכים זה את זה, ולא ניתן להוסיף אפילו עיגול אחד נוסף.
אלף אפס היא העוצמה האינסופית הקטנה ביותר
(בהנחת עקרון המקסימום של האוסדורף)
- תהי A קבוצה אינסופית, אזי
- דרך נוספת לזו המופיעה בסרטון:
- נוכיח בהמשך כי ניתן להשוות עוצמה בין כל שתי קבוצות
- אם
, כיוון ש
אינסופית נובע כי
- אחרת,
ולכן
כפי שרצינו.
- תהי A קבוצה אינסופית, ותהי B קבוצה סופית, אזי:
איחוד בן מנייה של קבוצות בנות מנייה
(בהנחת אקסיומת הבחירה)
- תהי S קבוצה בת מנייה של קבוצות בנות מנייה, כלומר:
- אזי גם האיחוד הכללי הוא בן מנייה:
- מסקנה: אוסף תתי הקבוצות הסופיות של המספרים הטבעיים הוא בן מנייה.
- הערה לסרטון: אנחנו משתמשים באקסיומת הבחירה כאשר "בוחרים" את הפונקציות החח"ע מהקבוצות באוסף אל הטבעיים.
השוואת עוצמות
(בהנחת עיקרון המקסימום של האוסדורף)
- תהיינה שתי קבוצות A,B אזי
או
סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות
- תהיינה עוצמות
אזי:
- נניח בנוסף כי
אזי:
- נניח בנוסף כי b אינסופית, ונקבל ביחד
(המעבר
מוכח בסרטון השני).
- ולכן לפי משפט ק.ש.ב נקבל כי
- דוגמא - מה היא עוצמת קבוצת המספרים האי-רציונאליים?
(איחוד זר כמובן)
- לכן
- לכן
- לפי המשפט לעיל, סכום העוצמות הוא העוצמה הגדולה מבין השתיים.
- כיוון ש
נקבל כי
- תהי עוצמה אינסופית b אזי
הקשר בין עוצמת הטבעיים לעוצמת הממשיים
כלומר