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

מתמטיקה בדידה (קורס 88-195) הוא קורס יסוד לתלמידי שנה א' במתמטיקה ובמדעי המחשב באוניברסיטת בר-אילן, המציג מושגי בסיס כגון לוגיקה, קבוצות, יחסים, פונקציות, עוצמות ומבוא לקומבינטוריקה ולתורת הגרפים. הדף, שחיבר ד"ר ארז שיינר, מכיל תקציר הרצאות מלא לפי פרקים, סרטוני הרצאה, מערכי תרגול ומבחנים ובחנים עם פתרונות משנים קודמות.

חומר עזר

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

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

פלייליסט של כל הסרטונים

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

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

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

• פסוק הוא טענה מתמטית שאפשר לקבוע אם היא נכונה (אמת, [math]\displaystyle{ T }[/math]) או לא נכונה (שקר, [math]\displaystyle{ F }[/math]). זו אינה הגדרה מדויקת - את הדיוק המלא משאירים לקורס בלוגיקה מתמטית.
• קשר הוא פעולה בין פסוקים שמייצרת מהם פסוק חדש. ערך האמת של הפסוק החדש נקבע לפי ערכי האמת של הפסוקים מהם הרכבנו אותו, לפי טבלת אמת.
• ארבעת הקשרים: שלילה [math]\displaystyle{ \neg p }[/math] (לא), וגם [math]\displaystyle{ p\land q }[/math], או [math]\displaystyle{ p\lor q }[/math] וגרירה [math]\displaystyle{ p\rightarrow q }[/math] (אם [math]\displaystyle{ p }[/math] אז [math]\displaystyle{ q }[/math]). טבלאות האמת שלהם:

[math]\displaystyle{ \begin{array}{c|c|c|c|c|c}p&q&\neg p&p\land q&p\lor q&p\rightarrow q\\ \hline T&T&F&T&T&T\\ T&F&F&F&T&F\\ F&T&T&F&T&T\\ F&F&T&F&F&T\end{array} }[/math]

• ה"או" המתמטי הוא או כולל: [math]\displaystyle{ p\lor q }[/math] אמת גם כאשר שני הפסוקים אמת.
• שקר גורר כל דבר: כאשר [math]\displaystyle{ p }[/math] שקר, הגרירה [math]\displaystyle{ p\rightarrow q }[/math] אמת. למשל, הפסוק "אם 7 מתחלק ב־6 אז 7 מתחלק ב־3" הוא אמת - וכך צריך להיות, שהרי זהו מקרה פרטי של הטענה הנכונה "לכל [math]\displaystyle{ n }[/math] טבעי, אם [math]\displaystyle{ n }[/math] מתחלק ב־6 אז [math]\displaystyle{ n }[/math] מתחלק ב־3".
• אם ההנחה של הגרירה אינה מתקיימת אף פעם, אומרים שהפסוק נכון באופן ריק. למשל: "לכל מספר, אם הוא גדול מ־5 וגם קטן מ־2, אז הוא ראשוני" - פסוק אמת.
• קשר הגרירה אינו חילופי: "אם יש גשם יש עננים" נכון, אבל "אם יש עננים יש גשם" לא נכון.

• שני פסוקים נקראים שקולים, ומסמנים [math]\displaystyle{ \equiv }[/math], אם תמיד שניהם אמת או ששניהם שקר.
• כללי דה־מורגן:
  • [math]\displaystyle{ \neg(p\land q)\equiv\neg p\lor\neg q }[/math]
  • [math]\displaystyle{ \neg(p\lor q)\equiv\neg p\land\neg q }[/math]
  • למשל: נגדיר שמספר הוא "מגניב" אם הוא זוגי או ראשוני. אז מספר לא מגניב הוא מספר שאינו זוגי וגם אינו ראשוני.
• קונטרה־פוזיטיב: [math]\displaystyle{ p\rightarrow q\equiv\neg q\rightarrow\neg p }[/math]
  • למשל: "אם טור מתכנס, סדרת איבריו שואפת לאפס" שקול ל"אם סדרת איברי הטור אינה שואפת לאפס, הטור אינו מתכנס".
• גרירה באמצעות "או": [math]\displaystyle{ p\rightarrow q\equiv\neg p\lor q }[/math]
• מכאן ומכללי דה־מורגן מקבלים את שלילת הגרירה: [math]\displaystyle{ \neg(p\rightarrow q)\equiv\neg(\neg p\lor q)\equiv p\land\neg q }[/math] (ההנחה מתקיימת אבל המסקנה לא).

הוכחה. שקילות בין פסוקים המורכבים מ־[math]\displaystyle{ p,q }[/math] מוכיחים על ידי בדיקת כל ארבעת המקרים האפשריים לערכי האמת של [math]\displaystyle{ p }[/math] ו־[math]\displaystyle{ q }[/math] (טבלת אמת), לפי טבלאות האמת של הקשרים.

כללי דה־מורגן (העמודה השלישית זהה לרביעית, והחמישית זהה לשישית):

[math]\displaystyle{ \begin{array}{c|c|c|c|c|c}p&q&\neg(p\land q)&\neg p\lor\neg q&\neg(p\lor q)&\neg p\land\neg q\\ \hline T&T&F&F&F&F\\ T&F&T&T&F&F\\ F&T&T&T&F&F\\ F&F&T&T&T&T\end{array} }[/math]

שקילויות הגרירה (שלוש העמודות האחרונות זהות):

[math]\displaystyle{ \begin{array}{c|c|c|c|c}p&q&p\rightarrow q&\neg q\rightarrow\neg p&\neg p\lor q\\ \hline T&T&T&T&T\\ T&F&F&F&F\\ F&T&T&T&T\\ F&F&T&T&T\end{array} }[/math]

שלילת הגרירה נובעת משתי השקילויות הקודמות.

שימו לב שהשקילות [math]\displaystyle{ \neg(p\lor q)\equiv\neg p\land\neg q }[/math] נכונה בזכות כך שה"או" המתמטי הוא או כולל: אילו "או" היה אומר "בדיוק אחד מהשניים", במקרה ש־[math]\displaystyle{ p,q }[/math] שניהם אמת אגף שמאל היה אמת ואגף ימין שקר.

▶ ההוכחה בהרצאה מ־6.7.26, החל מהדקה 1:22:14

• פרדיקט הוא "פונקציה" שמקבלת פרמטר והופכת אותו לפסוק. למשל [math]\displaystyle{ P(n) }[/math]: "[math]\displaystyle{ n }[/math] הוא ראשוני". הפרדיקט לבדו, לפני שמציבים בו ערך, אינו פסוק.
• הכמת "לכל" [math]\displaystyle{ \forall }[/math]: הפסוק [math]\displaystyle{ \forall x\in A:Q(x) }[/math] אומר שכל איבר בקבוצה [math]\displaystyle{ A }[/math], כשמציבים אותו בפרדיקט [math]\displaystyle{ Q }[/math], נותן אמת. זוהי הכללה של "וגם".
  • במדויק, [math]\displaystyle{ \forall x\in A:Q(x) }[/math] פירושו [math]\displaystyle{ \forall x:\left((x\in A)\rightarrow Q(x)\right) }[/math]. בפרט, אם [math]\displaystyle{ A }[/math] ריקה הפסוק נכון באופן ריק.
• הכמת "קיים" [math]\displaystyle{ \exists }[/math]: הפסוק [math]\displaystyle{ \exists x\in A:Q(x) }[/math] אומר שקיים לפחות איבר אחד ב־[math]\displaystyle{ A }[/math] שמקיים את [math]\displaystyle{ Q }[/math]. זוהי הכללה של "או".
• כללי דה־מורגן לכמתים:
  • [math]\displaystyle{ \neg\forall x\in A:Q(x)\equiv\exists x\in A:\neg Q(x) }[/math]
  • [math]\displaystyle{ \neg\exists x\in A:Q(x)\equiv\forall x\in A:\neg Q(x) }[/math]
  • למשל: אם לא נכון שכל התלמידים בכיתה מעצבנים, אז קיים לפחות תלמיד אחד שאינו מעצבן.
• בעזרת ששת הסימנים [math]\displaystyle{ \forall,\exists,\land,\lor,\neg,\rightarrow }[/math] (ובעזרת הגדרות) אפשר לנסח כמעט כל טענה מתמטית.

דוגמה: האם הפסוקים בכל אחד מהזוגות הבאים שקולים?

1. "כלב נובח אינו נושך" ו"כלב נושך אינו נובח".
2. "אם לא תעשה כלים, לא יהיו לך חברים" ו"תעשה כלים או שלא יהיו לך חברים".
3. "אם הבאתי אותך לעולם הזה, אז אני יכולה לקחת אותך ממנו" ו"אם אני לא יכולה לקחת אותך מהעולם הזה, אז לא הבאתי אותך אליו".

כל שלושת הזוגות שקולים:

1. עבור כלב מסוים נסמן [math]\displaystyle{ p }[/math]: "הכלב נובח", [math]\displaystyle{ q }[/math]: "הכלב נושך". הפסוק הראשון הוא [math]\displaystyle{ p\rightarrow\neg q }[/math] והשני הוא [math]\displaystyle{ q\rightarrow\neg p }[/math]. לפי הקונטרה־פוזיטיב [math]\displaystyle{ p\rightarrow\neg q\equiv\neg\neg q\rightarrow\neg p\equiv q\rightarrow\neg p }[/math].
2. נסמן [math]\displaystyle{ p }[/math]: "תעשה כלים", [math]\displaystyle{ q }[/math]: "יהיו לך חברים". הפסוק הראשון הוא [math]\displaystyle{ \neg p\rightarrow\neg q }[/math], ולפי השקילות [math]\displaystyle{ a\rightarrow b\equiv\neg a\lor b }[/math] הוא שקול ל־[math]\displaystyle{ \neg\neg p\lor\neg q\equiv p\lor\neg q }[/math], שזה בדיוק הפסוק השני.
3. נסמן [math]\displaystyle{ p }[/math]: "הבאתי אותך לעולם הזה", [math]\displaystyle{ q }[/math]: "אני יכולה לקחת אותך ממנו". הפסוקים הם [math]\displaystyle{ p\rightarrow q }[/math] ו־[math]\displaystyle{ \neg q\rightarrow\neg p }[/math], וזו בדיוק שקילות הקונטרה־פוזיטיב.

▶ הפתרון בהרצאה מ־6.7.26, החל מהדקה 2:05:32

דוגמה: נניח ש־[math]\displaystyle{ \forall x\in A:Q(x) }[/math]. האם בהכרח נובע ש־[math]\displaystyle{ \exists x\in A:Q(x) }[/math]?

לא בהכרח. אם [math]\displaystyle{ A }[/math] ריקה, הפסוק [math]\displaystyle{ \forall x\in A:Q(x) }[/math] נכון באופן ריק: הוא אומר

[math]\displaystyle{ \forall x:\left((x\in A)\rightarrow Q(x)\right) }[/math]

ולכל [math]\displaystyle{ x }[/math] הפסוק [math]\displaystyle{ x\in A }[/math] שקר, ושקר גורר כל דבר. לעומת זאת [math]\displaystyle{ \exists x\in A:Q(x) }[/math] שקר, כי בקבוצה הריקה לא קיים איבר שמקיים משהו.

(אם [math]\displaystyle{ A }[/math] אינה ריקה, הגרירה כן נכונה: יש ב־[math]\displaystyle{ A }[/math] איבר, והוא מקיים את [math]\displaystyle{ Q }[/math] כמו כל איברי [math]\displaystyle{ A }[/math].)

▶ הפתרון בהרצאה מ־6.7.26, החל מהדקה 2:46:47

דוגמה: כתבו את הטענה "כל מספר ראשוני אינו מתחלק ב־4" באמצעות הסימונים [math]\displaystyle{ \forall,\exists,\land,\lor,\neg,\rightarrow }[/math] בלבד, כאשר כל המשתנים הם מספרים טבעיים (ללא אפס) ומותר להשתמש בכפל.

נגדיר את הפרדיקט [math]\displaystyle{ Q(n) }[/math], שאומר "[math]\displaystyle{ n }[/math] מתחלק ב־4":

[math]\displaystyle{ Q(n)=\exists k:n=4k }[/math]

נגדיר את הפרדיקט [math]\displaystyle{ P(n) }[/math], שאומר "[math]\displaystyle{ n }[/math] ראשוני": [math]\displaystyle{ n }[/math] שונה מ־1, ואין לו פירוק למכפלה של שני מספרים השונים מ־1:

[math]\displaystyle{ P(n)=\neg\left(\exists a,b:(ab=n)\land(a\ne 1)\land(b\ne 1)\right)\land(n\ne 1) }[/math]

(בלי הדרישה [math]\displaystyle{ n\ne 1 }[/math] גם 1 היה יוצא "ראשוני", שהרי לא קיימים [math]\displaystyle{ a,b\ne 1 }[/math] שמכפלתם 1.)

סה"כ ההצרנה של הטענה המקורית היא

[math]\displaystyle{ \forall n:\left(P(n)\rightarrow\neg Q(n)\right) }[/math]

▶ הפתרון בהרצאה מ־6.7.26, החל מהדקה 2:51:03

דוגמה: נניח ש־[math]\displaystyle{ A }[/math] ריקה. מי מבין הפסוק [math]\displaystyle{ \forall x\in A:Q(x) }[/math] ושלילתו [math]\displaystyle{ \exists x\in A:\neg Q(x) }[/math] נכון?

הפסוק [math]\displaystyle{ \forall x\in A:Q(x) }[/math] נכון (באופן ריק), ושלילתו [math]\displaystyle{ \exists x\in A:\neg Q(x) }[/math] שקר: ב־[math]\displaystyle{ A }[/math] אין אף איבר, ובפרט אין בה איבר שאינו מקיים את [math]\displaystyle{ Q }[/math].

זה מתאים לאינטואיציה: כדי לסתור טענת "לכל" צריך להביא איבר אחד שאינו מקיים אותה, ובקבוצה ריקה אין איבר כזה.

▶ הפתרון בהרצאה מ־6.7.26, החל מהדקה 3:10:30

דוגמה: האם הפסוקים הבאים שקולים?

[math]\displaystyle{ \forall x\in A:\left(Q(x)\lor P(x)\right) }[/math]

[math]\displaystyle{ \left(\forall x\in A:Q(x)\right)\lor\left(\forall x\in A:P(x)\right) }[/math]

לא. עצה: לספר "סיפור" מאחורי הפסוקים, אבל כמה שיותר כללי - למשל כיתה [math]\displaystyle{ A }[/math] ושתי תכונות לא קשורות של התלמידים. אם חלק מהתלמידים מקיימים רק את [math]\displaystyle{ Q }[/math] וכל השאר מקיימים רק את [math]\displaystyle{ P }[/math], הפסוק הראשון אמת (כל תלמיד מקיים לפחות אחת מהתכונות), אבל השני שקר (לא כולם מקיימים את [math]\displaystyle{ Q }[/math], וגם לא כולם מקיימים את [math]\displaystyle{ P }[/math]).

כדי להוכיח שהפסוקים אינם שקולים נותנים דוגמה מפורשת לקבוצה ולתכונות: [math]\displaystyle{ A=\{1,2\} }[/math] ו־

[math]\displaystyle{ P(1)=T,\ P(2)=F }[/math]

[math]\displaystyle{ Q(1)=F,\ Q(2)=T }[/math]

אז [math]\displaystyle{ Q(1)\lor P(1) }[/math] ו־[math]\displaystyle{ Q(2)\lor P(2) }[/math] אמת, ולכן [math]\displaystyle{ \forall x\in A:\left(Q(x)\lor P(x)\right) }[/math], כלומר הפסוק הראשון אמת.

אבל לא נכון ש־[math]\displaystyle{ \forall x\in A:Q(x) }[/math], כי [math]\displaystyle{ Q(1)=F }[/math], ולא נכון ש־[math]\displaystyle{ \forall x\in A:P(x) }[/math], כי [math]\displaystyle{ P(2)=F }[/math]. לכן הפסוק השני, שהוא "או" בין שני פסוקי שקר, שקר.

שימו לב: הפסוקים אינם שלילה זה של זה. הפסוק השני גורר את הראשון (אם כולם מקיימים את [math]\displaystyle{ Q }[/math] או שכולם מקיימים את [math]\displaystyle{ P }[/math], אז כל אחד מקיים לפחות אחת מהתכונות); הכיוון ההפוך הוא שאינו נכון.

▶ הפתרון בהרצאה מ־6.7.26, החל מהדקה 3:20:04

דוגמה: הוכיחו או הפריכו:

1. [math]\displaystyle{ \forall x\in\mathbb{R}\ \exists y\in\mathbb{R}:y<x }[/math]
2. [math]\displaystyle{ \forall x\in\mathbb{N}\ \exists y\in\mathbb{N}:y<x }[/math]

תזכורת: טענת "לכל" מוכיחים באמצעות המילה "יהי" - הוכחה שעובדת לכל איבר שיביאו לנו. למשל, להוכחת [math]\displaystyle{ \forall n\in\mathbb{N}:n+1>n }[/math]: יהי [math]\displaystyle{ n\in\mathbb{N} }[/math]; ידוע ש־[math]\displaystyle{ 1>0 }[/math], ולכן [math]\displaystyle{ n+1>n+0=n }[/math]. טענת "קיים" אפשר להוכיח באמצעות דוגמה. למשל, להוכחת [math]\displaystyle{ \exists n\in\mathbb{N}:n^2=9 }[/math] נבחר [math]\displaystyle{ n=3 }[/math]. ואין דבר כזה "הפרכה": מפריכים טענה על ידי הוכחת השלילה שלה.

1. זו טענת "לכל", ולכן נתחיל ב"יהי": יהי [math]\displaystyle{ x\in\mathbb{R} }[/math]. צ"ל שקיים [math]\displaystyle{ y\in\mathbb{R} }[/math] כך ש־[math]\displaystyle{ y<x }[/math]. נבחר [math]\displaystyle{ y=x-1 }[/math]. אכן [math]\displaystyle{ y\in\mathbb{R} }[/math] (הממשיים סגורים לחיסור) ו־[math]\displaystyle{ y<x }[/math].
2. הטענה אינה נכונה, ולכן נוכיח את שלילתה. לפי כללי דה־מורגן לכמתים (פעמיים):

   [math]\displaystyle{ \neg\left(\forall x\in\mathbb{N}\ \exists y\in\mathbb{N}:y<x\right)\equiv\exists x\in\mathbb{N}:\neg\left(\exists y\in\mathbb{N}:y<x\right) }[/math]

   [math]\displaystyle{ \equiv\exists x\in\mathbb{N}\ \forall y\in\mathbb{N}:y\geq x }[/math]

   ואכן, נבחר [math]\displaystyle{ x=0 }[/math], ולכל [math]\displaystyle{ y\in\mathbb{N} }[/math] מתקיים [math]\displaystyle{ y\geq 0 }[/math].

▶ הפתרון בהרצאה מ־8.7.26, החל מהדקה 2:03

דוגמה: האם הפסוקים הבאים שקולים?

[math]\displaystyle{ \forall x\in A\ \exists y\in B:P(x,y) }[/math]

[math]\displaystyle{ \exists y\in B\ \forall x\in A:P(x,y) }[/math]

לא. סיפור: [math]\displaystyle{ A }[/math] קבוצת בנים, [math]\displaystyle{ B }[/math] קבוצת בנות, ו־[math]\displaystyle{ P(x,y) }[/math] אומר ש־[math]\displaystyle{ x }[/math] אוהב את [math]\displaystyle{ y }[/math]. הפסוק הראשון אומר שכל בן אוהב בת כלשהי (לכל בן - בת משלו), והשני אומר שיש בת אחת שכל הבנים אוהבים.

הפרכה מפורשת: [math]\displaystyle{ A=\{1,2\} }[/math], [math]\displaystyle{ B=\{6,7\} }[/math] ו־

[math]\displaystyle{ P(1,6)=P(2,7)=T }[/math]

[math]\displaystyle{ P(1,7)=P(2,6)=F }[/math]

הפסוק הראשון אמת: עבור [math]\displaystyle{ x=1 }[/math] נבחר [math]\displaystyle{ y=6 }[/math], ועבור [math]\displaystyle{ x=2 }[/math] נבחר [math]\displaystyle{ y=7 }[/math].

הפסוק השני שקר: לא קיים [math]\displaystyle{ y\in B }[/math] כך שלכל [math]\displaystyle{ x\in A }[/math] מתקיים [math]\displaystyle{ P(x,y) }[/math], כי עבור [math]\displaystyle{ y=6 }[/math] מתקיים [math]\displaystyle{ \neg P(2,6) }[/math], ועבור [math]\displaystyle{ y=7 }[/math] מתקיים [math]\displaystyle{ \neg P(1,7) }[/math].

▶ הפתרון בהרצאה מ־8.7.26, החל מהדקה 24:47

תרגול

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

אינדוקציה

• משפט האינדוקציה המתמטית
• תהי סדרת טענות כך שמתקיימים שני התנאים הבאים:
  • הטענה הראשונה נכונה.
  • לכל [math]\displaystyle{ n\in \mathbb{N} }[/math] אם הטענה הn מתקיימת אז גם הטענה הn+1 מתקיימת.
• אזי כל הטענות בסדרה נכונות

הוכחה. נסמן את סדרת הטענות ב־[math]\displaystyle{ P_0,P_1,P_2,\dots }[/math] (הטענה הראשונה היא [math]\displaystyle{ P_0 }[/math]). בכתיב לוגי המשפט אומר:

[math]\displaystyle{ \left(P_0\land\forall n\in\mathbb{N}:(P_n\rightarrow P_{n+1})\right)\rightarrow\forall n\in\mathbb{N}:P_n }[/math]

נב"ש שהתנאים מתקיימים, כלומר [math]\displaystyle{ P_0\land\forall n\in\mathbb{N}:(P_n\rightarrow P_{n+1}) }[/math], אבל לא כל הטענות נכונות, כלומר [math]\displaystyle{ \neg\forall n\in\mathbb{N}:P_n }[/math] (זו שלילת הגרירה: [math]\displaystyle{ \neg(p\rightarrow q)\equiv p\land\neg q }[/math]).

לכן קיימת בסדרה טענה שאינה נכונה. נסמן ב־[math]\displaystyle{ k }[/math] את המקום הראשון שבו הטענה [math]\displaystyle{ P_k }[/math] אינה מתקיימת.

לא ייתכן ש־[math]\displaystyle{ k=0 }[/math], כי נתון ש־[math]\displaystyle{ P_0 }[/math] אמת. לכן [math]\displaystyle{ k\geq 1 }[/math], וקיימת גם הטענה [math]\displaystyle{ P_{k-1} }[/math]. היא מתקיימת, שהרי [math]\displaystyle{ P_k }[/math] היא הראשונה שאינה מתקיימת.

אבל מהנתון (עבור [math]\displaystyle{ n=k-1 }[/math]) מתקיים [math]\displaystyle{ P_{k-1}\rightarrow P_k }[/math], ולכן [math]\displaystyle{ P_k }[/math] מתקיימת - סתירה.

▶ ההוכחה בהרצאה מ־8.7.26, החל מהדקה 54:28

• בפועל, הוכחה באינדוקציה נכתבת כך:
  • בדיקה: מראים שהטענה הראשונה נכונה.
  • צעד: "יהי [math]\displaystyle{ n }[/math] עבורו הטענה נכונה, צ"ל את הטענה ה־[math]\displaystyle{ n+1 }[/math]". זהו קיצור להוכחת טענת ה"לכל" [math]\displaystyle{ \forall n:(P_n\rightarrow P_{n+1}) }[/math], ולכן היא מתחילה ב"יהי".

• דוגמא:
• [math]\displaystyle{ \sum_{k=1}^{2^{n-1}}\frac{1}{k} > \frac{n}{2} }[/math]

דוגמה: הוכיחו באינדוקציה כי לכל [math]\displaystyle{ n\in\mathbb{N} }[/math] מתקיים [math]\displaystyle{ n<2^n }[/math].

לפי עקרון האינדוקציה צריך להוכיח כי

[math]\displaystyle{ 0<2^0\ \land\ \forall n\in\mathbb{N}:\left(n<2^n\rightarrow n+1<2^{n+1}\right) }[/math]

בדיקה: ברור כי [math]\displaystyle{ 0<1=2^0 }[/math].

צעד: יהי [math]\displaystyle{ n }[/math] עבורו הטענה נכונה, צ"ל את הטענה עבור [math]\displaystyle{ n+1 }[/math]. כלומר נתון [math]\displaystyle{ n<2^n }[/math], וצ"ל [math]\displaystyle{ n+1<2^{n+1} }[/math]. אכן, לפי הנתון ומכיוון ש־[math]\displaystyle{ 2^0\leq 2^n }[/math]:

[math]\displaystyle{ n+1<2^n+1=2^n+2^0 }[/math]

[math]\displaystyle{ \leq 2^n+2^n=2\cdot 2^n=2^{n+1} }[/math]

▶ הפתרון בהרצאה מ־8.7.26, החל מהדקה 1:05:16

דוגמה (אי־שוויון ברנולי): יהי [math]\displaystyle{ a>-1 }[/math]. הוכיחו כי לכל [math]\displaystyle{ n\in\mathbb{N} }[/math] מתקיים [math]\displaystyle{ (1+a)^n\geq 1+na }[/math].

נוכיח באינדוקציה.

בדיקה: עבור [math]\displaystyle{ n=0 }[/math]: [math]\displaystyle{ (1+a)^0=1=1+0\cdot a }[/math], ובפרט [math]\displaystyle{ (1+a)^0\geq 1+0\cdot a }[/math].

צעד: יהי [math]\displaystyle{ n }[/math] עבורו הטענה נכונה, צ"ל עבור [math]\displaystyle{ n+1 }[/math]. כלומר נתון [math]\displaystyle{ (1+a)^n\geq 1+na }[/math], וצ"ל [math]\displaystyle{ (1+a)^{n+1}\geq 1+(n+1)a }[/math].

נתון [math]\displaystyle{ 1+a>0 }[/math], ולכן מותר לכפול בו את שני אגפי הנתון:

[math]\displaystyle{ (1+a)^{n+1}\geq(1+a)(1+na)=1+a+na+na^2 }[/math]

[math]\displaystyle{ =1+(n+1)a+na^2\geq 1+(n+1)a }[/math]

כאשר בצעד האחרון השתמשנו בכך ש־[math]\displaystyle{ na^2\geq 0 }[/math].

▶ הפתרון בהרצאה מ־8.7.26, החל מהדקה 1:17:44

דוגמה: נתון לוח בגודל [math]\displaystyle{ 2^n\times 2^n }[/math] משבצות, כאשר [math]\displaystyle{ 1\leq n\in\mathbb{N} }[/math], שמשבצת אחת בו חסרה. האם אפשר לרצף את הלוח באריחים בצורת האות ר' (שלוש משבצות: משבצת, משבצת מעליה ומשבצת משמאלה; מותר לסובב את האריחים)?

כן. נוכיח באינדוקציה על [math]\displaystyle{ n }[/math].

בדיקה: עבור [math]\displaystyle{ n=1 }[/math], לוח בגודל [math]\displaystyle{ 2\times 2 }[/math] בלי משבצת אחת הוא בדיוק אריח אחד (בסיבוב המתאים).

צעד: יהי [math]\displaystyle{ n }[/math] עבורו הטענה נכונה, צ"ל עבור [math]\displaystyle{ n+1 }[/math]. יהי לוח בגודל [math]\displaystyle{ 2^{n+1}\times 2^{n+1} }[/math] עם משבצת חסרה; צ"ל שאפשר לרצף אותו.

נחלק את הלוח ל־4 לוחות בגודל [math]\displaystyle{ 2^n\times 2^n }[/math]. באחד מהם נמצאת המשבצת החסרה, ולפי הנחת האינדוקציה אפשר לרצף אותו.

נניח אריח אחד צמוד למרכז הלוח, כך שמשבצת אחת שלו נמצאת בכל אחד משלושת הלוחות הנותרים (בפינה הסמוכה למרכז). כעת בכל אחד משלושת הלוחות האלה יש משבצת אחת "חסרה" (שכבר מכוסה), ולכן לפי הנחת האינדוקציה אפשר לרצף גם אותם. סה"כ ריצפנו את כל הלוח.

(ההוכחה נותנת גם שיטה רקורסיבית לרצף את הלוח בפועל.)

▶ הפתרון בהרצאה מ־8.7.26, החל מהדקה 2:16:51

• אינדוקציה שלמה (מלאה)
• תהי סדרת טענות כך ש:
  • לכל [math]\displaystyle{ n\in \mathbb{N} }[/math] אם כל הטענות עד ולא כולל הטענה הn מתקיימות, אזי גם הטענה הn מתקיימת.
• אזי כל הטענות בסדרה מתקיימות.
• שימו לב: לפני הטענה הראשונה אין טענות, ולכן כולן מתקיימות באופן ריק. כלומר מנוסח התנאי נובע שצריך להוכיח שהטענה הראשונה מתקיימת.

הוכחה. כמעט זהה להוכחת משפט האינדוקציה. נסמן את הטענות ב־[math]\displaystyle{ P_0,P_1,P_2,\dots }[/math]; התנאי הוא

[math]\displaystyle{ \forall n\in\mathbb{N}:\left((\forall k<n:P_k)\rightarrow P_n\right) }[/math]

נב"ש שהתנאי מתקיים אבל לא כל הטענות נכונות, ונסמן ב־[math]\displaystyle{ m }[/math] את המקום הראשון שבו הטענה [math]\displaystyle{ P_m }[/math] אינה מתקיימת.

כיוון ש־[math]\displaystyle{ P_m }[/math] היא הטענה הראשונה שאינה מתקיימת, כל הטענות עד ולא כולל [math]\displaystyle{ P_m }[/math] מתקיימות (אם [math]\displaystyle{ m=0 }[/math] - באופן ריק). לכן לפי התנאי עבור [math]\displaystyle{ n=m }[/math], גם [math]\displaystyle{ P_m }[/math] מתקיימת - סתירה.

בהוכחת משפט האינדוקציה הרגיל השתמשנו רק בכך שהטענה שלפני הטענה הראשונה שנכשלה מתקיימת; כאן משתמשים בכך שכל הטענות שלפניה מתקיימות.

▶ ההוכחה בהרצאה מ־8.7.26, החל מהדקה 2:01:34

• בפועל ההוכחה נכתבת כמו באינדוקציה רגילה, ורק מילה אחת מתחלפת: בדיקה של הטענה הראשונה, ואז "יהי [math]\displaystyle{ n }[/math] עד אליו הטענה נכונה, צ"ל את הטענה ה־[math]\displaystyle{ n+1 }[/math]" (במקום "יהי [math]\displaystyle{ n }[/math] עבורו הטענה נכונה").

דוגמה: הוכיחו שכל מספר טבעי גדול מ־1 הוא ראשוני או מכפלה של ראשוניים. (מספר ראשוני הוא מספר גדול מ־1 שמתחלק רק בעצמו וב־1.)

ניסיון באינדוקציה רגילה: בדיקה: [math]\displaystyle{ n=2 }[/math] אכן ראשוני. יהי [math]\displaystyle{ n }[/math] עבורו הטענה נכונה, צ"ל עבור [math]\displaystyle{ n+1 }[/math]. אם [math]\displaystyle{ n+1 }[/math] ראשוני, סיימנו. אחרת יש לו מחלק [math]\displaystyle{ a }[/math] כך ש־[math]\displaystyle{ 1<a<n+1 }[/math], כלומר [math]\displaystyle{ n+1=ab }[/math] כאשר [math]\displaystyle{ 1<a,b\leq n }[/math]. כאן יש בעיה: אנחנו יודעים שהטענה נכונה עבור [math]\displaystyle{ n }[/math], אבל לא בטוחים שהיא נכונה עבור [math]\displaystyle{ a,b }[/math]. בשביל זה צריך את עקרון האינדוקציה השלמה.

הוכחה באינדוקציה שלמה: בדיקה: [math]\displaystyle{ n=2 }[/math] ראשוני. יהי [math]\displaystyle{ n }[/math] עד אליו הטענה נכונה, צ"ל עבור [math]\displaystyle{ n+1 }[/math]. אם [math]\displaystyle{ n+1 }[/math] ראשוני, סיימנו. אחרת, כמו קודם, [math]\displaystyle{ n+1=ab }[/math] כאשר [math]\displaystyle{ 1<a,b\leq n }[/math]. כיוון שהנחנו שעד [math]\displaystyle{ n }[/math] (כולל) הטענה מתקיימת, כל אחד מ־[math]\displaystyle{ a,b }[/math] הוא ראשוני או מכפלה של ראשוניים, ולכן

[math]\displaystyle{ n+1=a\cdot b }[/math]

הוא מכפלה של ראשוניים.

▶ הפתרון בהרצאה מ־8.7.26, החל מהדקה 1:58:03

• פרדוקס הסוסים (או פתיתי השלג)

תרגול

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

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

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

• איבר שייך לקבוצה [math]\displaystyle{ a\in A }[/math] אם הוא אחד האיברים בקבוצה.
• קבוצה מוכלת בקבוצה אחרת [math]\displaystyle{ A\subseteq B }[/math] אם [math]\displaystyle{ \forall a\in A : a\in B }[/math]

• שתי קבוצות שוות, [math]\displaystyle{ A=B }[/math], אם ורק אם [math]\displaystyle{ A\subseteq B }[/math] וגם [math]\displaystyle{ B\subseteq A }[/math] (הכלה דו-כיוונית). זו למעשה האקסיומה הראשונה של תורת הקבוצות: קבוצה נקבעת אך ורק על ידי האיברים השייכים לה, ללא חשיבות לסדר ולחזרות.

• [math]\displaystyle{ \{1,2\}=\{2,1\} }[/math]
• [math]\displaystyle{ \{1,1,2\}=\{1,2\} }[/math]

• איבר של קבוצה יכול להיות בעצמו קבוצה. למשל [math]\displaystyle{ 1\in\{1,\{1,2\}\} }[/math] וגם [math]\displaystyle{ \{1,2\}\in\{1,\{1,2\}\} }[/math], אבל [math]\displaystyle{ 2\notin\{1,\{1,2\}\} }[/math].

• פרדוקס ראסל: אוסף כל הקבוצות שאינן שייכות לעצמן, [math]\displaystyle{ X=\{A\mid A\notin A\} }[/math], אינו יכול להיות קבוצה. המסקנה היא שאין "קבוצה של כל הקבוצות", ולכן, למשל, משלים של קבוצה מגדירים רק ביחס לקבוצת עולם [math]\displaystyle{ U }[/math] מוסכמת.

הוכחה. נב"ש ש־[math]\displaystyle{ X }[/math] קבוצה, ונשאל האם [math]\displaystyle{ X\in X }[/math].

• אם [math]\displaystyle{ X\in X }[/math], אז [math]\displaystyle{ X }[/math] מקיימת את התנאי של איברי [math]\displaystyle{ X }[/math], כלומר [math]\displaystyle{ X\notin X }[/math]. סתירה.
• לכן [math]\displaystyle{ X\notin X }[/math]. אבל אז [math]\displaystyle{ X }[/math] מקיימת את התנאי [math]\displaystyle{ A\notin A }[/math] של איברי [math]\displaystyle{ X }[/math], ולכן [math]\displaystyle{ X\in X }[/math]. שוב סתירה.

בשני המקרים קיבלנו סתירה, ולכן [math]\displaystyle{ X }[/math] אינה קבוצה. (ההגדרה של "קבוצת כל הקבוצות" מעגלית, בדומה למשפט "משפט זה הוא שקר".) ▶ ההוכחה בהרצאה מ־8.7.26, החל מהדקה 2:36:12

• הערה: בתורת הקבוצות האקסיומטית לא מגדירים מהי קבוצה; מתחילים מהקבוצה הריקה ובונים ממנה את כל השאר. למשל, המספרים הטבעיים מוגדרים כך: [math]\displaystyle{ 0=\emptyset }[/math], [math]\displaystyle{ 1=\{\emptyset\}=\{0\} }[/math], [math]\displaystyle{ 2=\{\emptyset,\{\emptyset\}\}=\{0,1\} }[/math], ובאופן כללי [math]\displaystyle{ n=\{0,1,\dots,n-1\} }[/math]. בפרט [math]\displaystyle{ 0\in 1 }[/math] אבל [math]\displaystyle{ 1\notin 1 }[/math].

• תהי קבוצה [math]\displaystyle{ U }[/math] ותהיינה [math]\displaystyle{ A,B\subseteq U }[/math]. נגדיר את:
  • קבוצת האיחוד [math]\displaystyle{ A\cup B =\{ x\in U:x\in A \or x\in B\} }[/math]
  • קבוצת החיתוך [math]\displaystyle{ A\cap B =\{ x\in U:x\in A \and x\in B\} }[/math]
  • קבוצת ההפרש [math]\displaystyle{ A\setminus B =\{ x\in U:x\in A \and x\not\in B\} }[/math]
  • קבוצת ההפרש הסימטרי [math]\displaystyle{ A\Delta B = (A\setminus B)\cup (B\setminus A) }[/math]
  • קבוצת המשלים [math]\displaystyle{ \overline{A}=\{x\in U:x\not\in A\} }[/math]

דוגמה: תהיינה [math]\displaystyle{ A=\{1,2\} }[/math] ו־[math]\displaystyle{ B=\{2,3\} }[/math], בעולם [math]\displaystyle{ U=\{1,2,3,4\} }[/math]. חשבו את [math]\displaystyle{ A\cup B }[/math], [math]\displaystyle{ A\cap B }[/math], [math]\displaystyle{ A\setminus B }[/math], [math]\displaystyle{ A\Delta B }[/math] ו־[math]\displaystyle{ \overline{A} }[/math].

[math]\displaystyle{ A\cup B=\{1,2,3\} }[/math]

[math]\displaystyle{ A\cap B=\{2\} }[/math]

[math]\displaystyle{ A\setminus B=\{1\} }[/math]

[math]\displaystyle{ A\Delta B=(A\setminus B)\cup(B\setminus A)=\{1\}\cup\{3\}=\{1,3\} }[/math]

[math]\displaystyle{ \overline{A}=U\setminus A=\{3,4\} }[/math]

שימו לב שהמשלים תלוי בעולם: בלי עולם מוסכם אי אפשר לדעת מי נמצא ב־[math]\displaystyle{ \overline{A} }[/math] (למשל, אם [math]\displaystyle{ U=\{1,2,3\} }[/math] אז [math]\displaystyle{ \overline{A}=\{3\} }[/math]). ▶ הפתרון בהרצאה מ־13.7.26, החל מהדקה 22:45

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

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

• הוכחת טענות מכומתות - טענות 'לכל' וטענות 'קיים'

• הוכחת הכלה בין קבוצות, ושיוויון בין קבוצות

• הכלה היא טרנזיטיבית: אם [math]\displaystyle{ A\subseteq B }[/math] וגם [math]\displaystyle{ B\subseteq C }[/math], אזי [math]\displaystyle{ A\subseteq C }[/math].

הוכחה. טענת הכלה היא טענת "לכל", ולכן ההוכחה מתחילה ב"יהי". יהי [math]\displaystyle{ x\in A }[/math]; צ"ל [math]\displaystyle{ x\in C }[/math]. כיוון ש־[math]\displaystyle{ A\subseteq B }[/math], נובע [math]\displaystyle{ x\in B }[/math]. כיוון ש־[math]\displaystyle{ B\subseteq C }[/math], נובע [math]\displaystyle{ x\in C }[/math]. מש"ל. ▶ ההוכחה בהרצאה מ־13.7.26, החל מהדקה 1:10:55

דוגמה: תנו טענה שקולה לכך ש־[math]\displaystyle{ A\neq B }[/math], במונחי האיברים של הקבוצות.

[math]\displaystyle{ A\neq B }[/math]

[math]\displaystyle{ \iff \neg(A=B) }[/math]

[math]\displaystyle{ \iff \neg(A\subseteq B\land B\subseteq A) }[/math]

[math]\displaystyle{ \iff A\not\subseteq B\ \lor\ B\not\subseteq A }[/math]

[math]\displaystyle{ \iff \neg(\forall a\in A:a\in B)\ \lor\ \neg(\forall b\in B:b\in A) }[/math]

[math]\displaystyle{ \iff (\exists a\in A:a\notin B)\ \lor\ (\exists b\in B:b\notin A) }[/math]

המעברים: הגדרת השוויון (הכלה דו-כיוונית), כלל דה מורגן, הגדרת ההכלה, ושלילת הכמת "לכל". כלומר: קיים איבר של [math]\displaystyle{ A }[/math] שאינו ב־[math]\displaystyle{ B }[/math], או שקיים איבר של [math]\displaystyle{ B }[/math] שאינו ב־[math]\displaystyle{ A }[/math]. (טעות נפוצה היא לרשום רק אחד משני הצדדים.) ▶ הפתרון בהרצאה מ־8.7.26, החל מהדקה 3:15:32

דוגמה: מצאו תנאי השקול לכך ש־[math]\displaystyle{ A\not\subseteq B\cup C }[/math].

לפי הגדרת ההכלה, [math]\displaystyle{ A\not\subseteq B\cup C }[/math] פירושו שלא כל איבר של [math]\displaystyle{ A }[/math] נמצא ב־[math]\displaystyle{ B\cup C }[/math], כלומר קיים [math]\displaystyle{ a\in A }[/math] כך ש־[math]\displaystyle{ a\notin B\cup C }[/math]. לפי הגדרת האיחוד, [math]\displaystyle{ a\notin B\cup C }[/math] פירושו [math]\displaystyle{ \neg(a\in B\lor a\in C) }[/math], ולפי דה מורגן זה שקול ל־[math]\displaystyle{ a\notin B }[/math] וגם [math]\displaystyle{ a\notin C }[/math]. לכן:

[math]\displaystyle{ A\not\subseteq B\cup C\iff \exists a\in A:\ (a\notin B\land a\notin C) }[/math]

▶ הפתרון בהרצאה מ־13.7.26, החל מהדקה 10:24

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

• תהי S קבוצה של קבוצות, נגדיר:
  • [math]\displaystyle{ \cup_{A\in S}A = \{x|\exists A\in S :x\in A\} }[/math]
  • [math]\displaystyle{ \cap_{A\in S}A = \{x|\forall A\in S :x\in A\} }[/math] (עבור [math]\displaystyle{ S\neq\emptyset }[/math])

• כתיב אינדקסים: תהי [math]\displaystyle{ I }[/math] קבוצה (של אינדקסים), ולכל [math]\displaystyle{ i\in I }[/math] תהי [math]\displaystyle{ A_i }[/math] קבוצה. האינדקסים אינם חייבים להיות מספרים טבעיים, ואפילו לא מספרים, אבל תמיד צריך לומר מהיכן הם מגיעים. האיחוד והחיתוך של האוסף [math]\displaystyle{ \{A_i\mid i\in I\} }[/math] הם:
  • [math]\displaystyle{ \bigcup_{i\in I}A_i=\{x\mid \exists i\in I: x\in A_i\} }[/math] - האיברים השייכים ללפחות אחת מהקבוצות
  • [math]\displaystyle{ \bigcap_{i\in I}A_i=\{x\mid \forall i\in I: x\in A_i\} }[/math] (כאשר [math]\displaystyle{ I\neq\emptyset }[/math]) - האיברים השייכים לכל הקבוצות
• למשל, עבור [math]\displaystyle{ A_n=\{n,n+1\} }[/math] כאשר [math]\displaystyle{ 1\le n\in\mathbb{N} }[/math], האיחוד הוא [math]\displaystyle{ \{1,2\}\cup\{2,3\}\cup\{3,4\}\cup\cdots=\{1,2,3,\dots\} }[/math], ואילו החיתוך ריק (אין מספר השייך לכל הקבוצות).

דוגמה: נביט באוסף הקבוצות [math]\displaystyle{ S=\{\{x\in\mathbb{R}\mid x^2=c\}\mid c\in\mathbb{R}\} }[/math]. אילו קבוצות יש ב־[math]\displaystyle{ S }[/math], ומהו האיחוד [math]\displaystyle{ \bigcup_{A\in S}A }[/math]?

מציבים את כל הערכים הממשיים של [math]\displaystyle{ c }[/math]:

• לכל [math]\displaystyle{ c<0 }[/math]: [math]\displaystyle{ \{x\in\mathbb{R}\mid x^2=c\}=\emptyset }[/math].
• עבור [math]\displaystyle{ c=0 }[/math]: [math]\displaystyle{ \{x\in\mathbb{R}\mid x^2=0\}=\{0\} }[/math].
• לכל [math]\displaystyle{ c>0 }[/math]: [math]\displaystyle{ \{x\in\mathbb{R}\mid x^2=c\}=\{-\sqrt{c},\sqrt{c}\} }[/math].

לכן [math]\displaystyle{ S=\{\emptyset,\{0\},\{-1,1\},\dots\} }[/math], כלומר [math]\displaystyle{ S }[/math] מכילה את [math]\displaystyle{ \emptyset }[/math], את [math]\displaystyle{ \{0\} }[/math] ואת כל הקבוצות [math]\displaystyle{ \{-\sqrt{c},\sqrt{c}\} }[/math] עבור [math]\displaystyle{ c>0 }[/math]. (הקבוצה הריקה מתקבלת מכל [math]\displaystyle{ c<0 }[/math], אבל היא איבר אחד של [math]\displaystyle{ S }[/math].) האיחוד הוא [math]\displaystyle{ \mathbb{R} }[/math]: כל איברי הקבוצות ב־[math]\displaystyle{ S }[/math] הם מספרים ממשיים, ולהפך, לכל [math]\displaystyle{ x\in\mathbb{R} }[/math] נבחר [math]\displaystyle{ c=x^2 }[/math], ואז [math]\displaystyle{ x }[/math] שייך לקבוצה [math]\displaystyle{ \{y\in\mathbb{R}\mid y^2=c\} }[/math] שהיא איבר של [math]\displaystyle{ S }[/math]. החיתוך, לעומת זאת, ריק, שהרי [math]\displaystyle{ \emptyset\in S }[/math]. ▶ הפתרון בהרצאה מ־13.7.26, החל מהדקה 27:19

דוגמה: נסמן [math]\displaystyle{ (a,b)=\{x\in\mathbb{R}\mid a<x<b\} }[/math]. חשבו והוכיחו את תשובתכם: [math]\displaystyle{ \bigcup_{n\in\mathbb{N}}\left(\frac{1}{n+1},1\right) }[/math] (כאן [math]\displaystyle{ 0\in\mathbb{N} }[/math]).

זהו האיחוד [math]\displaystyle{ (1,1)\cup\left(\frac{1}{2},1\right)\cup\left(\frac{1}{3},1\right)\cup\cdots }[/math] (עבור [math]\displaystyle{ n=0 }[/math] מתקבל [math]\displaystyle{ (1,1)=\emptyset }[/math]). הקטעים הולכים וגדלים, והקצה השמאלי שלהם מתקרב ל־0, ולכן ניחוש:

[math]\displaystyle{ \bigcup_{n\in\mathbb{N}}\left(\frac{1}{n+1},1\right)=(0,1) }[/math]

הוכחה. זו טענת שוויון בין קבוצות, ולכן נוכיח הכלה דו-כיוונית.

• [math]\displaystyle{ \subseteq }[/math]: יהי [math]\displaystyle{ x\in\bigcup_{n\in\mathbb{N}}\left(\frac{1}{n+1},1\right) }[/math]; צ"ל [math]\displaystyle{ x\in(0,1) }[/math]. לפי הגדרת האיחוד קיים [math]\displaystyle{ n\in\mathbb{N} }[/math] כך ש־[math]\displaystyle{ x\in\left(\frac{1}{n+1},1\right) }[/math], כלומר [math]\displaystyle{ \frac{1}{n+1}<x<1 }[/math]. כיוון ש־[math]\displaystyle{ \frac{1}{n+1}>0 }[/math], נובע [math]\displaystyle{ 0<x<1 }[/math], ולכן [math]\displaystyle{ x\in(0,1) }[/math].
• [math]\displaystyle{ \supseteq }[/math]: יהי [math]\displaystyle{ x\in(0,1) }[/math]; צ"ל שקיים [math]\displaystyle{ n\in\mathbb{N} }[/math] כך ש־[math]\displaystyle{ \frac{1}{n+1}<x<1 }[/math]. אי השוויון [math]\displaystyle{ x<1 }[/math] נתון, ולכן נותר למצוא [math]\displaystyle{ n\in\mathbb{N} }[/math] כך ש־[math]\displaystyle{ \frac{1}{n+1}<x }[/math]. כיוון שהמספרים [math]\displaystyle{ x }[/math] ו־[math]\displaystyle{ n+1 }[/math] חיוביים, זה שקול ל־[math]\displaystyle{ \frac{1}{x}<n+1 }[/math], כלומר ל־[math]\displaystyle{ n>\frac{1}{x}-1 }[/math]. ברור שקיים מספר טבעי כזה (תכונת ארכימדס). מש"ל.

▶ הפתרון בהרצאה מ־13.7.26, החל מהדקה 40:46

דוגמה: נסמן [math]\displaystyle{ (n,\infty)=\{x\in\mathbb{R}\mid x>n\} }[/math]. חשבו והוכיחו את תשובתכם: [math]\displaystyle{ \bigcap_{n\in\mathbb{N}}(n,\infty) }[/math].

זהו החיתוך [math]\displaystyle{ (0,\infty)\cap(1,\infty)\cap(2,\infty)\cap\cdots }[/math]. נוכיח כי

[math]\displaystyle{ \bigcap_{n\in\mathbb{N}}(n,\infty)=\emptyset }[/math]

כאשר צריך להוכיח שקבוצה ריקה, מניחים בשלילה שהיא אינה ריקה. נב"ש שקיים [math]\displaystyle{ x\in\bigcap_{n\in\mathbb{N}}(n,\infty) }[/math]. כיוון ש־[math]\displaystyle{ x }[/math] בחיתוך, הוא שייך לכל הקבוצות, ובפרט [math]\displaystyle{ x\in(0,\infty) }[/math]; לכן [math]\displaystyle{ x }[/math] מספר ממשי. לפי תכונת ארכימדס קיים [math]\displaystyle{ n\in\mathbb{N} }[/math] כך ש־[math]\displaystyle{ n>x }[/math], ולכן [math]\displaystyle{ x\notin(n,\infty) }[/math], בסתירה לכך ש־[math]\displaystyle{ x }[/math] שייך לכל הקבוצות בחיתוך. מש"ל. ▶ הפתרון בהרצאה מ־13.7.26, החל מהדקה 1:00:20

דוגמה (שאלה מבוחן): נגדיר [math]\displaystyle{ A_1=\{1\} }[/math], [math]\displaystyle{ B_1=\{2\} }[/math], ולכל [math]\displaystyle{ n }[/math] טבעי (כאן [math]\displaystyle{ \mathbb{N}=\{1,2,3,\dots\} }[/math]):

[math]\displaystyle{ A_{n+1}=B_n\cup\{x+2^n\mid x\in A_n\} }[/math]

[math]\displaystyle{ B_{n+1}=A_n\cup\{x+2^n\mid x\in B_n\} }[/math]

• (א) כתבו במפורש את הקבוצות [math]\displaystyle{ A_2,B_2 }[/math].
• (ב) הוכיחו, באינדוקציה או בכל דרך אחרת, כי לכל [math]\displaystyle{ n }[/math] טבעי מתקיים [math]\displaystyle{ A_n\cup B_n=\{x\in\mathbb{N}\mid 1\le x\le 2^n\} }[/math].
• (ג) הוכיחו כי [math]\displaystyle{ \bigcup_{n\in\mathbb{N}}A_n=\mathbb{N} }[/math].

(א) נציב [math]\displaystyle{ n=1 }[/math] בשתי המשוואות:

[math]\displaystyle{ A_2=B_1\cup\{x+2\mid x\in A_1\}=\{2\}\cup\{3\}=\{2,3\} }[/math]

[math]\displaystyle{ B_2=A_1\cup\{x+2\mid x\in B_1\}=\{1\}\cup\{4\}=\{1,4\} }[/math]

(ולשם ההבנה, עבור [math]\displaystyle{ n=2 }[/math]: [math]\displaystyle{ A_3=B_2\cup\{x+4\mid x\in A_2\}=\{1,4,6,7\} }[/math] ו־[math]\displaystyle{ B_3=A_2\cup\{x+4\mid x\in B_2\}=\{2,3,5,8\} }[/math].)

(ב) באינדוקציה על [math]\displaystyle{ n }[/math]. בדיקה: עבור [math]\displaystyle{ n=1 }[/math] אכן [math]\displaystyle{ A_1\cup B_1=\{1,2\}=\{x\in\mathbb{N}\mid 1\le x\le 2^1\} }[/math]. יהי [math]\displaystyle{ n }[/math] עבורו הטענה מתקיימת, כלומר [math]\displaystyle{ A_n\cup B_n=\{x\in\mathbb{N}\mid 1\le x\le 2^n\} }[/math]; צ"ל [math]\displaystyle{ A_{n+1}\cup B_{n+1}=\{x\in\mathbb{N}\mid 1\le x\le 2^{n+1}\} }[/math]. לפי הגדרת הקבוצות (ולפי חילופיות וקיבוציות האיחוד):

[math]\displaystyle{ A_{n+1}\cup B_{n+1}=(A_n\cup B_n)\cup\{x+2^n\mid x\in A_n\}\cup\{x+2^n\mid x\in B_n\} }[/math]

[math]\displaystyle{ =(A_n\cup B_n)\cup\{x+2^n\mid x\in A_n\cup B_n\} }[/math]

ולפי הנחת האינדוקציה (בשני המקומות):

[math]\displaystyle{ =\{x\in\mathbb{N}\mid 1\le x\le 2^n\}\cup\{x+2^n\mid x\in\mathbb{N},\ 1\le x\le 2^n\} }[/math]

[math]\displaystyle{ =\{x\in\mathbb{N}\mid 1\le x\le 2^n\}\cup\{x\in\mathbb{N}\mid 2^n+1\le x\le 2^n+2^n\} }[/math]

[math]\displaystyle{ =\{x\in\mathbb{N}\mid 1\le x\le 2^{n+1}\} }[/math]

שהרי [math]\displaystyle{ 2^n+2^n=2\cdot 2^n=2^{n+1} }[/math].

(ג) זו טענת שוויון בין קבוצות, ולכן נוכיח הכלה דו-כיוונית.

• [math]\displaystyle{ \subseteq }[/math]: יהי [math]\displaystyle{ x\in\bigcup_{n\in\mathbb{N}}A_n }[/math]; אז קיים [math]\displaystyle{ n\in\mathbb{N} }[/math] כך ש־[math]\displaystyle{ x\in A_n }[/math], ולכן לפי סעיף (ב) [math]\displaystyle{ x\in A_n\cup B_n\subseteq\mathbb{N} }[/math].
• [math]\displaystyle{ \supseteq }[/math]: יהי [math]\displaystyle{ k\in\mathbb{N} }[/math]; צ"ל שקיים [math]\displaystyle{ n }[/math] כך ש־[math]\displaystyle{ k\in A_n }[/math]. נבחר [math]\displaystyle{ m\in\mathbb{N} }[/math] כך ש־[math]\displaystyle{ k\le 2^m }[/math] (למשל [math]\displaystyle{ m=k }[/math]). לפי סעיף (ב) [math]\displaystyle{ k\in A_m\cup B_m }[/math]. אם [math]\displaystyle{ k\in A_m }[/math] סיימנו. אחרת [math]\displaystyle{ k\in B_m }[/math], ולכן [math]\displaystyle{ k\in A_{m+1} }[/math], שהרי [math]\displaystyle{ A_{m+1}=B_m\cup\{x+2^m\mid x\in A_m\}\supseteq B_m }[/math]. בשני המקרים [math]\displaystyle{ k }[/math] שייך לאחת הקבוצות [math]\displaystyle{ A_n }[/math], ולכן לאיחוד. מש"ל.

▶ הפתרון בהרצאה מ־13.7.26, החל מהדקה 1:11:30; המשכו בהרצאה מ־15.7.26, החל מהדקה 4:12

קבוצת החזקה

• [math]\displaystyle{ X\in P(A) \iff X\subseteq A }[/math]

• הקבוצה הריקה מוכלת בכל קבוצה: לכל קבוצה [math]\displaystyle{ A }[/math] מתקיים [math]\displaystyle{ \emptyset\subseteq A }[/math], וכן [math]\displaystyle{ A\subseteq A }[/math]. לכן תמיד [math]\displaystyle{ \emptyset\in P(A) }[/math] וגם [math]\displaystyle{ A\in P(A) }[/math].

הוכחה. נוכיח ש־[math]\displaystyle{ \emptyset\subseteq A }[/math] בשתי דרכים.

• באופן ריק: לפי ההגדרה, [math]\displaystyle{ \emptyset\subseteq A }[/math] פירושו [math]\displaystyle{ \forall x:\ x\in\emptyset\Rightarrow x\in A }[/math]. הרישא [math]\displaystyle{ x\in\emptyset }[/math] תמיד שקרית, ושקר גורר כל דבר, ולכן הטענה נכונה.
• בשלילה: נב"ש ש־[math]\displaystyle{ \emptyset\not\subseteq A }[/math]. אז קיים [math]\displaystyle{ x\in\emptyset }[/math] כך ש־[math]\displaystyle{ x\notin A }[/math], סתירה, שהרי אין איברים בקבוצה הריקה.

כמו כן [math]\displaystyle{ A\subseteq A }[/math], שהרי כל [math]\displaystyle{ a\in A }[/math] מקיים [math]\displaystyle{ a\in A }[/math]. כעת, כיוון ש־[math]\displaystyle{ X\in P(A)\iff X\subseteq A }[/math], נקבל [math]\displaystyle{ \emptyset\in P(A) }[/math] ו־[math]\displaystyle{ A\in P(A) }[/math]. ▶ ההוכחה בהרצאה מ־13.7.26, החל מהדקה 32:44

• תהיינה קבוצות [math]\displaystyle{ A,B }[/math]. אזי [math]\displaystyle{ A\subseteq B }[/math] אם ורק אם [math]\displaystyle{ P(A)\subseteq P(B) }[/math].

הוכחה. זו טענת "אם ורק אם", ולכן נוכיח שתי גרירות, אחת בכל כיוון. בכל כיוון צריך להוכיח הכלה, כלומר טענת "לכל", ולכן ההוכחה מתחילה ב"יהי".

כיוון ראשון. נתון [math]\displaystyle{ A\subseteq B }[/math], צ"ל [math]\displaystyle{ P(A)\subseteq P(B) }[/math]. תהי [math]\displaystyle{ X\in P(A) }[/math] (איברי [math]\displaystyle{ P(A) }[/math] הם קבוצות); צ"ל [math]\displaystyle{ X\in P(B) }[/math]. כלומר, נתון [math]\displaystyle{ X\subseteq A }[/math] וצ"ל [math]\displaystyle{ X\subseteq B }[/math]. זה נובע מ־[math]\displaystyle{ X\subseteq A }[/math] ו־[math]\displaystyle{ A\subseteq B }[/math] לפי הטרנזיטיביות של ההכלה.

כיוון שני. נתון [math]\displaystyle{ P(A)\subseteq P(B) }[/math], צ"ל [math]\displaystyle{ A\subseteq B }[/math].

• דרך ראשונה: יהי [math]\displaystyle{ a\in A }[/math]; צ"ל [math]\displaystyle{ a\in B }[/math]. נביט ביחידון [math]\displaystyle{ \{a\} }[/math]. מתקיים [math]\displaystyle{ \{a\}\subseteq A }[/math], ולכן [math]\displaystyle{ \{a\}\in P(A) }[/math]. לפי הנתון [math]\displaystyle{ \{a\}\in P(B) }[/math], כלומר [math]\displaystyle{ \{a\}\subseteq B }[/math], ולכן [math]\displaystyle{ a\in B }[/math].
• דרך שנייה (מתחילה ב"הברקה" ולא בתבנית): [math]\displaystyle{ A\subseteq A }[/math], ולכן [math]\displaystyle{ A\in P(A) }[/math]. לפי הנתון [math]\displaystyle{ A\in P(B) }[/math], כלומר [math]\displaystyle{ A\subseteq B }[/math].

מש"ל. ▶ ההוכחה בהרצאה מ־13.7.26, החל מהדקה 58:07

דוגמה: חשבו את [math]\displaystyle{ P(\emptyset) }[/math], את [math]\displaystyle{ P(P(\emptyset)) }[/math] ואת [math]\displaystyle{ P(P(P(\emptyset))) }[/math].

כדי לא להתבלבל, כדאי לעקוב בכל שלב אחרי מספר האיברים בקבוצה.

• לקבוצה הריקה אין איברים, ויש לה תת־קבוצה אחת בלבד, היא עצמה: [math]\displaystyle{ P(\emptyset)=\{\emptyset\} }[/math].
• לקבוצה [math]\displaystyle{ \{\emptyset\} }[/math] יש איבר אחד, ולכן שתי תתי־קבוצות: [math]\displaystyle{ P(P(\emptyset))=P(\{\emptyset\})=\{\emptyset,\{\emptyset\}\} }[/math]. (באותו אופן [math]\displaystyle{ P(\{0\})=\{\emptyset,\{0\}\} }[/math]; למעשה זו אותה קבוצה, שהרי [math]\displaystyle{ 0=\emptyset }[/math].)
• לקבוצה [math]\displaystyle{ \{\emptyset,\{\emptyset\}\} }[/math] יש שני איברים. לכל קבוצה עם שני איברים [math]\displaystyle{ P(\{a,b\})=\{\emptyset,\{a\},\{b\},\{a,b\}\} }[/math], ונציב [math]\displaystyle{ a=\emptyset }[/math], [math]\displaystyle{ b=\{\emptyset\} }[/math]:

[math]\displaystyle{ P(P(P(\emptyset)))=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\emptyset,\{\emptyset\}\}\} }[/math]

▶ הפתרון בהרצאה מ־13.7.26, החל מהדקה 28:19

דוגמה: קבעו אילו מהטענות הבאות נכונות: [math]\displaystyle{ \{1\}\in\{\{1\},\{2\}\} }[/math], [math]\displaystyle{ 1\in\{\{1\},\{2\}\} }[/math], [math]\displaystyle{ \{1\}\subseteq\{\{1\},\{2\}\} }[/math], [math]\displaystyle{ \emptyset\subseteq\{\{1\},\{2\}\} }[/math], [math]\displaystyle{ \emptyset\in\{\{1\},\{2\}\} }[/math].

לקבוצה [math]\displaystyle{ \{\{1\},\{2\}\} }[/math] יש בדיוק שני איברים, [math]\displaystyle{ \{1\} }[/math] ו־[math]\displaystyle{ \{2\} }[/math], וכל אובייקט אחר אינו שייך לה. לכן:

• [math]\displaystyle{ \{1\}\in\{\{1\},\{2\}\} }[/math] נכון.
• [math]\displaystyle{ 1\in\{\{1\},\{2\}\} }[/math] לא נכון, כי [math]\displaystyle{ 1 }[/math] אינו אחד משני האיברים ([math]\displaystyle{ 1\neq\{1\} }[/math]).
• [math]\displaystyle{ \{1\}\subseteq\{\{1\},\{2\}\} }[/math] לא נכון: האיבר היחיד של [math]\displaystyle{ \{1\} }[/math] הוא [math]\displaystyle{ 1 }[/math], והוא אינו שייך לקבוצה.
• [math]\displaystyle{ \emptyset\subseteq\{\{1\},\{2\}\} }[/math] נכון: הקבוצה הריקה מוכלת בכל קבוצה.
• [math]\displaystyle{ \emptyset\in\{\{1\},\{2\}\} }[/math] לא נכון: [math]\displaystyle{ \emptyset }[/math] אינו אחד משני האיברים.

הוספה או השמטה של סוגריים מסולסלים משנה את האובייקט. ▶ הפתרון בהרצאה מ־13.7.26, החל מהדקה 43:32

דוגמה: תהי [math]\displaystyle{ A=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\emptyset,\{\emptyset\}\}\} }[/math] (זו בדיוק [math]\displaystyle{ P(P(P(\emptyset))) }[/math] מהדוגמה הקודמת). קבעו אילו מהטענות הבאות נכונות: [math]\displaystyle{ \{\{\emptyset\}\}\in A }[/math], [math]\displaystyle{ \{\{\emptyset\}\}\subseteq A }[/math], [math]\displaystyle{ \{\emptyset,\{\{\emptyset\}\}\}\subseteq A }[/math], [math]\displaystyle{ \{\{\emptyset\},\emptyset\}\in A }[/math], [math]\displaystyle{ \{\{\{\emptyset\}\}\}\in A }[/math], [math]\displaystyle{ \{\{\{\emptyset\}\}\}\subseteq A }[/math].

ב־[math]\displaystyle{ A }[/math] יש ארבעה איברים: [math]\displaystyle{ \emptyset }[/math], [math]\displaystyle{ \{\emptyset\} }[/math], [math]\displaystyle{ \{\{\emptyset\}\} }[/math] ו־[math]\displaystyle{ \{\emptyset,\{\emptyset\}\} }[/math]. "שייך ל־[math]\displaystyle{ A }[/math]" פירושו "הוא אחד מארבעת האיברים", ו"מוכל ב־[math]\displaystyle{ A }[/math]" פירושו "כל אחד מאיבריו הוא אחד מארבעת האיברים".

• [math]\displaystyle{ \{\{\emptyset\}\}\in A }[/math] נכון: זה האיבר השלישי.
• [math]\displaystyle{ \{\{\emptyset\}\}\subseteq A }[/math] נכון: האיבר היחיד שלה, [math]\displaystyle{ \{\emptyset\} }[/math], הוא האיבר השני של [math]\displaystyle{ A }[/math].
• [math]\displaystyle{ \{\emptyset,\{\{\emptyset\}\}\}\subseteq A }[/math] נכון: [math]\displaystyle{ \emptyset }[/math] ו־[math]\displaystyle{ \{\{\emptyset\}\} }[/math] הם האיבר הראשון והשלישי של [math]\displaystyle{ A }[/math].
• [math]\displaystyle{ \{\{\emptyset\},\emptyset\}\in A }[/math] נכון: זו הקבוצה [math]\displaystyle{ \{\emptyset,\{\emptyset\}\} }[/math] (הסדר לא משנה), האיבר הרביעי.
• [math]\displaystyle{ \{\{\{\emptyset\}\}\}\in A }[/math] לא נכון: זה אינו אחד מארבעת האיברים.
• [math]\displaystyle{ \{\{\{\emptyset\}\}\}\subseteq A }[/math] נכון: האיבר היחיד שלה, [math]\displaystyle{ \{\{\emptyset\}\} }[/math], שייך ל־[math]\displaystyle{ A }[/math].

▶ הפתרון בהרצאה מ־13.7.26, החל מהדקה 51:15

תרגול

• תרגול בנושא קבוצות

פרק 3 - יחסים

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

• תהיינה קבוצות A,B. המכפלה הקרטזית שלהן היא קבוצת כל הזוגות הסדורים שהאיבר הראשון בהם מA והשני מB:
  • [math]\displaystyle{ A\times B=\{(a,b)\mid a\in A,\ b\in B\} }[/math]
• יחס מA לB הוא תת קבוצה של המכפלה הקרטזית, כלומר [math]\displaystyle{ R\subseteq A\times B }[/math] (אוסף של "חצים" מאיברי A לאיברי B). אם [math]\displaystyle{ R\subseteq A\times A }[/math] אומרים כי R הוא יחס על A.
• סימון: [math]\displaystyle{ aRb }[/math] פירושו [math]\displaystyle{ (a,b)\in R }[/math].
• דוגמאות:
  • [math]\displaystyle{ R=\{(n,n+1)\mid n\in\mathbb{N}\} }[/math] הוא יחס על הטבעיים: כל מספר מתייחס לעוקב שלו.
  • [math]\displaystyle{ R=\{(x,y)\in\mathbb{R}\times\mathbb{R}\mid x^2+y^2=1\} }[/math] הוא יחס על הממשיים, והגרף שלו הוא מעגל היחידה.
  • [math]\displaystyle{ R=\{(X,n)\in P(\mathbb{N})\times\mathbb{N}\mid n\in X\} }[/math] הוא יחס מ[math]\displaystyle{ P(\mathbb{N}) }[/math] ל[math]\displaystyle{ \mathbb{N} }[/math] (יחס השייכות); למשל [math]\displaystyle{ (\{1,2,3\},1)\in R }[/math].
  • הקבוצה הריקה היא יחס בין כל שתי קבוצות (אף איבר אינו מתייחס לאף איבר).

דוגמה: תהי A קבוצה בת 4 איברים ותהי B קבוצה בת 5 איברים. כמה יחסים יש מA לB?

יחס מA לB הוא תת קבוצה של [math]\displaystyle{ A\times B }[/math], ולכן קבוצת כל היחסים מA לB היא בדיוק קבוצת החזקה [math]\displaystyle{ P(A\times B) }[/math].

ב[math]\displaystyle{ A\times B }[/math] יש [math]\displaystyle{ 4\cdot 5=20 }[/math] זוגות סדורים (כל ה"חצים" האפשריים), ולכן מספר היחסים הוא

[math]\displaystyle{ |P(A\times B)|=2^{|A\times B|}=2^{20} }[/math]

במילים: לכל אחד מ־20 החצים האפשריים בוחרים אם הוא שייך ליחס או לא.

▶ הפתרון בהרצאה מ־15.7.26, החל מהדקה 59:26

תכונות של יחסים

• יהי R יחס על A (כלומר [math]\displaystyle{ R\subseteq A\times A }[/math]) אזי:
  • R נקרא רפלקסיבי אם לכל [math]\displaystyle{ a\in A }[/math] מתקיים [math]\displaystyle{ aRa }[/math].
  • R נקרא סימטרי אם לכל [math]\displaystyle{ a,b\in A }[/math] המקיימים [math]\displaystyle{ aRb }[/math] מתקיים [math]\displaystyle{ bRa }[/math]
  • R נקרא אנטי-סימטרי אם לכל [math]\displaystyle{ a,b\in A }[/math] המקיימים [math]\displaystyle{ aRb\and bRa }[/math] מתקיים [math]\displaystyle{ a=b }[/math]
  • R נקרא טרנזיטיבי אם לכל [math]\displaystyle{ a,b,c\in A }[/math] המקיימים [math]\displaystyle{ aRb \and bRc }[/math] מתקיים [math]\displaystyle{ aRc }[/math]
  • R נקרא מלא אם לכל [math]\displaystyle{ a,b\in A }[/math] מתקיים כי [math]\displaystyle{ aRb\or bRa }[/math]

• יהי R יחס מA לB (כלומר [math]\displaystyle{ R\subseteq A\times B }[/math]) אזי:
  • R נקרא חד-ערכי (ח"ע) אם לכל [math]\displaystyle{ a\in A }[/math] ולכל [math]\displaystyle{ b_1,b_2\in B }[/math] המקיימים [math]\displaystyle{ aRb_1 \and aRb_2 }[/math] מתקיים [math]\displaystyle{ b_1=b_2 }[/math]
  • R נקרא שלם אם לכל [math]\displaystyle{ a\in A }[/math] קיים [math]\displaystyle{ b\in B }[/math] כך ש [math]\displaystyle{ aRb }[/math]
  • R נקרא חד-חד-ערכי (חח"ע) אם לכל [math]\displaystyle{ a_1,a_2\in A }[/math] ולכל [math]\displaystyle{ b\in B }[/math] המקיימים [math]\displaystyle{ a_1Rb\and a_2Rb }[/math] מתקיים [math]\displaystyle{ a_1=a_2 }[/math]
  • R נקרא על אם לכל [math]\displaystyle{ b\in B }[/math] קיים [math]\displaystyle{ a\in A }[/math] כך ש [math]\displaystyle{ aRb }[/math]

יחסי שקילות

📄 דף נושא: יחסים ויחס שקילות - הגדרות, דוגמאות פתורות, שאלות ממבחנים וסרטונים

• יחס R על קבוצה A נקרא יחס שקילות אם הוא רפלקסיבי, סימטרי וטרנזיטיבי.

דוגמה: נגדיר יחס R על [math]\displaystyle{ \mathbb{Z} }[/math] ע"י [math]\displaystyle{ R=\{(0,0)\}\cup\{(a,b)\in\mathbb{Z}\times\mathbb{Z}\mid a\cdot b>0\} }[/math]. הוכיחו כי R יחס שקילות.

רפלקסיביות. יהי [math]\displaystyle{ a\in\mathbb{Z} }[/math], צריך להוכיח [math]\displaystyle{ (a,a)\in R }[/math]. אם [math]\displaystyle{ a=0 }[/math] אכן [math]\displaystyle{ (0,0)\in R }[/math]. אחרת [math]\displaystyle{ a\neq 0 }[/math], ולכן [math]\displaystyle{ a\cdot a>0 }[/math] ולכן [math]\displaystyle{ (a,a)\in R }[/math].

סימטריות. יהיו [math]\displaystyle{ a,b\in\mathbb{Z} }[/math] כך ש[math]\displaystyle{ aRb }[/math], צריך להוכיח [math]\displaystyle{ bRa }[/math]. אם [math]\displaystyle{ (a,b)=(0,0) }[/math] אז [math]\displaystyle{ (b,a)=(0,0)\in R }[/math]. אחרת [math]\displaystyle{ a\cdot b>0 }[/math], ולכן גם [math]\displaystyle{ b\cdot a>0 }[/math], כלומר [math]\displaystyle{ (b,a)\in R }[/math].

טרנזיטיביות. יהיו [math]\displaystyle{ a,b,c\in\mathbb{Z} }[/math] כך ש[math]\displaystyle{ aRb\land bRc }[/math], צריך להוכיח [math]\displaystyle{ aRc }[/math]. נשים לב שבזוגות מהקבוצה הימנית באיחוד אין אפס באף צד של הזוג, שהרי המכפלה שלהם חיובית.

• אם [math]\displaystyle{ (a,b)=(0,0) }[/math] אז [math]\displaystyle{ b=0 }[/math], ולכן גם [math]\displaystyle{ (b,c)=(0,0) }[/math], כלומר [math]\displaystyle{ c=0 }[/math]. לכן [math]\displaystyle{ (a,c)=(0,0)\in R }[/math].
• אחרת [math]\displaystyle{ a\cdot b>0 }[/math], ולכן [math]\displaystyle{ b\neq 0 }[/math], ולכן גם [math]\displaystyle{ b\cdot c>0 }[/math]. נכפול את שני אי-השוויונות:

  [math]\displaystyle{ (ab)(bc)=ac\cdot b^2>0 }[/math]

  ומכיוון ש־[math]\displaystyle{ b^2>0 }[/math] נקבל [math]\displaystyle{ ac>0 }[/math], כלומר [math]\displaystyle{ (a,c)\in R }[/math].

היחס מחלק את השלמים לשלוש קבוצות: החיוביים, השליליים, ואפס לבדו (ראו את מחלקות השקילות שלו בהמשך).

▶ הפתרון בהרצאה מ־15.7.26, החל מהדקה 2:26:01

דוגמה: נגדיר יחס S על אוסף הנקודות במישור [math]\displaystyle{ \mathbb{R}\times\mathbb{R} }[/math] ע"י: [math]\displaystyle{ (a,b)S(c,d) }[/math] אם ורק אם המרחק בין הנקודות קטן או שווה ל־1, כלומר [math]\displaystyle{ \sqrt{(a-c)^2+(b-d)^2}\leq 1 }[/math]. האם S יחס שקילות?

(למשל [math]\displaystyle{ \neg\big((0,0)S(1,1)\big) }[/math], כי המרחק בין הנקודות הוא [math]\displaystyle{ \sqrt{2}>1 }[/math].)

רפלקסיביות - מתקיימת. תהי נקודה [math]\displaystyle{ (a,b)\in\mathbb{R}\times\mathbb{R} }[/math]. אכן [math]\displaystyle{ \sqrt{(a-a)^2+(b-b)^2}=0\leq 1 }[/math], ולכן [math]\displaystyle{ (a,b)S(a,b) }[/math].

סימטריות - מתקיימת. תהיינה נקודות [math]\displaystyle{ (a,b),(c,d) }[/math] כך ש[math]\displaystyle{ (a,b)S(c,d) }[/math]. אז

[math]\displaystyle{ \sqrt{(c-a)^2+(d-b)^2}=\sqrt{(a-c)^2+(b-d)^2}\leq 1 }[/math]

ולכן [math]\displaystyle{ (c,d)S(a,b) }[/math].

טרנזיטיביות - לא מתקיימת. נוכיח את השלילה. שלילת הטרנזיטיביות היא

[math]\displaystyle{ \neg\big(\forall x,y,z:xSy\land ySz\rightarrow xSz\big) }[/math]

[math]\displaystyle{ \equiv\exists x,y,z:xSy\land ySz\land\neg(xSz) }[/math]

(שהרי [math]\displaystyle{ \neg(p\rightarrow q)\equiv p\land\neg q }[/math]). נבחר את הנקודות [math]\displaystyle{ (0,0),(1,0),(2,0) }[/math]. אכן [math]\displaystyle{ (0,0)S(1,0) }[/math] ו[math]\displaystyle{ (1,0)S(2,0) }[/math] (המרחק בכל זוג הוא 1), אבל [math]\displaystyle{ \neg\big((0,0)S(2,0)\big) }[/math] כי המרחק ביניהן הוא 2.

לכן S אינו יחס שקילות.

▶ הפתרון בהרצאה מ־15.7.26, החל מהדקה 2:52:59

• יהי R יחס שקילות על A.
• לכל [math]\displaystyle{ a\in A }[/math] מוגדרת קבוצת מחלקת השקילות של a ע"י:
  • [math]\displaystyle{ [a]_R=\{x\in A|aRx\} }[/math]
• קבוצת כל מחלקות השקילות נקראת קבוצת המנה:
  • [math]\displaystyle{ A/R=\{[a]_R:a\in A\} }[/math]

דוגמה: מצאו את מחלקות השקילות ואת קבוצת המנה של יחס השקילות [math]\displaystyle{ R=\{(0,0)\}\cup\{(a,b)\in\mathbb{Z}\times\mathbb{Z}\mid a\cdot b>0\} }[/math] על [math]\displaystyle{ \mathbb{Z} }[/math].

• [math]\displaystyle{ [0]_R=\{0\} }[/math]: לכל [math]\displaystyle{ x }[/math] מתקיים [math]\displaystyle{ 0\cdot x=0 }[/math], ולכן הזוג היחיד ביחס שהאיבר הראשון בו הוא 0 הוא [math]\displaystyle{ (0,0) }[/math].
• אם [math]\displaystyle{ a>0 }[/math] אז [math]\displaystyle{ aRx }[/math] אם ורק אם [math]\displaystyle{ a\cdot x>0 }[/math], כלומר אם ורק אם [math]\displaystyle{ x>0 }[/math]. לכן למשל [math]\displaystyle{ [1]_R=[2]_R=\{1,2,3,\ldots\} }[/math].
• אם [math]\displaystyle{ a<0 }[/math] אז [math]\displaystyle{ aRx }[/math] אם ורק אם [math]\displaystyle{ x<0 }[/math]. לכן למשל [math]\displaystyle{ [-1]_R=[-67]_R=\{-1,-2,-3,\ldots\} }[/math].

לכן קבוצת המנה היא

[math]\displaystyle{ \mathbb{Z}/R=\{[a]_R\mid a\in\mathbb{Z}\}=\{[0]_R,[1]_R,[-1]_R\} }[/math]

[math]\displaystyle{ =\big\{\{0\},\{1,2,3,\ldots\},\{-1,-2,-3,\ldots\}\big\} }[/math]

שימו לב: אף על פי שיש אינסוף מספרים שלמים, בקבוצת המנה יש רק שלושה איברים, כי לאיברים שונים יכולה להיות אותה מחלקת שקילות. קבוצת המנה היא בדיוק החלוקה של השלמים לחיוביים, לשליליים ולאפס לבדו.

▶ הפתרון בהרצאה מ־15.7.26, החל מהדקה 3:15:25

• תהי קבוצה A. קבוצת תתי קבוצות [math]\displaystyle{ U\subseteq P(A) }[/math] נקראת חלוקה של A אם:
  • [math]\displaystyle{ \cup_{X\in U}X=A }[/math]
  • [math]\displaystyle{ \emptyset\notin U }[/math]
  • לכל [math]\displaystyle{ X_1,X_2\in U }[/math] אם [math]\displaystyle{ X_1\cap X_2\neq \emptyset }[/math] אזי [math]\displaystyle{ X_1=X_2 }[/math]

דוגמה: האם הקבוצות הבאות הן חלוקות של [math]\displaystyle{ \mathbb{Z} }[/math]?

[math]\displaystyle{ U_1=\big\{\{0\},\{a\in\mathbb{Z}\mid a>0\},\{a\in\mathbb{Z}\mid a<0\}\big\} }[/math]

[math]\displaystyle{ U_2=\big\{\{0\},\{a\in\mathbb{Z}\mid a>0\},\{a\in\mathbb{Z}\mid a<0\},\{a\in\mathbb{Z}\mid a^2=2\}\big\} }[/math]

[math]\displaystyle{ U_1 }[/math] היא חלוקה של [math]\displaystyle{ \mathbb{Z} }[/math]:

• כל מספר שלם הוא אפס, חיובי או שלילי, ולכן איחוד שלוש הקבוצות הוא [math]\displaystyle{ \mathbb{Z} }[/math].
• אף אחת משלוש הקבוצות אינה ריקה.
• כל שתי קבוצות שונות מבין השלוש זרות, ולכן אם שתי קבוצות ב[math]\displaystyle{ U_1 }[/math] נחתכות - זו אותה הקבוצה.

[math]\displaystyle{ U_2 }[/math] אינה חלוקה של [math]\displaystyle{ \mathbb{Z} }[/math]: אין מספר שלם שריבועו 2, ולכן [math]\displaystyle{ \{a\in\mathbb{Z}\mid a^2=2\}=\emptyset }[/math], כלומר [math]\displaystyle{ \emptyset\in U_2 }[/math].

▶ הפתרון בהרצאה מ־20.7.26, החל מהדקה 26:52

• היחס המושרה מחלוקה:
• תהי קבוצה A ותהי חלוקה שלה U. נגדיר יחס R על A על ידי:
  • [math]\displaystyle{ aRb }[/math] אם ורק אם קיימת [math]\displaystyle{ X\in U }[/math] כך ש[math]\displaystyle{ a,b\in X }[/math]

דוגמה: תהי [math]\displaystyle{ A=\{1,2,3,4\} }[/math]. מהו היחס המושרה מהחלוקה [math]\displaystyle{ U_1=\{\{1\},\{2\},\{3\},\{4\}\} }[/math]? ומהו היחס המושרה מהחלוקה [math]\displaystyle{ U_2=\{A\} }[/math]?

• בחלוקה [math]\displaystyle{ U_1 }[/math] כל קבוצה היא יחידון, ולכן קיימת [math]\displaystyle{ X\in U_1 }[/math] כך ש[math]\displaystyle{ a,b\in X }[/math] אם ורק אם [math]\displaystyle{ a=b }[/math]. לכן היחס המושרה הוא יחס הזהות [math]\displaystyle{ I_A=\{(a,a)\mid a\in A\} }[/math]: כל איבר מתייחס לעצמו, ורק לעצמו.
• בחלוקה [math]\displaystyle{ U_2 }[/math] יש קבוצה אחת בלבד, A עצמה, והיא מכילה כל שני איברים. לכן היחס המושרה הוא היחס המלא [math]\displaystyle{ A\times A }[/math]: כל איבר מתייחס לכל איבר.

אלה שני המקרים הקיצוניים: ביחס הזהות כל מחלקת שקילות היא יחידון, וביחס המלא יש מחלקה אחת - A כולה.

▶ הפתרון בהרצאה מ־20.7.26, החל מהדקה 19:46

• היחס המושרה מחלוקה הוא יחס שקילות.
• טענת עזר: יהי R יחס שקילות על A ויהי [math]\displaystyle{ a\in A }[/math]. אזי לכל [math]\displaystyle{ b\in[a]_R }[/math] מתקיים [math]\displaystyle{ [b]_R=[a]_R }[/math].

הוכחה. יהי [math]\displaystyle{ b\in[a]_R }[/math], כלומר [math]\displaystyle{ aRb }[/math]. נוכיח הכלה דו כיוונית.

• [math]\displaystyle{ [a]_R\subseteq[b]_R }[/math]: יהי [math]\displaystyle{ c\in[a]_R }[/math], כלומר [math]\displaystyle{ aRc }[/math]. צריך להוכיח [math]\displaystyle{ c\in[b]_R }[/math], כלומר [math]\displaystyle{ bRc }[/math]. מהסימטריות ומ־[math]\displaystyle{ aRb }[/math] נובע [math]\displaystyle{ bRa }[/math]. כיוון ש[math]\displaystyle{ bRa }[/math] ו[math]\displaystyle{ aRc }[/math], מהטרנזיטיביות נובע [math]\displaystyle{ bRc }[/math].
• [math]\displaystyle{ [b]_R\subseteq[a]_R }[/math]: יהי [math]\displaystyle{ c\in[b]_R }[/math], כלומר [math]\displaystyle{ bRc }[/math]. צריך להוכיח [math]\displaystyle{ aRc }[/math]. כיוון ש[math]\displaystyle{ aRb }[/math] ו[math]\displaystyle{ bRc }[/math], מהטרנזיטיביות נובע [math]\displaystyle{ aRc }[/math].

▶ ההוכחה בהרצאה מ־20.7.26, החל מהדקה 33:41

• קבוצת המנה היא חלוקה של A.

הוכחה. יהי R יחס שקילות על A. קבוצת המנה היא קבוצת מחלקות השקילות, וכל מחלקת שקילות מוכלת בA לפי הגדרתה, ולכן [math]\displaystyle{ A/R\subseteq P(A) }[/math]. נוכיח את שלושת התנאים בהגדרת החלוקה.

1. איחוד כל מחלקות השקילות הוא A. נוכיח הכלה דו כיוונית.

• יהי [math]\displaystyle{ x\in\bigcup_{a\in A}[a]_R }[/math]. אזי קיים [math]\displaystyle{ a\in A }[/math] כך ש[math]\displaystyle{ x\in[a]_R }[/math], ולכן [math]\displaystyle{ x\in A }[/math].
• יהי [math]\displaystyle{ x\in A }[/math]. בזכות הרפלקסיביות [math]\displaystyle{ xRx }[/math], ולכן [math]\displaystyle{ x\in[x]_R }[/math], ולכן [math]\displaystyle{ x\in\bigcup_{a\in A}[a]_R }[/math].

2. אין מחלקת שקילות ריקה. תהי מחלקת שקילות [math]\displaystyle{ [a]_R\in A/R }[/math]. לפי הרפלקסיביות [math]\displaystyle{ aRa }[/math], כלומר [math]\displaystyle{ a\in[a]_R }[/math], ולכן [math]\displaystyle{ [a]_R\neq\emptyset }[/math].

3. מחלקות שקילות שנחתכות הן שוות. יהיו [math]\displaystyle{ a,b\in A }[/math] כך ש[math]\displaystyle{ [a]_R\cap[b]_R\neq\emptyset }[/math]. צריך להוכיח [math]\displaystyle{ [a]_R=[b]_R }[/math]. קיים [math]\displaystyle{ c\in[a]_R\cap[b]_R }[/math]. בפרט [math]\displaystyle{ c\in[a]_R }[/math], ולכן לפי טענת העזר [math]\displaystyle{ [c]_R=[a]_R }[/math]. אבל גם [math]\displaystyle{ c\in[b]_R }[/math], ולכן [math]\displaystyle{ [c]_R=[b]_R }[/math]. לכן [math]\displaystyle{ [a]_R=[c]_R=[b]_R }[/math].

▶ ההוכחה בהרצאה מ־20.7.26, החל מהדקה 45:21

• היחס המושרה מקבוצת המנה, הוא יחס השקילות המקורי; קבוצת המנה של יחס שקילות מושרה היא החלוקה המקורית.

תרגול

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

יחסי סדר

• יחס R על קבוצה A נקרא יחס סדר חלקי אם הוא רפלקסיבי, אנטי-סימטרי וטרנזיטיבי

דוגמה: הוכיחו כי היחס [math]\displaystyle{ \leq }[/math] על הטבעיים (כאשר [math]\displaystyle{ 0\in\mathbb{N} }[/math]), המוגדר ע"י [math]\displaystyle{ a\leq b\iff\exists c\in\mathbb{N}:b=a+c }[/math], הוא יחס סדר חלקי.

רפלקסיביות. לכל [math]\displaystyle{ a\in\mathbb{N} }[/math] מתקיים [math]\displaystyle{ a=a+0 }[/math], ולכן [math]\displaystyle{ a\leq a }[/math].

אנטי-סימטריות. יהיו [math]\displaystyle{ a,b\in\mathbb{N} }[/math] כך ש[math]\displaystyle{ a\leq b }[/math] וגם [math]\displaystyle{ b\leq a }[/math]. אזי קיימים [math]\displaystyle{ c_1,c_2\in\mathbb{N} }[/math] כך ש

[math]\displaystyle{ a=b+c_1,\quad b=a+c_2 }[/math]

נחבר את המשוואות ונקבל [math]\displaystyle{ a+b=a+b+c_1+c_2 }[/math], ולכן [math]\displaystyle{ c_1+c_2=0 }[/math]. כיוון ש־[math]\displaystyle{ c_1,c_2 }[/math] טבעיים, [math]\displaystyle{ c_1=c_2=0 }[/math], ולכן [math]\displaystyle{ a=b }[/math].

טרנזיטיביות. יהיו [math]\displaystyle{ a,b,c\in\mathbb{N} }[/math] כך ש[math]\displaystyle{ a\leq b }[/math] ו[math]\displaystyle{ b\leq c }[/math]. אזי קיימים [math]\displaystyle{ d_1,d_2\in\mathbb{N} }[/math] כך ש [math]\displaystyle{ b=a+d_1 }[/math] ו[math]\displaystyle{ c=b+d_2 }[/math]. לכן [math]\displaystyle{ c=a+(d_1+d_2) }[/math], ו־[math]\displaystyle{ d_1+d_2\in\mathbb{N} }[/math], ולכן [math]\displaystyle{ a\leq c }[/math].

▶ הפתרון בהרצאה מ־20.7.26, החל מהדקה 2:10:25

• היחס מחלק את על הטבעיים, המוגדר ע"י [math]\displaystyle{ a|b\iff\exists c\in\mathbb{N}:b=ac }[/math], הוא יחס סדר חלקי.

הוכחה. רפלקסיביות: יהי [math]\displaystyle{ a\in\mathbb{N} }[/math]. נבחר [math]\displaystyle{ c=1 }[/math], ואכן [math]\displaystyle{ a=a\cdot 1 }[/math], ולכן [math]\displaystyle{ a|a }[/math].

טרנזיטיביות: יהיו [math]\displaystyle{ a,b,c\in\mathbb{N} }[/math] כך ש[math]\displaystyle{ a|b }[/math] ו[math]\displaystyle{ b|c }[/math]. אזי קיימים [math]\displaystyle{ d_1,d_2\in\mathbb{N} }[/math] כך ש [math]\displaystyle{ b=ad_1 }[/math] ו[math]\displaystyle{ c=bd_2 }[/math]. לכן [math]\displaystyle{ c=a(d_1d_2) }[/math], ולכן [math]\displaystyle{ a|c }[/math].

אנטי-סימטריות: יהיו [math]\displaystyle{ a,b\in\mathbb{N} }[/math] כך ש[math]\displaystyle{ a|b }[/math] ו[math]\displaystyle{ b|a }[/math]. אזי קיימים [math]\displaystyle{ c_1,c_2\in\mathbb{N} }[/math] כך ש

[math]\displaystyle{ b=ac_1,\quad a=bc_2 }[/math]

לכן [math]\displaystyle{ a=ac_1c_2 }[/math], כלומר [math]\displaystyle{ a(1-c_1c_2)=0 }[/math].

• אם [math]\displaystyle{ a=0 }[/math] אז [math]\displaystyle{ b=ac_1=0 }[/math], ואכן [math]\displaystyle{ a=b }[/math].
• אם [math]\displaystyle{ a\neq 0 }[/math] אז [math]\displaystyle{ c_1c_2=1 }[/math]. כיוון ש־[math]\displaystyle{ c_1,c_2 }[/math] טבעיים, בהכרח [math]\displaystyle{ c_1=c_2=1 }[/math], ולכן [math]\displaystyle{ b=a }[/math].

▶ ההוכחה בהרצאה מ־20.7.26, החל מהדקה 2:23:56

דוגמה: האם היחס R על השלמים, המוגדר ע"י [math]\displaystyle{ aRb\iff\exists c\in\mathbb{Z}:b=ac }[/math], הוא יחס סדר חלקי?

לא. הרפלקסיביות והטרנזיטיביות מוכחות בדיוק כמו ביחס "מחלק את" על הטבעיים. אבל באנטי-סימטריות, מ־[math]\displaystyle{ b=ac_1 }[/math] ו־[math]\displaystyle{ a=bc_2 }[/math] עם [math]\displaystyle{ a\neq 0 }[/math] נקבל רק [math]\displaystyle{ c_1c_2=1 }[/math], ובשלמים ייתכן גם [math]\displaystyle{ c_1=c_2=-1 }[/math]. ואכן זו דוגמה נגדית:

[math]\displaystyle{ -1=1\cdot(-1),\quad 1=(-1)\cdot(-1) }[/math]

כלומר [math]\displaystyle{ 1R(-1) }[/math] וגם [math]\displaystyle{ (-1)R1 }[/math], אבל [math]\displaystyle{ 1\neq -1 }[/math]. לכן R אינו אנטי-סימטרי, ולכן אינו יחס סדר חלקי.

▶ הפתרון בהרצאה מ־20.7.26, החל מהדקה 2:20:27

• תהי A קבוצה של קבוצות. יחס ההכלה על A, המוגדר ע"י [math]\displaystyle{ X_1RX_2\iff X_1\subseteq X_2 }[/math], הוא יחס סדר חלקי.

הוכחה. רפלקסיביות: לכל [math]\displaystyle{ X\in A }[/math] מתקיים [math]\displaystyle{ X\subseteq X }[/math].

אנטי-סימטריות: תהיינה [math]\displaystyle{ X_1,X_2\in A }[/math] כך ש[math]\displaystyle{ X_1\subseteq X_2 }[/math] וגם [math]\displaystyle{ X_2\subseteq X_1 }[/math]. לפי הגדרת שוויון קבוצות (הכלה דו כיוונית) [math]\displaystyle{ X_1=X_2 }[/math].

טרנזיטיביות: תהיינה [math]\displaystyle{ X_1,X_2,X_3\in A }[/math] כך ש[math]\displaystyle{ X_1\subseteq X_2 }[/math] וגם [math]\displaystyle{ X_2\subseteq X_3 }[/math]. צריך להוכיח [math]\displaystyle{ X_1\subseteq X_3 }[/math]. יהי [math]\displaystyle{ a\in X_1 }[/math]. כיוון ש[math]\displaystyle{ X_1\subseteq X_2 }[/math] נובע [math]\displaystyle{ a\in X_2 }[/math], וכיוון ש[math]\displaystyle{ X_2\subseteq X_3 }[/math] נובע [math]\displaystyle{ a\in X_3 }[/math].

▶ ההוכחה בהרצאה מ־20.7.26, החל מהדקה 2:40:16

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

• יהי R יחס סדר חלקי על קבוצה X, ותהי [math]\displaystyle{ A\subseteq X }[/math] תת קבוצה.
  • איבר [math]\displaystyle{ M\in A }[/math] נקרא מקסימלי בA אם לכל [math]\displaystyle{ a\in A }[/math] המקיים [math]\displaystyle{ MRa }[/math] מתקיים כי [math]\displaystyle{ a=M }[/math] (אין גדולים ממנו)
  • איבר [math]\displaystyle{ m\in A }[/math] נקרא מינימלי בA אם לכל [math]\displaystyle{ a\in A }[/math] המקיים [math]\displaystyle{ aRm }[/math] מתקיים כי [math]\displaystyle{ a=m }[/math] (אין קטנים ממנו)
  • איבר [math]\displaystyle{ M\in A }[/math] נקרא הגדול ביותר (מקסימום) בA אם לכל [math]\displaystyle{ a\in A }[/math] מתקיים [math]\displaystyle{ aRM }[/math] (הוא גדול מכולם)
  • איבר [math]\displaystyle{ m\in A }[/math] נקרא הקטן ביותר (מינימום) בA אם לכל [math]\displaystyle{ a\in A }[/math] מתקיים [math]\displaystyle{ mRa }[/math] (הוא קטן מכולם)
  • איבר [math]\displaystyle{ M\in X }[/math] נקרא חסם מלעיל של A אם לכל [math]\displaystyle{ a\in A }[/math] מתקיים [math]\displaystyle{ aRM }[/math] (הוא גדול מכל איברי הקבוצה, אבל לאו דווקא נמצא בקבוצה)
  • איבר [math]\displaystyle{ m\in X }[/math] נקרא חסם מלרע של A אם לכל [math]\displaystyle{ a\in A }[/math] מתקיים [math]\displaystyle{ mRa }[/math] (הוא קטן מכל איברי הקבוצה, אבל לאו דווקא נמצא בקבוצה)
  • אם בקבוצת חסמי המלעיל של A יש איבר קטן ביותר הוא נקרא חסם עליון (supremum) של A.
  • אם בקבוצת חסמי המלרע של A יש איבר גדול ביותר הוא נקרא חסם תחתון (infimum) של A.

דוגמה: נביט בקבוצה [math]\displaystyle{ \{2,3,5,30\} }[/math] עם היחס "מחלק את". האם יש בה איבר גדול ביותר? קטן ביותר? אילו איברים מקסימליים ומינימליים יש בה?

• גדול ביותר: 30, כי כל איברי הקבוצה מחלקים את 30.
• קטן ביותר: אין. איבר קטן ביותר צריך לחלק את כל האחרים, אבל 2 לא מחלק את 3, 3 ו־5 לא מחלקים את 2, ו־30 לא מחלק את 2.
• מקסימלי: 30 (והוא המקסימלי היחיד, ראו הטענה בהמשך). 2, 3 ו־5 אינם מקסימליים, כי כל אחד מהם מחלק את 30.
• מינימליים: 2, 3 ו־5 - אף איבר אחר בקבוצה אינו מחלק אף אחד מהם. 30 אינו מינימלי, כי [math]\displaystyle{ 2|30 }[/math].

▶ הפתרון בהרצאה מ־22.7.26, החל מהדקה 33:01

דוגמה: נביט בקטע [math]\displaystyle{ (0,1)=\{x\in\mathbb{R}\mid 0<x<1\} }[/math] עם יחס הסדר [math]\displaystyle{ \leq }[/math] הרגיל. האם יש בו איבר גדול ביותר, קטן ביותר, מקסימלי או מינימלי?

אין אף אחד מהם.

לכל [math]\displaystyle{ x\in(0,1) }[/math] גם אמצע הקטע בינו לבין 1, [math]\displaystyle{ \tfrac{x+1}{2} }[/math], נמצא בקטע וגדול ממש מ־x. לכן אף איבר אינו מקסימלי, ובפרט אף איבר אינו גדול ביותר.

באופן דומה, לכל [math]\displaystyle{ x\in(0,1) }[/math] גם [math]\displaystyle{ \tfrac{x}{2}\in(0,1) }[/math] וקטן ממש מ־x, ולכן אין איבר מינימלי ואין איבר קטן ביותר.

▶ הפתרון בהרצאה מ־22.7.26, החל מהדקה 44:25

• איבר גדול ביותר הוא יחיד.

הוכחה. נניח ש־[math]\displaystyle{ M_1,M_2\in A }[/math] שניהם איברים גדולים ביותר בA, כלומר כל אחד מהם גדול מכל איברי A. בפרט

[math]\displaystyle{ M_1RM_2\land M_2RM_1 }[/math]

ולפי האנטי-סימטריות [math]\displaystyle{ M_1=M_2 }[/math].

• אם חסם מלעיל שייך לקבוצה, אז הוא הגדול ביותר.

הוכחה. יהי [math]\displaystyle{ M }[/math] חסם מלעיל של A כך ש[math]\displaystyle{ M\in A }[/math]. היותו חסם מלעיל אומרת שלכל [math]\displaystyle{ a\in A }[/math] מתקיים [math]\displaystyle{ aRM }[/math]. יחד עם [math]\displaystyle{ M\in A }[/math], זו בדיוק ההגדרה של איבר גדול ביותר בA. (ההבדל היחיד בין שתי ההגדרות הוא שחסם מלעיל אינו חייב להיות בקבוצה.)

▶ ההוכחה בהרצאה מ־22.7.26, החל מהדקה 2:04:28

• האיבר הגדול ביותר בקבוצה הוא איבר מקסימלי, ואין איברים מקסימליים אחרים.

הוכחה. יהי [math]\displaystyle{ M\in A }[/math] האיבר הגדול ביותר בA.

M מקסימלי: יהי [math]\displaystyle{ a\in A }[/math] כך ש[math]\displaystyle{ MRa }[/math]. צריך להוכיח [math]\displaystyle{ a=M }[/math]. כיוון ש־M גדול ביותר, מתקיים [math]\displaystyle{ aRM }[/math]. לפי האנטי-סימטריות [math]\displaystyle{ a=M }[/math].

M הוא המקסימלי היחיד: יהי [math]\displaystyle{ K\in A }[/math] איבר מקסימלי. כיוון ש־M גדול ביותר, [math]\displaystyle{ KRM }[/math]. כיוון ש־K מקסימלי ו[math]\displaystyle{ KRM }[/math], נובע [math]\displaystyle{ M=K }[/math].

▶ ההוכחה בהרצאה מ־22.7.26, החל מהדקה 56:03

• אם יש בA איבר גדול ביותר, הוא גם החסם העליון של A.

הוכחה. נסמן את יחס הסדר ב־[math]\displaystyle{ \leq }[/math], ויהי [math]\displaystyle{ M\in A }[/math] האיבר הגדול ביותר בA. צריך להוכיח ש־M הוא האיבר הקטן ביותר בקבוצת חסמי המלעיל של A, כלומר:

1. M הוא חסם מלעיל של A.
2. אם K חסם מלעיל של A, אזי [math]\displaystyle{ M\leq K }[/math].

כיוון ש־M גדול ביותר, לכל [math]\displaystyle{ a\in A }[/math] מתקיים [math]\displaystyle{ a\leq M }[/math], ולכן M חסם מלעיל של A.

יהי K חסם מלעיל של A. כיוון ש[math]\displaystyle{ M\in A }[/math], וכיוון ש־K גדול מכל איברי A, נובע [math]\displaystyle{ M\leq K }[/math].

▶ ההוכחה בהרצאה מ־22.7.26, החל מהדקה 2:26:16

• האם תתכן קבוצה עם איבר מקסימלי יחיד שאינו האיבר הגדול ביותר בקבוצה?

כן. נביט בקבוצה [math]\displaystyle{ \mathbb{N}\times\mathbb{N} }[/math] עם היחס

[math]\displaystyle{ (a,b)R(c,d)\iff a=c\land b\leq d }[/math]

(זהו יחס סדר חלקי: רפלקסיביות ברורה; אם [math]\displaystyle{ (a,b)R(c,d) }[/math] ו[math]\displaystyle{ (c,d)R(a,b) }[/math] אז [math]\displaystyle{ a=c }[/math] ו[math]\displaystyle{ b\leq d\leq b }[/math], ולכן [math]\displaystyle{ (a,b)=(c,d) }[/math]; וטרנזיטיביות נובעת מהטרנזיטיביות של שוויון ושל [math]\displaystyle{ \leq }[/math].) נביט בתת הקבוצה

[math]\displaystyle{ A=\{(1,0)\}\cup\{(0,n)\mid n\in\mathbb{N}\} }[/math]

[math]\displaystyle{ (1,0) }[/math] מקסימלי: יהי [math]\displaystyle{ (a,b)\in A }[/math] כך ש[math]\displaystyle{ (1,0)R(a,b) }[/math]. לפי הגדרת היחס [math]\displaystyle{ a=1 }[/math] (ו[math]\displaystyle{ 0\leq b }[/math]). אבל [math]\displaystyle{ (1,0) }[/math] הוא הזוג היחיד בA שהאיבר השמאלי שלו הוא 1, ולכן [math]\displaystyle{ (a,b)=(1,0) }[/math].

[math]\displaystyle{ (1,0) }[/math] הוא המקסימלי היחיד: כל איבר אחר בA הוא מהצורה [math]\displaystyle{ (0,b) }[/math], ומתקיים [math]\displaystyle{ (0,b)R(0,b+1) }[/math] כאשר [math]\displaystyle{ (0,b+1)\in A }[/math] ו[math]\displaystyle{ (0,b+1)\neq(0,b) }[/math]. לכן [math]\displaystyle{ (0,b) }[/math] אינו מקסימלי.

[math]\displaystyle{ (1,0) }[/math] אינו הגדול ביותר: [math]\displaystyle{ \neg\big((0,0)R(1,0)\big) }[/math], כי [math]\displaystyle{ 0\neq 1 }[/math].

הערה: בקבוצה סופית זה לא ייתכן - אם בקבוצה סופית יש איבר מקסימלי יחיד, הוא האיבר הגדול ביותר (תרגיל; הוכחה באינדוקציה על מספר האיברים). לכן הדוגמה הנגדית חייבת להיות אינסופית.

▶ הפתרון בהרצאה מ־22.7.26, החל מהדקה 1:15:01

• ביחס ההכלה על קבוצת חזקה, האיחוד הכללי של קבוצת קבוצות הוא החסם העליון שלה, והחיתוך הכללי (של קבוצת קבוצות לא ריקה) הוא החסם התחתון.

הוכחה. תהי קבוצה A ונביט ב־[math]\displaystyle{ P(A) }[/math] הסדורה ביחס ההכלה. תהי [math]\displaystyle{ D\subseteq P(A) }[/math].

החסם העליון. נסמן [math]\displaystyle{ M=\bigcup_{X\in D}X }[/math]. כל [math]\displaystyle{ X\in D }[/math] מוכלת בA, ולכן [math]\displaystyle{ M\subseteq A }[/math], כלומר [math]\displaystyle{ M\in P(A) }[/math]. צריך להוכיח:

1. M חסם מלעיל של D.
2. לכל K חסם מלעיל של D מתקיים [math]\displaystyle{ M\subseteq K }[/math].

ראשית, תהי [math]\displaystyle{ X\in D }[/math], צריך להוכיח [math]\displaystyle{ X\subseteq M }[/math]. יהי [math]\displaystyle{ a\in X }[/math]; אז [math]\displaystyle{ a\in M }[/math] ישירות מהגדרת האיחוד.

כעת יהי K חסם מלעיל של D, צריך להוכיח [math]\displaystyle{ M\subseteq K }[/math]. יהי [math]\displaystyle{ x\in M }[/math]. אז קיימת [math]\displaystyle{ X\in D }[/math] כך ש[math]\displaystyle{ x\in X }[/math]. כיוון ש־K חסם מלעיל של D ו[math]\displaystyle{ X\in D }[/math], מתקיים [math]\displaystyle{ X\subseteq K }[/math], ולכן [math]\displaystyle{ x\in K }[/math].

החסם התחתון (בתנאי ש־D אינה ריקה, כדי שהחיתוך יהיה מוגדר). נסמן [math]\displaystyle{ N=\bigcap_{X\in D}X }[/math]. כיוון ש־D אינה ריקה יש [math]\displaystyle{ X_0\in D }[/math], ו[math]\displaystyle{ N\subseteq X_0\subseteq A }[/math], ולכן [math]\displaystyle{ N\in P(A) }[/math]. באופן דומה:

• N חסם מלרע של D: לכל [math]\displaystyle{ X\in D }[/math] ולכל [math]\displaystyle{ x\in N }[/math] מתקיים [math]\displaystyle{ x\in X }[/math] לפי הגדרת החיתוך, ולכן [math]\displaystyle{ N\subseteq X }[/math].
• יהי K חסם מלרע של D, כלומר [math]\displaystyle{ K\subseteq X }[/math] לכל [math]\displaystyle{ X\in D }[/math]. אז כל [math]\displaystyle{ x\in K }[/math] שייך לכל [math]\displaystyle{ X\in D }[/math], ולכן [math]\displaystyle{ x\in N }[/math]. לכן [math]\displaystyle{ K\subseteq N }[/math].

▶ ההוכחה בהרצאה מ־22.7.26, החל מהדקה 2:33:31

• ביחס 'מחלק את' על הטבעיים, המחלק המשותף המקסימלי הוא החסם התחתון, והכפולה המשותפת המינימלית היא החסם העליון.

דוגמה: ביחס "מחלק את" על הטבעיים, מצאו את החסם העליון ואת החסם התחתון של הקבוצה [math]\displaystyle{ \{6,15\} }[/math].

[math]\displaystyle{ \sup\{6,15\}=30 }[/math]. חסמי המלעיל של הקבוצה הם המספרים שמתחלקים גם ב־6 וגם ב־15 (למשל [math]\displaystyle{ 6\cdot 15=90 }[/math]). צריך להראות שני דברים:

1. 30 הוא חסם מלעיל: אכן 6 ו־15 מחלקים את 30.
2. 30 מחלק כל חסם מלעיל: יהי m חסם מלעיל. אז m מתחלק ב־6 וב־15, ולכן בפרט ב־2, ב־3 וב־5. כיוון שאלה מספרים ראשוניים שונים, m מתחלק ב־[math]\displaystyle{ 2\cdot 3\cdot 5=30 }[/math].

[math]\displaystyle{ \inf\{6,15\}=3 }[/math]. חסמי המלרע הם המחלקים המשותפים של 6 ו־15, כלומר 1 ו־3. מביניהם 3 הוא הגדול ביותר ביחס "מחלק את", כי [math]\displaystyle{ 1|3 }[/math].

▶ הפתרון בהרצאה מ־22.7.26, החל מהדקה 2:16:53

שרשראות

• יחס סדר חלקי R על A נקרא מלא (או לינארי, או קווי) אם:
  • [math]\displaystyle{ \forall a,b\in A:aRb\or bRa }[/math]

• יהי R יחס סדר חלקי על A, ותהי [math]\displaystyle{ S\subseteq A }[/math].
• אזי [math]\displaystyle{ S }[/math] נקראת שרשרת אם היחס מלא עליה, כלומר [math]\displaystyle{ \forall a,b\in S:aRb\or bRa }[/math]

דוגמה:

1. האם היחס "מחלק את" על הטבעיים הוא יחס סדר מלא?
2. האם [math]\displaystyle{ \{2,4,6,8,10\} }[/math] היא שרשרת ביחס "מחלק את"?
3. האם [math]\displaystyle{ \{2^n\mid n\in\mathbb{N}\} }[/math] (ובפרט [math]\displaystyle{ \{2,4,8,16,32\} }[/math]) היא שרשרת ביחס "מחלק את"?
4. האם יחס ההכלה על [math]\displaystyle{ P(A) }[/math] הוא יחס סדר מלא?

1. לא: 2 לא מחלק את 3, וגם 3 לא מחלק את 2.
2. לא: 4 לא מחלק את 6, וגם 6 לא מחלק את 4.
3. כן. יהיו [math]\displaystyle{ 2^k,2^m }[/math] בקבוצה, צריך להוכיח [math]\displaystyle{ 2^k|2^m }[/math] או [math]\displaystyle{ 2^m|2^k }[/math]. אם [math]\displaystyle{ m\geq k }[/math] אז [math]\displaystyle{ m=k+d }[/math] עבור [math]\displaystyle{ d\in\mathbb{N} }[/math], ולכן [math]\displaystyle{ 2^m=2^k\cdot 2^d }[/math], כלומר [math]\displaystyle{ 2^k|2^m }[/math]. אם [math]\displaystyle{ m<k }[/math], באופן דומה [math]\displaystyle{ 2^m|2^k }[/math]. כל תת קבוצה של שרשרת היא שרשרת, ולכן גם [math]\displaystyle{ \{2,4,8,16,32\} }[/math] שרשרת.
4. לא (אלא אם בA יש לכל היותר איבר אחד). למשל ב־[math]\displaystyle{ P(\{1,2\})=\{\emptyset,\{1\},\{2\},\{1,2\}\} }[/math] מתקיים [math]\displaystyle{ \{1\}\not\subseteq\{2\} }[/math] וגם [math]\displaystyle{ \{2\}\not\subseteq\{1\} }[/math].

▶ הפתרון בהרצאה מ־20.7.26, החל מהדקה 2:52:11

תרגול

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

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

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

• יחס f מA לB נקרא פונקציה אם הוא ח"ע ושלם, ומסמנים במקרה זה [math]\displaystyle{ f:A\to B }[/math], וכן [math]\displaystyle{ f(a)=b\iff (a,b)\in f }[/math].
• A נקרא תחום הפונקציה (או תחום הגדרה), B נקרא הטווח של הפונקציה.

• פורמלית, פונקציה היא השלשה [math]\displaystyle{ (f,A,B) }[/math] - היחס יחד עם התחום והטווח. אותו יחס יכול להיות פונקציה עם טווחים שונים, ולכן כדי לקבוע למשל אם פונקציה היא על, חייבים לדעת מהו הטווח שלה.
• הסימון [math]\displaystyle{ f(a)=b }[/math] מותר רק כאשר f היא פונקציה: בזכות הח"ע והשלמות, לכל [math]\displaystyle{ a\in A }[/math] קיים b יחיד כך ש[math]\displaystyle{ (a,b)\in f }[/math].

• שימו לב, הסרטון ישן, ושם פונקציה הוגדרה כיחס ח"ע בלבד, בניגוד להגדרה העדכנית שלנו בקורס.

דוגמה: נביט ביחס [math]\displaystyle{ R=\{((a,b),c)\in(\mathbb{N}\times\mathbb{N})\times\mathbb{N}|a+b=c\} }[/math]. האם R היא פונקציה [math]\displaystyle{ R:\mathbb{N}\times\mathbb{N}\to\mathbb{N} }[/math]?

כן. צריך לבדוק שלושה דברים:

• [math]\displaystyle{ R\subseteq(\mathbb{N}\times\mathbb{N})\times\mathbb{N} }[/math] - ממש לפי ההגדרה של R.
• R ח"ע: יהי [math]\displaystyle{ (a,b) }[/math] איבר מהתחום ויהיו [math]\displaystyle{ c_1,c_2 }[/math] איברים מהטווח כך ש[math]\displaystyle{ ((a,b),c_1),((a,b),c_2)\in R }[/math]. צ"ל [math]\displaystyle{ c_1=c_2 }[/math]. אכן, נתון כי [math]\displaystyle{ a+b=c_1 }[/math] וכן [math]\displaystyle{ a+b=c_2 }[/math], ולכן [math]\displaystyle{ c_1=c_2 }[/math].
• R שלם: יהי [math]\displaystyle{ (a,b) }[/math] איבר מהתחום. צ"ל שקיים איבר c מהטווח כך ש[math]\displaystyle{ ((a,b),c)\in R }[/math]. אכן, נבחר [math]\displaystyle{ c=a+b\in\mathbb{N} }[/math].

לכן R היא פונקציה - זו בעצם פונקציית החיבור [math]\displaystyle{ R(a,b)=a+b }[/math]. ▶ הפתרון בהרצאה מ־27.7.26, החל מהדקה 1:01:39

דוגמה: האם היחס [math]\displaystyle{ R=\{((a,b),c)\in(\mathbb{N}\times\mathbb{N})\times\mathbb{N}|a^2+b^2=c^2\} }[/math] הוא פונקציה [math]\displaystyle{ R:\mathbb{N}\times\mathbb{N}\to\mathbb{N} }[/math]?

לא, כי R אינו שלם: [math]\displaystyle{ 1^2+2^2=5 }[/math] אינו ריבוע של מספר טבעי, ולכן

[math]\displaystyle{ \forall c\in\mathbb{N}:((1,2),c)\notin R }[/math]

כלומר לאיבר [math]\displaystyle{ (1,2) }[/math] שבתחום אין איבר מתאים בטווח. (היחס כן מוכל ב[math]\displaystyle{ (\mathbb{N}\times\mathbb{N})\times\mathbb{N} }[/math] וכן ח"ע, כי מספר טבעי נקבע ביחידות על ידי הריבוע שלו.) ▶ הפתרון בהרצאה מ־27.7.26, החל מהדקה 1:15:03

דוגמה: האם קיימת פונקציה [math]\displaystyle{ f:\{1\}\to\emptyset }[/math]? האם קיימת פונקציה [math]\displaystyle{ f:\emptyset\to\{1\} }[/math]? והאם קיימת פונקציה [math]\displaystyle{ f:\emptyset\to\emptyset }[/math]?

• [math]\displaystyle{ f:\{1\}\to\emptyset }[/math] - לא קיימת. פונקציה כזו צריכה להיות יחס, כלומר תת קבוצה של [math]\displaystyle{ \{1\}\times\emptyset=\emptyset }[/math]. לכן הפונקציה הפוטנציאלית היחידה היא היחס הריק. הוא ח"ע (באופן ריק), אבל אינו שלם: לאיבר 1 שבתחום לא קיים איבר מתאים בטווח, כי הטווח ריק.
• [math]\displaystyle{ f:\emptyset\to\{1\} }[/math] - קיימת. שוב הפוטנציאל היחיד הוא היחס הריק, אבל הפעם הוא גם ח"ע וגם שלם: לכל איבר בתחום קיים איבר בטווח - באופן ריק, כי אין איברים בתחום.
• [math]\displaystyle{ f:\emptyset\to\emptyset }[/math] - קיימת. היחס הריק ח"ע באופן ריק וגם שלם באופן ריק.

▶ הפתרון בהרצאה מ־27.7.26, החל מהדקה 1:17:57

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

📄 דף נושא: פונקציה חד-חד-ערכית ועל - הגדרות, דוגמאות פתורות, שאלות ממבחנים וסרטונים

• תהי [math]\displaystyle{ f:A\to B }[/math] פונקציה. אזי:
  • f חח"ע אם לכל [math]\displaystyle{ x_1,x_2\in A }[/math] המקיימים [math]\displaystyle{ f(x_1)=f(x_2) }[/math] מתקיים כי [math]\displaystyle{ x_1=x_2 }[/math]
  • f על אם לכל [math]\displaystyle{ y\in B }[/math] קיים [math]\displaystyle{ x\in A }[/math] כך ש[math]\displaystyle{ f(x)=y }[/math]
  • תהי [math]\displaystyle{ X\subseteq A }[/math] נגדיר את קבוצת התמונה [math]\displaystyle{ f[X]=\{f(a)|a\in X\} }[/math]
  • תהי [math]\displaystyle{ Y\subseteq B }[/math] נגדיר את קבוצת התמונה ההפוכה [math]\displaystyle{ f^{-1}[Y]=\{a\in A|f(a)\in Y\} }[/math]
  • [math]\displaystyle{ f[]:P(A)\to P(B) }[/math] היא פונקצית התמונה, השולחת כל תת קבוצה לקבוצת התמונה שלה
  • [math]\displaystyle{ f^{-1}[]:P(B)\to P(A) }[/math] היא פונקצית התמונה ההפוכה, השולחת כל תת קבוצה לקבוצת התמונה ההפוכה שלה

• אם [math]\displaystyle{ f(a)=b }[/math] אומרים כי b היא התמונה של a, וכי a הוא מקור של b.
• התמונה של f היא [math]\displaystyle{ Im(f)=f[A]=\{b\in B|\exists a\in A:f(a)=b\} }[/math], כלומר קבוצת האיברים בטווח שיש להם מקור. למשל עבור [math]\displaystyle{ f:\mathbb{R}\to\mathbb{R} }[/math] המוגדרת ע"י [math]\displaystyle{ f(x)=\sin(x) }[/math] מתקיים [math]\displaystyle{ Im(f)=[-1,1] }[/math].
• לכל פונקציה [math]\displaystyle{ f:A\to B }[/math], אותו היחס f הוא גם פונקציה [math]\displaystyle{ f:A\to Im(f) }[/math], והיא על.

הוכחה. כל זוג ב-f הוא מהצורה [math]\displaystyle{ (a,f(a)) }[/math] עבור [math]\displaystyle{ a\in A }[/math], ו[math]\displaystyle{ f(a)\in Im(f) }[/math]. לכן [math]\displaystyle{ f\subseteq A\times Im(f) }[/math]. היחס עצמו לא השתנה, ולכן הוא עדיין ח"ע, והוא שלם מ-A ל[math]\displaystyle{ Im(f) }[/math] (לכל [math]\displaystyle{ a\in A }[/math] מתקיים [math]\displaystyle{ (a,f(a))\in f }[/math] וכן [math]\displaystyle{ f(a)\in Im(f) }[/math]). כלומר [math]\displaystyle{ f:A\to Im(f) }[/math] היא פונקציה. היא על: לכל [math]\displaystyle{ b\in Im(f) }[/math] קיים, לפי הגדרת התמונה, [math]\displaystyle{ a\in A }[/math] כך ש[math]\displaystyle{ f(a)=b }[/math].

הערה: לעומת זאת, חח"ע היא תכונה מהותית יותר. אם f אינה חח"ע, קיימים [math]\displaystyle{ a_1\neq a_2 }[/math] ו-b כך ש[math]\displaystyle{ (a_1,b),(a_2,b)\in f }[/math], ובשביל לתקן זאת צריך למחוק את אחד הזוגות, כלומר לשנות את היחס עצמו. ▶ ההוכחה בהרצאה מ־29.7.26, החל מהדקה 24:01

• שימו לב
  • [math]\displaystyle{ x\in f^{-1}[Y]\iff f(x)\in Y }[/math]
  • [math]\displaystyle{ y\in f[X] \iff \exist a\in X :f(a)=y }[/math]

• תהי [math]\displaystyle{ f:A\to B }[/math]. פונקציות התמונה והתמונה ההפוכה מונוטוניות ביחס להכלה (תרגיל):
  • אם [math]\displaystyle{ X_1\subseteq X_2\subseteq A }[/math] אזי [math]\displaystyle{ f[X_1]\subseteq f[X_2] }[/math]
  • אם [math]\displaystyle{ Y_1\subseteq Y_2\subseteq B }[/math] אזי [math]\displaystyle{ f^{-1}[Y_1]\subseteq f^{-1}[Y_2] }[/math]

דוגמה: נביט ביחס [math]\displaystyle{ f=\{(x,x^2)|x\in\mathbb{R}\} }[/math]. אפשר להסתכל עליו כעל פונקציה [math]\displaystyle{ f:\mathbb{R}\to\mathbb{R} }[/math] או כעל פונקציה [math]\displaystyle{ f:\mathbb{R}\to[0,\infty) }[/math]. האם כל אחת מהן חח"ע? על?

• שתי הפונקציות אינן חח"ע, כי [math]\displaystyle{ f(-1)=f(1) }[/math] אך [math]\displaystyle{ -1\neq 1 }[/math].
• [math]\displaystyle{ f:\mathbb{R}\to\mathbb{R} }[/math] אינה על: אף איבר לא נשלח ל[math]\displaystyle{ -1\in\mathbb{R} }[/math], כי [math]\displaystyle{ x^2\geq 0 }[/math] לכל x ממשי.
• [math]\displaystyle{ f:\mathbb{R}\to[0,\infty) }[/math] כן על: לכל [math]\displaystyle{ y\geq 0 }[/math] מתקיים [math]\displaystyle{ f(\sqrt{y})=y }[/math].

זו הסיבה שחשוב שפונקציה היא שלשה: בלי לדעת מהו הטווח, אי אפשר לקבוע אם הפונקציה על. ▶ הפתרון בהרצאה מ־27.7.26, החל מהדקה 2:02:48

דוגמה: תהי A קבוצת הפונקציות מ[math]\displaystyle{ \mathbb{N} }[/math] ל[math]\displaystyle{ \mathbb{N} }[/math], ונגדיר [math]\displaystyle{ f:\mathbb{N}\to A }[/math] ע"י [math]\displaystyle{ f(n)(k)=n }[/math]. במילים: f שולחת את המספר n לפונקציה הקבועה n (למשל [math]\displaystyle{ f(3) }[/math] היא הפונקציה הקבועה 3). האם f חח"ע? האם f על?

• f חח"ע: ניקח שני איברים שונים מהתחום [math]\displaystyle{ n_1\neq n_2 }[/math]. אזי [math]\displaystyle{ f(n_1) }[/math] היא הפונקציה הקבועה [math]\displaystyle{ n_1 }[/math] ו[math]\displaystyle{ f(n_2) }[/math] היא הפונקציה הקבועה [math]\displaystyle{ n_2 }[/math]. מדובר בפונקציות שונות (למשל [math]\displaystyle{ f(n_1)(0)=n_1\neq n_2=f(n_2)(0) }[/math]), ולכן [math]\displaystyle{ f(n_1)\neq f(n_2) }[/math].
• f אינה על: f שולחת מספרים לפונקציות קבועות בלבד, ולכן לכל פונקציה שאינה קבועה, כמו למשל [math]\displaystyle{ g(k)=k }[/math], אין מקור.

▶ הפתרון בהרצאה מ־27.7.26, החל מהדקה 2:11:42

דוגמה: נסמן ב[math]\displaystyle{ \mathbb{R}^{\mathbb{N}} }[/math] את קבוצת כל הפונקציות מ[math]\displaystyle{ \mathbb{N} }[/math] ל[math]\displaystyle{ \mathbb{R} }[/math] (באופן כללי [math]\displaystyle{ B^A }[/math] היא קבוצת כל הפונקציות מ-A ל-B), ונביט בפונקציה [math]\displaystyle{ h:\mathbb{R}^{\mathbb{N}}\to P(\mathbb{R}) }[/math] המוגדרת ע"י [math]\displaystyle{ h(f)=\{f(0),f(1)\} }[/math]. למשל עבור [math]\displaystyle{ f(x)=x+2 }[/math] מתקיים [math]\displaystyle{ h(f)=\{2,3\} }[/math], ועבור [math]\displaystyle{ f(x)=x^2-x }[/math] מתקיים [math]\displaystyle{ h(f)=\{0\} }[/math]. האם h חח"ע? האם h על?

• h אינה חח"ע: עבור [math]\displaystyle{ f_1(x)=x^2-x }[/math] ו[math]\displaystyle{ f_2(x)=x^3-x }[/math] מתקיים [math]\displaystyle{ h(f_1)=h(f_2)=\{0\} }[/math], אך אלו פונקציות שונות (למשל [math]\displaystyle{ f_1(2)=2\neq 6=f_2(2) }[/math]).
• h אינה על: בקבוצה [math]\displaystyle{ \{f(0),f(1)\} }[/math] יש איבר אחד או שניים, ובפרט [math]\displaystyle{ \{f(0),f(1)\}\neq\emptyset }[/math] לכל f. לכן לקבוצה הריקה [math]\displaystyle{ \emptyset\in P(\mathbb{R}) }[/math] אין מקור.

▶ הפתרון בהרצאה מ־27.7.26, החל מהדקה 2:23:17

דוגמה: תהי [math]\displaystyle{ f:\mathbb{R}\to\mathbb{R} }[/math] המוגדרת ע"י [math]\displaystyle{ f(x)=x^2 }[/math]. חשבו את [math]\displaystyle{ f[\{1,0,-1\}] }[/math] ואת [math]\displaystyle{ f^{-1}[\{-1,-2\}] }[/math]. האם פונקציית התמונה ההפוכה [math]\displaystyle{ f^{-1}[]:P(\mathbb{R})\to P(\mathbb{R}) }[/math] חח"ע? האם היא על?

• מפעילים את f על כל האיברים: [math]\displaystyle{ f[\{1,0,-1\}]=\{f(1),f(0),f(-1)\}=\{0,1\} }[/math].
• [math]\displaystyle{ f^{-1}[\{-1,-2\}]=\emptyset }[/math], כי אין x ממשי עבורו [math]\displaystyle{ x^2\in\{-1,-2\} }[/math].
• [math]\displaystyle{ f^{-1}[] }[/math] אינה חח"ע: גם [math]\displaystyle{ f^{-1}[\{-1\}]=\emptyset }[/math], כלומר שתי הקבוצות השונות [math]\displaystyle{ \{-1\} }[/math] ו[math]\displaystyle{ \{-1,-2\} }[/math] נשלחות לאותה קבוצה.
• [math]\displaystyle{ f^{-1}[] }[/math] אינה על. במילים: פונקציית התמונה ההפוכה שולחת קבוצת איברים לקבוצת המקורות שלהם, ובפונקציה שלנו המקורות באים בזוגות (x ו-[math]\displaystyle{ -x }[/math], פרט ל-0). לכן נטען שלקבוצה [math]\displaystyle{ \{3\} }[/math] אין מקור, כלומר לא קיימת [math]\displaystyle{ Y\subseteq\mathbb{R} }[/math] כך ש[math]\displaystyle{ f^{-1}[Y]=\{3\} }[/math].

נב"ש שיש Y כזו. אז [math]\displaystyle{ 3\in f^{-1}[Y] }[/math], ולכן [math]\displaystyle{ 9=f(3)\in Y }[/math]. אבל גם [math]\displaystyle{ f(-3)=9\in Y }[/math], ולכן [math]\displaystyle{ -3\in f^{-1}[Y]=\{3\} }[/math]. סתירה.

▶ הפתרון בהרצאה מ־27.7.26, החל מהדקה 3:00:06

דוגמה: תהי פונקציה [math]\displaystyle{ f:A\to B }[/math] ותהי [math]\displaystyle{ X\subseteq A }[/math]. הפריכו: [math]\displaystyle{ f^{-1}[f[X]]=X }[/math].

נביט ב[math]\displaystyle{ f:\mathbb{R}\to\mathbb{R} }[/math], [math]\displaystyle{ f(x)=x^2 }[/math] וב[math]\displaystyle{ X=\{3\} }[/math]. אזי

[math]\displaystyle{ f^{-1}[f[\{3\}]]=f^{-1}[\{9\}]=\{-3,3\}\neq\{3\} }[/math]

(תרגיל: הוכיחו שתמיד מתקיימת ההכלה [math]\displaystyle{ X\subseteq f^{-1}[f[X]] }[/math].) ▶ הפתרון בהרצאה מ־27.7.26, החל מהדקה 3:16:43

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

• תהיינה [math]\displaystyle{ f:A\to B }[/math] וכן [math]\displaystyle{ g:B\to C }[/math] אזי נגדיר את פונקצית ההרכבה [math]\displaystyle{ g\circ f:A\to C }[/math] ע"י [math]\displaystyle{ g\circ f(a)=g(f(a)) }[/math]
• פעולת ההרכבה היא אסוציאטיבית.

הוכחה. ננסח במדויק: תהיינה שלוש פונקציות f,g,h. אם אחד מהצדדים הבאים מוגדר, אז גם השני מוגדר ושווה לו:

[math]\displaystyle{ (f\circ g)\circ h=f\circ (g\circ h) }[/math]

ראשית - כיצד מוכיחים שפונקציות שוות? מוכיחים שהתחומים שווים, שהטווחים שווים, ושהיחסים שווים (כלומר הפונקציה האחת שולחת כל איבר לאותו המקום כמו השנייה).

נניח שצד ימין מוגדר, ונסמן [math]\displaystyle{ h:A\to B }[/math]. כדי ש[math]\displaystyle{ g\circ h }[/math] תהיה מוגדרת, בהכרח [math]\displaystyle{ g:B\to C }[/math] עבור קבוצה C כלשהי, ואז [math]\displaystyle{ g\circ h:A\to C }[/math]. כדי ש[math]\displaystyle{ f\circ (g\circ h) }[/math] תהיה מוגדרת, בהכרח [math]\displaystyle{ f:C\to D }[/math] עבור קבוצה D כלשהי, ואז [math]\displaystyle{ f\circ (g\circ h):A\to D }[/math]. כעת [math]\displaystyle{ f\circ g:B\to D }[/math] מוגדרת, ולכן גם [math]\displaystyle{ (f\circ g)\circ h:A\to D }[/math] מוגדרת, עם אותו תחום ואותו טווח. הכיוון ההפוך (אם צד שמאל מוגדר אז גם צד ימין מוגדר) דומה.

נותר להראות שהנוסחאות זהות. יהי [math]\displaystyle{ a\in A }[/math], אזי:

[math]\displaystyle{ ((f\circ g)\circ h)(a)=(f\circ g)(h(a))=f(g(h(a))) }[/math]

[math]\displaystyle{ (f\circ (g\circ h))(a)=f((g\circ h)(a))=f(g(h(a))) }[/math]

ולכן שתי הפונקציות שוות.

הערה: איך ייתכן שההוכחה של אסוציאטיביות ההרכבה קלה יותר מהוכחת אסוציאטיביות כפל מטריצות, הרי מטריצות הן פונקציות לינאריות וכפל מטריצות הוא הרכבה? תשובה: על מנת להוכיח שמטריצות מייצגות פונקציות לינאריות (שכפלן מתאים להרכבתן), משתמשים באסוציאטיביות הכפל. ▶ ההוכחה בהרצאה מ־29.7.26, החל מהדקה 1:21:46

• תהי קבוצה A נגדיר את פונקצית הזהות [math]\displaystyle{ I_A:A\to A }[/math] ע"י [math]\displaystyle{ I_A(x)=x }[/math].
• לכל פונקציה [math]\displaystyle{ f:A\to B }[/math] מתקיים כי [math]\displaystyle{ I_B\circ f = f\circ I_A = f }[/math]

• תהיינה [math]\displaystyle{ f:A\to B }[/math] וכן [math]\displaystyle{ g:B\to C }[/math]. אזי:
  • אם f וg חח"ע, גם [math]\displaystyle{ g\circ f }[/math] חח"ע.
  • אם f וg על, גם [math]\displaystyle{ g\circ f }[/math] על.

הוכחה. חח"ע: יהיו [math]\displaystyle{ x_1,x_2\in A }[/math] כך ש[math]\displaystyle{ g\circ f(x_1)=g\circ f(x_2) }[/math]. צ"ל [math]\displaystyle{ x_1=x_2 }[/math]. נתון

[math]\displaystyle{ g(f(x_1))=g(f(x_2)) }[/math]

כיוון שg חח"ע נובע [math]\displaystyle{ f(x_1)=f(x_2) }[/math], וכיוון שf חח"ע נובע [math]\displaystyle{ x_1=x_2 }[/math].

על: צ"ל שלכל [math]\displaystyle{ c\in C }[/math] קיים [math]\displaystyle{ a\in A }[/math] כך ש[math]\displaystyle{ g\circ f(a)=c }[/math], כלומר [math]\displaystyle{ g(f(a))=c }[/math]. יהי [math]\displaystyle{ c\in C }[/math]. כיוון שg על, קיים [math]\displaystyle{ b\in B }[/math] כך ש[math]\displaystyle{ g(b)=c }[/math]. נרצה למצוא a עבורו [math]\displaystyle{ f(a)=b }[/math] ואז סיימנו: אכן קיים [math]\displaystyle{ a\in A }[/math] כזה כי f על, ואז [math]\displaystyle{ g(f(a))=g(b)=c }[/math]. ▶ ההוכחה בהרצאה מ־29.7.26, החל מהדקה 2:04:07

• תהיינה [math]\displaystyle{ f:A\to B }[/math] וכן [math]\displaystyle{ g:B\to C }[/math]. אזי:
  • אם [math]\displaystyle{ g\circ f }[/math] חח"ע, אז הפנימית f חח"ע. (החיצונית g לא חייבת להיות חח"ע - ראו דוגמה בסוף הסעיף.)
  • אם [math]\displaystyle{ g\circ f }[/math] על, אז החיצונית g על. (הפנימית f לא חייבת להיות על - ראו דוגמה בסוף הסעיף.)

הוכחה. חח"ע: נניח כי [math]\displaystyle{ g\circ f }[/math] חח"ע. יהיו [math]\displaystyle{ a_1,a_2\in A }[/math] כך ש[math]\displaystyle{ f(a_1)=f(a_2) }[/math]. צ"ל [math]\displaystyle{ a_1=a_2 }[/math]. נפעיל את g על שני האגפים:

[math]\displaystyle{ g(f(a_1))=g(f(a_2)) }[/math]

כלומר [math]\displaystyle{ g\circ f(a_1)=g\circ f(a_2) }[/math]. כיוון ש[math]\displaystyle{ g\circ f }[/math] חח"ע נובע כי [math]\displaystyle{ a_1=a_2 }[/math], כפי שרצינו.

על: נניח כי [math]\displaystyle{ g\circ f }[/math] על. יהי [math]\displaystyle{ c\in C }[/math]. צריך להוכיח שקיים [math]\displaystyle{ b\in B }[/math] כך ש[math]\displaystyle{ g(b)=c }[/math]. כיוון ש[math]\displaystyle{ g\circ f:A\to C }[/math] על, קיים [math]\displaystyle{ a\in A }[/math] כך ש[math]\displaystyle{ g\circ f(a)=c }[/math], כלומר [math]\displaystyle{ g(f(a))=c }[/math]. נבחר [math]\displaystyle{ b=f(a)\in B }[/math], ואז [math]\displaystyle{ g(b)=c }[/math]. ▶ ההוכחה בהרצאה מ־29.7.26, החל מהדקה 2:23:27

• פונקציה [math]\displaystyle{ f:A\to B }[/math] נקראת הפיכה אם קיימות פונקציות [math]\displaystyle{ g,h:B\to A }[/math] כך ש:
  • [math]\displaystyle{ g\circ f = I_A }[/math] וכן [math]\displaystyle{ f\circ h = I_B }[/math]
• נשים לב כי
  • [math]\displaystyle{ h=I_A\circ h = (g\circ f)\circ h = g\circ (f\circ h)=g\circ I_B = g }[/math]
• לכן אם פונקציה הפיכה, יש פונקציה יחידה שהופכת אותה (ההופכית), נסמנה [math]\displaystyle{ f^{-1}:B\to A }[/math].
• שימו לב: עם סוגריים מרובעים זו פונקצית התמונה ההפוכה שיש לכל פונקציה ופועלת על תתי קבוצות, עם סוגריים עגולים זו הפונקציה ההופכית שיש רק להפיכות ופועלת על איברים.

• משפט: תהי [math]\displaystyle{ f:A\to B }[/math]. אזי f הפיכה אם ורק אם f חח"ע ועל.

הוכחה. כיוון ראשון: נניח כי f הפיכה. לכן קיימת ההופכית [math]\displaystyle{ f^{-1}:B\to A }[/math] עבורה

[math]\displaystyle{ f\circ f^{-1}=I_B,\quad f^{-1}\circ f=I_A }[/math]

• כיוון ש[math]\displaystyle{ f\circ f^{-1}=I_B }[/math] היא על, גם החיצונית f היא על (לפי הטענה על הרכבה שהיא על).
• כיוון ש[math]\displaystyle{ f^{-1}\circ f=I_A }[/math] היא חח"ע, גם הפנימית f היא חח"ע (לפי הטענה על הרכבה שהיא חח"ע).

סה"כ f חח"ע ועל.

כיוון שני: נתון כי f חח"ע ועל, וצ"ל ש-f הפיכה. כלומר עלינו לבנות פונקציה שתהיה ההופכית של f. נביט ביחס ההפוך מ-B ל-A:

[math]\displaystyle{ f^{-1}=\{(b,a)|(a,b)\in f\}\subseteq B\times A }[/math]

וצריך להוכיח: (1) [math]\displaystyle{ f^{-1} }[/math] ח"ע; (2) [math]\displaystyle{ f^{-1} }[/math] שלם; (3) [math]\displaystyle{ f\circ f^{-1}=I_B }[/math]; (4) [math]\displaystyle{ f^{-1}\circ f=I_A }[/math].

(1) יהי איבר בתחום של [math]\displaystyle{ f^{-1} }[/math], כלומר [math]\displaystyle{ b\in B }[/math], ויהיו שני איברים בטווח של [math]\displaystyle{ f^{-1} }[/math], כלומר [math]\displaystyle{ a_1,a_2\in A }[/math], כך ש[math]\displaystyle{ (b,a_1),(b,a_2)\in f^{-1} }[/math]. צ"ל [math]\displaystyle{ a_1=a_2 }[/math]. לפי הגדרת היחס ההפוך [math]\displaystyle{ (a_1,b),(a_2,b)\in f }[/math], כלומר [math]\displaystyle{ f(a_1)=b=f(a_2) }[/math], וכיוון שf חח"ע נובע כי [math]\displaystyle{ a_1=a_2 }[/math].

(2) יהי [math]\displaystyle{ b\in B }[/math] איבר מהתחום. צריך להוכיח שקיים [math]\displaystyle{ a\in A }[/math] כך ש[math]\displaystyle{ (b,a)\in f^{-1} }[/math]. כיוון שf על, קיים [math]\displaystyle{ a\in A }[/math] כך ש[math]\displaystyle{ f(a)=b }[/math], כלומר [math]\displaystyle{ (a,b)\in f }[/math], ולכן [math]\displaystyle{ (b,a)\in f^{-1} }[/math].

עד כה הוכחנו כי [math]\displaystyle{ f^{-1}:B\to A }[/math] היא פונקציה.

(3) התחום והטווח של [math]\displaystyle{ f\circ f^{-1} }[/math] הם B ו-B לפי הגדרת ההרכבה, ונותר להוכיח שלכל [math]\displaystyle{ b\in B }[/math] מתקיים [math]\displaystyle{ f\circ f^{-1}(b)=I_B(b) }[/math]. יהי [math]\displaystyle{ b\in B }[/math]. כיוון שf על, קיים [math]\displaystyle{ a\in A }[/math] כך ש[math]\displaystyle{ f(a)=b }[/math], כלומר [math]\displaystyle{ (a,b)\in f }[/math], ולכן [math]\displaystyle{ (b,a)\in f^{-1} }[/math], כלומר [math]\displaystyle{ f^{-1}(b)=a }[/math]. סה"כ

[math]\displaystyle{ f\circ f^{-1}(b)=f(f^{-1}(b))=f(a)=b=I_B(b) }[/math]

(4) דומה: יהי [math]\displaystyle{ a\in A }[/math] ונסמן [math]\displaystyle{ b=f(a) }[/math]. אזי [math]\displaystyle{ (a,b)\in f }[/math], ולכן [math]\displaystyle{ (b,a)\in f^{-1} }[/math], כלומר [math]\displaystyle{ f^{-1}(b)=a }[/math]. סה"כ

[math]\displaystyle{ f^{-1}\circ f(a)=f^{-1}(f(a))=f^{-1}(b)=a=I_A(a) }[/math]

לכן f הפיכה (בהגדרת ההפיכות אפשר לבחור [math]\displaystyle{ g=h=f^{-1} }[/math]). ▶ ההוכחה בהרצאה מ־29.7.26, החל מהדקה 2:49:38

דוגמה: יהיו [math]\displaystyle{ f,g:\mathbb{R}\to\mathbb{R} }[/math] המוגדרות ע"י [math]\displaystyle{ f(x)=\sin(x) }[/math] ו[math]\displaystyle{ g(x)=x^2 }[/math]. חשבו את [math]\displaystyle{ f\circ g }[/math] ואת [math]\displaystyle{ g\circ f }[/math].

[math]\displaystyle{ f\circ g(x)=\sin(x^2),\quad g\circ f(x)=\sin^2(x) }[/math]

אלו פונקציות שונות: למשל [math]\displaystyle{ g\circ f(x)=\sin^2(x)\geq 0 }[/math] לכל x, אבל [math]\displaystyle{ f\circ g\left(\sqrt{3\pi/2}\right)=\sin(3\pi/2)=-1 }[/math]. כלומר חוק החילוף אינו מתקיים עבור הרכבה (ולעיתים ההרכבה בכיוון ההפוך כלל אינה מוגדרת). ▶ הפתרון בהרצאה מ־29.7.26, החל מהדקה 56:57

דוגמה: יהיו [math]\displaystyle{ f:\mathbb{N}\to P(\mathbb{N}) }[/math] המוגדרת ע"י [math]\displaystyle{ f(n)=\{0,1,2,\dots,n\} }[/math], ו[math]\displaystyle{ g:P(\mathbb{N})\to\mathbb{N} }[/math] המוגדרת ע"י [math]\displaystyle{ g(A)=\min(A\cup\{8\}) }[/math]. חשבו את [math]\displaystyle{ f(g(\{4,7,9\})) }[/math] ואת [math]\displaystyle{ g\circ f }[/math].

(שימו לב ש-g מוגדרת היטב: [math]\displaystyle{ A\cup\{8\} }[/math] היא תת קבוצה לא ריקה של הטבעיים, ולכן יש לה מינימום.)

[math]\displaystyle{ f(g(\{4,7,9\}))=f(4)=\{0,1,2,3,4\} }[/math]

ולכל [math]\displaystyle{ n\in\mathbb{N} }[/math]:

[math]\displaystyle{ g(f(n))=g(\{0,1,\dots,n\})=0 }[/math]

כלומר [math]\displaystyle{ g\circ f:\mathbb{N}\to\mathbb{N} }[/math] היא הפונקציה הקבועה 0, ואילו [math]\displaystyle{ f\circ g:P(\mathbb{N})\to P(\mathbb{N}) }[/math] היא פונקציה מסוג אחר לגמרי. ▶ הפתרון בהרצאה מ־29.7.26, החל מהדקה 1:12:57

דוגמה: יהיו [math]\displaystyle{ f,g:\mathbb{N}\to\mathbb{N} }[/math] המוגדרות ע"י [math]\displaystyle{ f(n)=2n }[/math], וכן [math]\displaystyle{ g(n)=\frac{n}{2} }[/math] אם n זוגי ו[math]\displaystyle{ g(n)=0 }[/math] אחרת. חשבו את [math]\displaystyle{ g\circ f }[/math] ואת [math]\displaystyle{ f\circ g }[/math]. מה ניתן ללמוד מכך?

• לכל n מתקיים [math]\displaystyle{ g(f(n))=g(2n)=\frac{2n}{2}=n }[/math], כלומר [math]\displaystyle{ g\circ f=I_{\mathbb{N}} }[/math].
• [math]\displaystyle{ f(g(n))=n }[/math] אם n זוגי, ו[math]\displaystyle{ f(g(n))=f(0)=0 }[/math] אחרת. בפרט [math]\displaystyle{ f(g(1))=0\neq 1 }[/math], ולכן [math]\displaystyle{ f\circ g\neq I_{\mathbb{N}} }[/math].
• f חח"ע (אם [math]\displaystyle{ 2n_1=2n_2 }[/math] אז [math]\displaystyle{ n_1=n_2 }[/math]) אך אינה על (לאי-זוגיים אין מקור). g על (לכל n מתקיים [math]\displaystyle{ g(2n)=n }[/math]) אך אינה חח"ע (למשל [math]\displaystyle{ g(1)=g(3)=0 }[/math]).
• לעומת זאת [math]\displaystyle{ g\circ f=I_{\mathbb{N}} }[/math] חח"ע ועל. לכן: מכך ש[math]\displaystyle{ g\circ f }[/math] חח"ע לא נובע שהחיצונית g חח"ע, ומכך ש[math]\displaystyle{ g\circ f }[/math] על לא נובע שהפנימית f על.
• f וg אינן הפיכות: אילו g הייתה הפיכה, היה נובע [math]\displaystyle{ f=(g^{-1}\circ g)\circ f=g^{-1}\circ (g\circ f)=g^{-1} }[/math], ואז [math]\displaystyle{ f\circ g=g^{-1}\circ g=I_{\mathbb{N}} }[/math] - סתירה. באופן דומה, אילו f הייתה הפיכה, היה נובע [math]\displaystyle{ g=g\circ (f\circ f^{-1})=(g\circ f)\circ f^{-1}=f^{-1} }[/math], ושוב [math]\displaystyle{ f\circ g=I_{\mathbb{N}} }[/math] - סתירה. (זה נובע גם מהמשפט: f אינה על, וg אינה חח"ע.)

▶ הפתרון בהרצאה מ־29.7.26, החל מהדקה 2:11:25

דוגמה: האם [math]\displaystyle{ e^{\ln(x)}=\ln(e^x) }[/math]?

לא. ההבדל הוא בתחום (בשפה התיכונית - "תחום ההגדרה"). מתקיים [math]\displaystyle{ e^x:\mathbb{R}\to(0,\infty) }[/math] וכן [math]\displaystyle{ \ln(x):(0,\infty)\to\mathbb{R} }[/math], ולכן

[math]\displaystyle{ e^{\ln(x)}=I_{(0,\infty)} }[/math]

[math]\displaystyle{ \ln(e^x)=I_{\mathbb{R}} }[/math]

ההרכבות אינן שוות (אלו פונקציות זהות על קבוצות שונות), אף על פי שמדובר בפונקציות הופכיות זו לזו: הרכבה בכיוון אחד נותנת את הזהות על התחום, ובכיוון השני את הזהות על הטווח. ▶ הפתרון בהרצאה מ־29.7.26, החל מהדקה 2:36:21

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

• "מוגדרת היטב" אינו מושג מתמטי חדש: זה כינוי לבדיקה שמה שכתבנו אכן עומד בהגדרה של פונקציה. כדי להראות שביטוי מגדיר פונקציה [math]\displaystyle{ f:A\to B }[/math], כותבים את f כיחס (אוסף זוגות) ובודקים שלושה דברים:
  • [math]\displaystyle{ f\subseteq A\times B }[/math]
  • f ח"ע מA לB
  • f שלם מA לB

דוגמה: האם [math]\displaystyle{ f:\mathbb{Q}\to\mathbb{Z} }[/math] המוגדרת ע"י [math]\displaystyle{ f\left(\frac{p}{q}\right)=p }[/math] היא פונקציה מוגדרת היטב?

לא. הביטוי אף מוביל לסתירה:

[math]\displaystyle{ 2=f\left(\frac{2}{4}\right)=f\left(\frac{1}{2}\right)=1 }[/math]

מה שהיה צריך לכתוב הוא היחס

[math]\displaystyle{ f=\left\{\left(\frac{p}{q},p\right)|p,q\in\mathbb{Z},q\neq 0\right\} }[/math]

ועכשיו בודקים את שלושת התנאים:

• [math]\displaystyle{ f\subseteq\mathbb{Q}\times\mathbb{Z} }[/math] - מתקיים.
• f ח"ע מ[math]\displaystyle{ \mathbb{Q} }[/math] ל[math]\displaystyle{ \mathbb{Z} }[/math] - לא מתקיים: [math]\displaystyle{ \left(\frac{1}{2},1\right),\left(\frac{1}{2},2\right)\in f }[/math] (כי [math]\displaystyle{ \frac{1}{2}=\frac{2}{4} }[/math]), אך [math]\displaystyle{ 1\neq 2 }[/math].
• f שלם מ[math]\displaystyle{ \mathbb{Q} }[/math] ל[math]\displaystyle{ \mathbb{Z} }[/math] - מתקיים (כל רציונלי ניתן לכתוב בצורה [math]\displaystyle{ \frac{p}{q} }[/math]).

לכן f אינה פונקציה, ולמעשה אסור היה לכתוב [math]\displaystyle{ f\left(\frac{p}{q}\right)=p }[/math] מלכתחילה - הסימון [math]\displaystyle{ f(a)=b }[/math] מותר רק כשהיחס הוא פונקציה. ▶ הפתרון בהרצאה מ־27.7.26, החל מהדקה 32:52

דוגמה: את הטענה [math]\displaystyle{ \forall x\in\mathbb{R}\exists y\in\mathbb{R}:y<x }[/math] אפשר להוכיח כך: "יהי x, נבחר [math]\displaystyle{ y=x-1 }[/math]". מה הבעיה אם נוכיח באותה דרך את הטענה [math]\displaystyle{ \forall x>0\exists y>0:y<x }[/math]?

ההוכחה משתמשת למעשה ב"פונקציה" [math]\displaystyle{ y:(0,\infty)\to(0,\infty) }[/math] המוגדרת ע"י [math]\displaystyle{ y(x)=x-1 }[/math], והיא אינה מוגדרת היטב. אם נכתוב אותה כיחס [math]\displaystyle{ y=\{(x,x-1)|x>0\} }[/math], הבעיה אינה בח"ע (לכל x יש ערך יחיד), אלא בתנאי הראשון:

[math]\displaystyle{ y\not\subseteq(0,\infty)\times(0,\infty) }[/math]

למשל [math]\displaystyle{ \left(\frac{1}{2},-\frac{1}{2}\right)\in y }[/math], אבל [math]\displaystyle{ -\frac{1}{2}\notin(0,\infty) }[/math]. (הוכחה נכונה: נבחר למשל [math]\displaystyle{ y=\frac{x}{2} }[/math].) ▶ הפתרון בהרצאה מ־27.7.26, החל מהדקה 50:33

תרגול

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

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

פרק 5 - עוצמות

📄 דף נושא: עוצמות של קבוצות - הגדרות, דוגמאות פתורות, שאלות ממבחנים וסרטונים

מבוא

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

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

הוכחה. שימו לב: באופן פורמלי שקילות עוצמה אינה יחס, כי אין "קבוצת כל הקבוצות" שעליה אפשר להגדיר אותו. למרות זאת נבדוק שמתקיימות שלוש התכונות של יחס שקילות.

רפלקסיביות: צריך להראות שקיימת פונקציה הפיכה מA לA. אכן, פונקציית הזהות [math]\displaystyle{ I_A:A\to A }[/math] היא כזו.

סימטריות: נתון שקיימת [math]\displaystyle{ f:A\to B }[/math] הפיכה. ההופכית שלה, [math]\displaystyle{ f^{-1}:B\to A }[/math], גם היא הפיכה, ולכן B שקולת עוצמה לA.

טרנזיטיביות: נתון שקיימות [math]\displaystyle{ f:A\to B }[/math] ו־[math]\displaystyle{ g:B\to C }[/math] הפיכות. לכן [math]\displaystyle{ g\circ f:A\to C }[/math] הפיכה: הרכבת פונקציות חח"ע היא חח"ע והרכבת פונקציות על היא על (או: ההופכית שלה היא [math]\displaystyle{ f^{-1}\circ g^{-1} }[/math]). לכן A שקולת עוצמה לC.

▶ ההוכחה בהרצאה מ־3.8.26, החל מהדקה 3:59

• עוצמתה של A קטנה או שווה לזו של B, אם קיימת פונקציה חח"ע [math]\displaystyle{ f:A\to B }[/math].
• במקרה זה מסמנים [math]\displaystyle{ |A|\leq |B| }[/math]

• תכונות של השוואת עוצמות:
  • לכל קבוצה A מתקיים [math]\displaystyle{ |A|\leq |A| }[/math]
  • אם [math]\displaystyle{ |A|\leq |B| }[/math] וגם [math]\displaystyle{ |B|\leq |C| }[/math] אזי [math]\displaystyle{ |A|\leq |C| }[/math]

הוכחה. פונקציית הזהות [math]\displaystyle{ I_A:A\to A }[/math] חח"ע, ולכן [math]\displaystyle{ |A|\leq |A| }[/math].

אם [math]\displaystyle{ f:A\to B }[/math] ו־[math]\displaystyle{ g:B\to C }[/math] חח"ע, אזי [math]\displaystyle{ g\circ f:A\to C }[/math] חח"ע (הרכבת חח"ע היא חח"ע), ולכן [math]\displaystyle{ |A|\leq |C| }[/math].

הערה (אנטי־סימטריות): אם [math]\displaystyle{ |A|\leq |B| }[/math] וגם [math]\displaystyle{ |B|\leq |A| }[/math], ברור שלא נובע [math]\displaystyle{ A=B }[/math] (יתכנו קבוצות שונות עם אותה עוצמה). אבל נובע ש־[math]\displaystyle{ A\sim B }[/math]: אם קיימות [math]\displaystyle{ f:A\to B }[/math] ו־[math]\displaystyle{ g:B\to A }[/math] חח"ע, אזי קיימת [math]\displaystyle{ h:A\to B }[/math] חח"ע ועל. זהו משפט קנטור־שרדר־ברנשטיין, שיוכח בהמשך, והוא כלל אינו טריוויאלי.

הערה (השוואה): האם לכל שתי קבוצות A,B מתקיים [math]\displaystyle{ |A|\leq |B| }[/math] או [math]\displaystyle{ |B|\leq |A| }[/math]? כן, בהנחת אקסיומת הבחירה (ראו בהמשך הפרק); בלעדיה לא ניתן להוכיח זאת.

▶ ההוכחה בהרצאה מ־3.8.26, החל מהדקה 19:58

• אם [math]\displaystyle{ A\subseteq B }[/math] אזי [math]\displaystyle{ |A|\leq |B| }[/math]

הוכחה. הפונקציה [math]\displaystyle{ f:A\to B }[/math] המוגדרת ע"י [math]\displaystyle{ f(a)=a }[/math] מוגדרת היטב (כי [math]\displaystyle{ A\subseteq B }[/math]) וחח"ע. למשל [math]\displaystyle{ \aleph_0=|\mathbb{N}|\leq |\mathbb{R}|=\aleph }[/math].

שימו לב: הכלה ממש אינה גוררת עוצמה קטנה ממש. למשל [math]\displaystyle{ \mathbb{N}\subsetneq\mathbb{Q} }[/math], אבל (כפי שנראה בדוגמה להלן) [math]\displaystyle{ |\mathbb{N}|=|\mathbb{Q}| }[/math].

▶ ההוכחה בהרצאה מ־5.8.26, החל מהדקה 30:35

• כל קבוצה A השקולת עוצמה לקבוצת הטבעיים מסומנת [math]\displaystyle{ |A|=\aleph_0 }[/math]

• סדרה של איברים מA היא פונקציה [math]\displaystyle{ a:\mathbb{N}\to A }[/math], ומסמנים [math]\displaystyle{ a_n=a(n) }[/math].
• קבוצה A שקולת עוצמה לטבעיים אם ורק אם קיימת סדרה של איברי A המכילה כל איבר של A פעם אחת בדיוק.

הוכחה. סדרה של איברי A היא פונקציה [math]\displaystyle{ a:\mathbb{N}\to A }[/math]. העובדה שכל איבר של A מופיע בסדרה פירושה ש־[math]\displaystyle{ a }[/math] על, והעובדה שכל איבר מופיע לכל היותר פעם אחת פירושה ש־[math]\displaystyle{ a }[/math] חח"ע. לכן סדרה כזו היא בדיוק פונקציה הפיכה [math]\displaystyle{ a:\mathbb{N}\to A }[/math], וקיומה שקול (לפי הסימטריה) ל־[math]\displaystyle{ |A|=\aleph_0 }[/math].

לכן כדי להראות שקבוצה היא מעוצמה [math]\displaystyle{ \aleph_0 }[/math] מספיק "לסדר את כל איבריה בשורה" כך שכל איבר מופיע בדיוק פעם אחת. בהוכחה מלאה יש לכתוב את הפונקציה במפורש ולהראות שהיא מוגדרת היטב, חח"ע ועל.

▶ ההוכחה בהרצאה מ־3.8.26, החל מהדקה 34:45

• כל קבוצה A השקולת עוצמה לקבוצת הממשיים מסומנת [math]\displaystyle{ |A|=\aleph }[/math]

דוגמה: הוכיחו כי [math]\displaystyle{ \mathbb{N}\setminus\{0\}\sim\mathbb{N} }[/math].

פשוט מסדרים את כל איברי [math]\displaystyle{ \mathbb{N}\setminus\{0\} }[/math] בשורה: [math]\displaystyle{ 1,2,3,\ldots }[/math]

להוכחה מלאה נשים לב שבנינו כאן את הפונקציה [math]\displaystyle{ f:\mathbb{N}\to\mathbb{N}\setminus\{0\} }[/math], [math]\displaystyle{ f(n)=n+1 }[/math]. היא מוגדרת היטב (כי [math]\displaystyle{ n+1\neq 0 }[/math]), חח"ע (אם [math]\displaystyle{ n_1+1=n_2+1 }[/math] אזי [math]\displaystyle{ n_1=n_2 }[/math]) ועל (לכל [math]\displaystyle{ m\geq 1 }[/math] מתקיים [math]\displaystyle{ m-1\in\mathbb{N} }[/math] ו־[math]\displaystyle{ f(m-1)=m }[/math]).

כלומר הוצאת איבר אחד לא שינתה את העוצמה, דבר שאינו אפשרי בקבוצה סופית.

▶ הפתרון בהרצאה מ־3.8.26, החל מהדקה 37:03

דוגמה: הוכיחו כי קבוצת המספרים הזוגיים [math]\displaystyle{ E=\{0,2,4,\ldots\} }[/math] שקולת עוצמה לטבעיים.

הסדרה [math]\displaystyle{ 0,2,4,6,\ldots }[/math] מכילה כל מספר זוגי טבעי פעם אחת בדיוק. במפורש, [math]\displaystyle{ f:\mathbb{N}\to E }[/math], [math]\displaystyle{ f(n)=2n }[/math] היא פונקציה הפיכה (ההופכית: [math]\displaystyle{ f^{-1}(m)=\frac{m}{2} }[/math]). לכן [math]\displaystyle{ |E|=\aleph_0 }[/math].

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

באופן דומה גם קבוצת האי־זוגיים [math]\displaystyle{ O=\{1,3,5,\ldots\} }[/math] מעוצמה [math]\displaystyle{ \aleph_0 }[/math], בעזרת [math]\displaystyle{ g(n)=2n+1 }[/math].

▶ הפתרון בהרצאה מ־3.8.26, החל מהדקה 40:00

דוגמה: הוכיחו כי [math]\displaystyle{ |\mathbb{Z}|=\aleph_0 }[/math].

נסדר את השלמים בשורה:

[math]\displaystyle{ 0,-1,1,-2,2,-3,3,\ldots }[/math]

כל מספר שלם מופיע בסדרה הזו פעם אחת בדיוק. במפורש, זו הפונקציה ההפיכה [math]\displaystyle{ f:\mathbb{N}\to\mathbb{Z} }[/math] המוגדרת לכל [math]\displaystyle{ k\in\mathbb{N} }[/math] ע"י [math]\displaystyle{ f(2k)=k }[/math] ו־[math]\displaystyle{ f(2k+1)=-(k+1) }[/math].

▶ הפתרון בהרצאה מ־3.8.26, החל מהדקה 42:30

דוגמה: הוכיחו כי [math]\displaystyle{ |\mathbb{Q}|=\aleph_0 }[/math].

נסדר תחילה את השברים האי־שליליים בשורה. נסדר אותם לפי הסכום של המונה והמכנה: לכל סכום יש כמות סופית של שברים, מסיימים אותם וממשיכים לסכום הבא. לא חוזרים על מספרים שכבר הופיעו (למשל [math]\displaystyle{ \frac{2}{4}=\frac{1}{2} }[/math] כבר הופיע):

[math]\displaystyle{ 0,\ 1,\ \tfrac{1}{2},\ 2,\ \tfrac{1}{3},\ 3, }[/math]

[math]\displaystyle{ \tfrac{1}{4},\ \tfrac{2}{3},\ \tfrac{3}{2},\ 4,\ \tfrac{1}{5},\ 5, }[/math]

[math]\displaystyle{ \tfrac{1}{6},\ \tfrac{2}{5},\ \tfrac{3}{4},\ \tfrac{4}{3},\ \tfrac{5}{2},\ 6,\ \ldots }[/math]

כל רציונלי אי־שלילי [math]\displaystyle{ \frac{p}{q} }[/math] (בהצגה מצומצמת) מופיע בסדרה בדיוק פעם אחת, בשלב של הסכום [math]\displaystyle{ p+q }[/math].

את השליליים נשלב בין לבין, כמו בשלמים: אם [math]\displaystyle{ q_1,q_2,q_3,\ldots }[/math] הם השברים החיוביים לפי הסדר לעיל, נסדר

[math]\displaystyle{ 0,\ q_1,\ -q_1,\ q_2,\ -q_2,\ \ldots }[/math]

וכך כל מספר רציונלי מופיע בדיוק פעם אחת. לכן [math]\displaystyle{ |\mathbb{Q}|=\aleph_0 }[/math], וביחד [math]\displaystyle{ |\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}| }[/math].

▶ הפתרון בהרצאה מ־3.8.26, החל מהדקה 43:24

משפט קנטור

• [math]\displaystyle{ |A|<|P(A)| }[/math]

הוכחה. [math]\displaystyle{ |A|<|P(A)| }[/math] פירושו [math]\displaystyle{ |A|\leq |P(A)| }[/math] וגם [math]\displaystyle{ |A|\neq |P(A)| }[/math].

ראשית, [math]\displaystyle{ |A|\leq |P(A)| }[/math]: הפונקציה [math]\displaystyle{ f:A\to P(A) }[/math] המוגדרת ע"י [math]\displaystyle{ f(a)=\{a\} }[/math] היא בבירור חח"ע.

כעת נוכיח כי [math]\displaystyle{ |A|\neq |P(A)| }[/math]. נראה שאף פונקציה מA ל־[math]\displaystyle{ P(A) }[/math] אינה על. תהי [math]\displaystyle{ f:A\to P(A) }[/math], ונביט בקבוצה

[math]\displaystyle{ D=\{a\in A\mid a\notin f(a)\} }[/math]

נב"ש שקיים [math]\displaystyle{ d\in A }[/math] עבורו [math]\displaystyle{ f(d)=D }[/math].

• אם [math]\displaystyle{ d\in D }[/math] אזי [math]\displaystyle{ d\in f(d) }[/math], ולכן לפי הגדרת D מתקיים [math]\displaystyle{ d\notin D }[/math]. סתירה.
• אם [math]\displaystyle{ d\notin D }[/math] אזי [math]\displaystyle{ d\notin f(d) }[/math], ולכן לפי הגדרת D מתקיים [math]\displaystyle{ d\in D }[/math]. סתירה.

לכן [math]\displaystyle{ D\notin Im(f) }[/math], כלומר f אינה על, ולכן לא תיתכן פונקציה הפיכה מA ל־[math]\displaystyle{ P(A) }[/math].

▶ ההוכחה בהרצאה מ־5.8.26, החל מהדקה 42:14

דוגמה: תהי [math]\displaystyle{ f:\{1,2,3,4\}\to P(\{1,2,3,4\}) }[/math] המוגדרת ע"י [math]\displaystyle{ f(1)=\emptyset }[/math], [math]\displaystyle{ f(2)=\{1,2,3,4\} }[/math], [math]\displaystyle{ f(3)=\{1\} }[/math], [math]\displaystyle{ f(4)=\{2,3,4\} }[/math]. מצאו את הקבוצה [math]\displaystyle{ D=\{a\mid a\notin f(a)\} }[/math] ובדקו האם [math]\displaystyle{ D\in Im(f) }[/math].

נבדוק לכל איבר האם הוא שייך לתמונה שלו:

[math]\displaystyle{ 1\notin f(1),\quad 2\in f(2),\quad 3\notin f(3),\quad 4\in f(4) }[/math]

לכן [math]\displaystyle{ D=\{1,3\} }[/math].

התמונה היא [math]\displaystyle{ Im(f)=\{\emptyset,\{1,2,3,4\},\{1\},\{2,3,4\}\} }[/math], ולכן [math]\displaystyle{ D\notin Im(f) }[/math] ו־f אינה על. זה לא מקרי: D שונה מכל [math]\displaystyle{ f(a) }[/math] לפחות באיבר a עצמו (אם [math]\displaystyle{ a\in f(a) }[/math] אז [math]\displaystyle{ a\notin D }[/math], ולהפך). זה בדיוק הרעיון של הוכחת משפט קנטור.

▶ הפתרון בהרצאה מ־5.8.26, החל מהדקה 35:58

• האלכסון של קנטור: קבוצת הסדרות הבינאריות [math]\displaystyle{ \{0,1\}^{\mathbb{N}} }[/math] (אוסף כל הפונקציות מ־[math]\displaystyle{ \mathbb{N} }[/math] ל־[math]\displaystyle{ \{0,1\} }[/math]) אינה שקולת עוצמה לטבעיים. יותר מזה, לא קיימת פונקציה על [math]\displaystyle{ h:\mathbb{N}\to\{0,1\}^{\mathbb{N}} }[/math].

הוכחה. תהי [math]\displaystyle{ h:\mathbb{N}\to\{0,1\}^{\mathbb{N}} }[/math] פונקציה כלשהי; נראה שהיא אינה על (ובפרט אינה הפיכה). אפשר לחשוב על h כעל "עמודה של סדרות": [math]\displaystyle{ h(0) }[/math] היא הסדרה הראשונה, [math]\displaystyle{ h(1) }[/math] השנייה, וכן הלאה. נגדיר סדרה [math]\displaystyle{ a:\mathbb{N}\to\{0,1\} }[/math] ע"י

[math]\displaystyle{ a(n)=1-h(n)(n) }[/math]

כאן [math]\displaystyle{ h(n)(n) }[/math] היא הספרה במקום הn של הסדרה במקום הn, וזה בדיוק האלכסון. [math]\displaystyle{ 1-h(n)(n) }[/math] הופך את הספרה: 0 הופך ל־1 ו־1 הופך ל־0. כלומר לסדרה a יש ספרה שונה מכל ספרה על האלכסון.

נב"ש שקיים [math]\displaystyle{ k\in\mathbb{N} }[/math] כך ש־[math]\displaystyle{ h(k)=a }[/math], כלומר a היא הסדרה במקום k. אזי [math]\displaystyle{ a(k)=h(k)(k) }[/math], אבל לפי ההגדרה [math]\displaystyle{ a(k)=1-h(k)(k)\neq h(k)(k) }[/math]. סתירה, ולכן a אינה בתמונה של h.

המחשה: אם

[math]\displaystyle{ h(0)=100100100\ldots }[/math]

[math]\displaystyle{ h(1)=010101010\ldots }[/math]

[math]\displaystyle{ h(2)=111111111\ldots }[/math]

[math]\displaystyle{ h(3)=110110110\ldots }[/math]

[math]\displaystyle{ h(4)=101001000\ldots }[/math]

אזי ספרות האלכסון הן [math]\displaystyle{ 1,1,1,1,0,\ldots }[/math], ולכן [math]\displaystyle{ a=00001\ldots }[/math], השונה מכל אחת מהסדרות ברשימה.

▶ ההוכחה בהרצאה מ־5.8.26, החל מהדקה 11:52

• מסקנה: [math]\displaystyle{ \aleph_0<\aleph }[/math], כלומר קבוצת הממשיים אינה שקולת עוצמה לטבעיים.

הוכחה. כיוון ש־[math]\displaystyle{ \mathbb{N}\subseteq\mathbb{R} }[/math], מתקיים [math]\displaystyle{ \aleph_0\leq\aleph }[/math]. נותר להראות ש־[math]\displaystyle{ \aleph_0\neq\aleph }[/math].

נתאים לכל סדרה בינארית a את המספר הממשי שספרותיו העשרוניות אחרי הנקודה הן ספרות הסדרה:

[math]\displaystyle{ \varphi(a)=0.a_0a_1a_2\ldots }[/math]

למשל [math]\displaystyle{ \varphi(111\ldots)=0.111\ldots=\frac{1}{9} }[/math]. הפונקציה [math]\displaystyle{ \varphi:\{0,1\}^{\mathbb{N}}\to\mathbb{R} }[/math] חח"ע, כי שני פיתוחים עשרוניים שונים נותנים אותו מספר רק כאשר אחד מהם מסתיים ב־9 חוזר, וכאן הספרות הן רק 0 ו־1.

נב"ש שקיימת [math]\displaystyle{ g:\mathbb{R}\to\mathbb{N} }[/math] הפיכה. אזי [math]\displaystyle{ g\circ\varphi:\{0,1\}^{\mathbb{N}}\to\mathbb{N} }[/math] חח"ע. נגדיר [math]\displaystyle{ h:\mathbb{N}\to\{0,1\}^{\mathbb{N}} }[/math] כך: אם [math]\displaystyle{ n\in Im(g\circ\varphi) }[/math], אז [math]\displaystyle{ h(n) }[/math] היא הסדרה (היחידה) a שעבורה [math]\displaystyle{ g(\varphi(a))=n }[/math]; אחרת [math]\displaystyle{ h(n) }[/math] היא סדרת האפסים. הפונקציה h על, כי כל סדרה a מתקבלת כ־[math]\displaystyle{ h(g(\varphi(a))) }[/math]. זו סתירה לאלכסון של קנטור.

במילים: אפילו הקבוצה ה"קטנה" של הממשיים בין 0 ל־1 שכל ספרותיהם הן 0 או 1 כבר אינה בת מנייה, ובוודאי ש־[math]\displaystyle{ |\mathbb{N}|\neq |\mathbb{R}| }[/math].

▶ ההוכחה בהרצאה מ־5.8.26, החל מהדקה 26:20

קבוצות בנות מנייה

• קבוצה A נקראת בת מנייה אם [math]\displaystyle{ |A|\leq \aleph_0 }[/math]

• כל קבוצה A בת מנייה אינסופית מקיימת [math]\displaystyle{ |A|=\aleph_0 }[/math]

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

חיבור עוצמות

• תהיינה שתי עוצמות a,b ותהיינה שתי נציגות זרות לעוצמות A,B.
• נגדיר [math]\displaystyle{ a+b=|A\cup B| }[/math], הגדרה זו אינה תלוייה בבחירת הנציגות.

הוכחה. צריך להוכיח: אם A,B זרות, C,D זרות, [math]\displaystyle{ A\sim C }[/math] וגם [math]\displaystyle{ B\sim D }[/math], אזי [math]\displaystyle{ |A\cup B|=|C\cup D| }[/math].

קיימת [math]\displaystyle{ f:A\to C }[/math] הפיכה, וקיימת [math]\displaystyle{ g:B\to D }[/math] הפיכה. נבנה [math]\displaystyle{ h:A\cup B\to C\cup D }[/math]:

[math]\displaystyle{ h(x)=\begin{cases}f(x) & x\in A\\ g(x) & x\in B\end{cases} }[/math]

h מוגדרת היטב: כל איבר של [math]\displaystyle{ A\cup B }[/math] נמצא בA או בB, והערך נמצא בC או בD. התכונה היחידה שאינה ברורה היא החד־ערכיות (ששני המקרים בהגדרה אינם חלים בו־זמנית על אותו x), והיא נובעת מכך ש־[math]\displaystyle{ A\cap B=\emptyset }[/math]. זה המקום שבו משתמשים בזרות של A ו־B; בלעדיה הטענה אינה נכונה.

h על: יהי [math]\displaystyle{ y\in C\cup D }[/math]; צריך למצוא [math]\displaystyle{ x\in A\cup B }[/math] כך ש־[math]\displaystyle{ h(x)=y }[/math]. נניח [math]\displaystyle{ y\in C }[/math] (המקרה השני דומה). כיוון שf על, קיים [math]\displaystyle{ x\in A }[/math] כך ש־[math]\displaystyle{ f(x)=y }[/math], ולכן [math]\displaystyle{ h(x)=f(x)=y }[/math].

h חח"ע: יהיו [math]\displaystyle{ x_1,x_2\in A\cup B }[/math] כך ש־[math]\displaystyle{ h(x_1)=h(x_2) }[/math]. נניח [math]\displaystyle{ h(x_1)\in C }[/math] (המקרה השני דומה). כיוון ש־[math]\displaystyle{ C\cap D=\emptyset }[/math], נובע כי [math]\displaystyle{ h(x_1)\notin D }[/math], ולכן בהכרח [math]\displaystyle{ x_1\in A }[/math] (אחרת [math]\displaystyle{ h(x_1)=g(x_1)\in D }[/math]) ו־[math]\displaystyle{ h(x_1)=f(x_1) }[/math]. באופן דומה, כיוון ש־[math]\displaystyle{ h(x_2)=h(x_1)\in C }[/math], גם [math]\displaystyle{ h(x_2)=f(x_2) }[/math]. לכן [math]\displaystyle{ f(x_1)=f(x_2) }[/math], וכיוון שf חח"ע נובע כי [math]\displaystyle{ x_1=x_2 }[/math].

▶ ההוכחה בהרצאה מ־5.8.26, החל מהדקה 56:38

• לכל שתי עוצמות אפשר לבחור נציגות זרות: אם [math]\displaystyle{ |A|=a }[/math] ו־[math]\displaystyle{ |B|=b }[/math], אזי [math]\displaystyle{ \{0\}\times A }[/math] ו־[math]\displaystyle{ \{1\}\times B }[/math] הן קבוצות זרות מעוצמות a,b בהתאמה.

הוכחה. הקבוצות זרות, כי הרכיב הראשון של כל זוג ב־[math]\displaystyle{ \{0\}\times A }[/math] הוא 0, ושל כל זוג ב־[math]\displaystyle{ \{1\}\times B }[/math] הוא 1. הפונקציה [math]\displaystyle{ x\mapsto (0,x) }[/math] היא פונקציה הפיכה מA ל־[math]\displaystyle{ \{0\}\times A }[/math] (ההופכית: [math]\displaystyle{ (0,x)\mapsto x }[/math]), ולכן [math]\displaystyle{ |\{0\}\times A|=|A|=a }[/math]; ובאופן דומה [math]\displaystyle{ |\{1\}\times B|=b }[/math].

הזרות היא רק "עניין של שם": סימנו את איברי כל קבוצה בתווית אחרת, בלי לשנות את העוצמה.

▶ ההוכחה בהרצאה מ־5.8.26, החל מהדקה 1:13:50

דוגמה: חשבו את [math]\displaystyle{ \aleph_0+\aleph_0 }[/math].

נבחר נציגות זרות: הזוגיים E והאי־זוגיים O. ראינו ש־[math]\displaystyle{ |E|=|O|=\aleph_0 }[/math], וכמובן [math]\displaystyle{ E\cap O=\emptyset }[/math]. כיוון ש־[math]\displaystyle{ E\cup O=\mathbb{N} }[/math], נקבל

[math]\displaystyle{ \aleph_0+\aleph_0=|E\cup O|=|\mathbb{N}|=\aleph_0 }[/math]

שימו לב שזה לא מתנהג כמו מספרים בשדה: שם [math]\displaystyle{ x+x=x }[/math] גורר [math]\displaystyle{ x=0 }[/math].

▶ הפתרון בהרצאה מ־5.8.26, החל מהדקה 1:16:15

דוגמה: מדוע אין חיסור עוצמות? נסו להגדיר את [math]\displaystyle{ \aleph_0-\aleph_0 }[/math] כעוצמת ההפרש [math]\displaystyle{ |A\setminus B| }[/math] של נציגות [math]\displaystyle{ B\subseteq A }[/math] מעוצמה [math]\displaystyle{ \aleph_0 }[/math].

כאן בחירת הנציגות משנה את התוצאה:

[math]\displaystyle{ \mathbb{N}\setminus O=E }[/math]

[math]\displaystyle{ \mathbb{N}\setminus\mathbb{N}=\emptyset }[/math]

לפי הבחירה הראשונה יוצא [math]\displaystyle{ \aleph_0-\aleph_0=\aleph_0 }[/math], ולפי השנייה [math]\displaystyle{ \aleph_0-\aleph_0=0 }[/math], וזה לא הגיוני. לכן "חיסור עוצמות" אינו מוגדר היטב. באופן דומה יש כפל וחזקה של עוצמות, אבל אין חילוק ואין לוגריתם.

▶ הפתרון בהרצאה מ־5.8.26, החל מהדקה 1:18:00

כפל עוצמות

• תהיינה שתי עוצמות a,b ותהיינה שתי נציגות לעוצמות A,B.
• נגדיר [math]\displaystyle{ a\cdot b=|A\times B| }[/math], הגדרה זו אינה תלוייה בבחירת הנציגות.

דוגמה: חשבו את [math]\displaystyle{ \aleph_0\cdot\aleph_0 }[/math].

לפי ההגדרה [math]\displaystyle{ \aleph_0\cdot\aleph_0=|\mathbb{N}\times\mathbb{N}| }[/math]. נסדר את כל הזוגות בשורה לפי סכום הרכיבים: תחילה הזוג שסכומו 0, אחריו הזוגות שסכומם 1, אחריהם אלו שסכומם 2, וכן הלאה (לכל סכום יש מספר סופי של זוגות):

[math]\displaystyle{ (0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),\ldots }[/math]

כל זוג מופיע בדיוק פעם אחת (הפעם, בניגוד לרציונליים, אין צמצומים ואין על מה לדלג). לכן [math]\displaystyle{ \mathbb{N}\times\mathbb{N}\sim\mathbb{N} }[/math], כלומר

[math]\displaystyle{ \aleph_0\cdot\aleph_0=\aleph_0 }[/math]

(במפורש: הזוג [math]\displaystyle{ (m,n) }[/math] נמצא במקום [math]\displaystyle{ \frac{(m+n)(m+n+1)}{2}+n }[/math] בסדרה, כשהמקומות ממוספרים מ־0.)

▶ הפתרון בהרצאה מ־5.8.26, החל מהדקה 2:04:14

חזקת עוצמות

• תהיינה שתי עוצמות a,b ותהיינה שתי נציגות לעוצמות A,B.
• נגדיר את [math]\displaystyle{ A^B }[/math] להיות אוסף כל הפונקציות מB לA (מהמעריך לבסיס).
• נגדיר [math]\displaystyle{ a^b=|A^B| }[/math], הגדרה זו אינה תלוייה בבחירת הנציגות.

דוגמה: כמה פונקציות יש מ־[math]\displaystyle{ \{1,2,3,4,5\} }[/math] ל־[math]\displaystyle{ \{a,b,c\} }[/math]?

יש 3 אפשרויות לאן לשלוח את 1, ועל כל בחירה כזו יש 3 אפשרויות לאן לשלוח את 2, וכך הלאה. בסך הכל

[math]\displaystyle{ 3\cdot 3\cdot 3\cdot 3\cdot 3=3^5=243 }[/math]

פונקציות שונות (הוכחה מדויקת: באינדוקציה). זו הסיבה שבהגדרת [math]\displaystyle{ a^b=|A^B| }[/math] הקבוצה [math]\displaystyle{ A^B }[/math] היא אוסף הפונקציות מהמעריך לבסיס.

▶ הפתרון בהרצאה מ־5.8.26, החל מהדקה 2:07:53

דוגמה: חשבו את [math]\displaystyle{ 0^0 }[/math], את [math]\displaystyle{ 0^a }[/math] עבור עוצמה [math]\displaystyle{ a\neq 0 }[/math], ואת [math]\displaystyle{ a^0 }[/math] לכל עוצמה a.

• [math]\displaystyle{ 0^0=|\emptyset^{\emptyset}| }[/math] היא כמות הפונקציות מהקבוצה הריקה אל הקבוצה הריקה. יש בדיוק פונקציה אחת כזו, הפונקציה הריקה, ולכן [math]\displaystyle{ 0^0=1 }[/math].
• אם [math]\displaystyle{ a\neq 0 }[/math] ו־[math]\displaystyle{ |A|=a }[/math], אזי A אינה ריקה, ואין אף פונקציה מA אל הקבוצה הריקה (אין לאן לשלוח את איברי A). לכן [math]\displaystyle{ 0^a=0 }[/math].
• לכל קבוצה A, הפונקציה הריקה היא הפונקציה היחידה מהקבוצה הריקה לA. לכן [math]\displaystyle{ a^0=1 }[/math].

▶ הפתרון בהרצאה מ־5.8.26, החל מהדקה 2:13:39

• חוקי חזקות
• תהיינה עוצמות a,b,c אזי
  • [math]\displaystyle{ a^b\cdot a^c = a^{b+c} }[/math]
  • [math]\displaystyle{ (a^b)^c = a^{b\cdot c} }[/math]

הוכחה. נבחר נציגות A,B,C לעוצמות a,b,c. לפי ההגדרות [math]\displaystyle{ (a^b)^c=|(A^B)^C| }[/math] ו־[math]\displaystyle{ a^{b\cdot c}=|A^{B\times C}| }[/math], ולכן צריך להוכיח

[math]\displaystyle{ (A^B)^C\sim A^{B\times C} }[/math]

נבנה פונקציה הפיכה [math]\displaystyle{ h:(A^B)^C\to A^{B\times C} }[/math]. תהי [math]\displaystyle{ f:C\to A^B }[/math] (כלומר לכל [math]\displaystyle{ y\in C }[/math], [math]\displaystyle{ f(y) }[/math] היא פונקציה מB לA). נגדיר [math]\displaystyle{ h(f):B\times C\to A }[/math] ע"י

[math]\displaystyle{ h(f)(x,y)=f(y)(x) }[/math]

h חח"ע: תהיינה [math]\displaystyle{ f_1,f_2:C\to A^B }[/math] כך ש־[math]\displaystyle{ h(f_1)=h(f_2) }[/math]; צריך להוכיח [math]\displaystyle{ f_1=f_2 }[/math]. יהי [math]\displaystyle{ y\in C }[/math]; צריך להוכיח [math]\displaystyle{ f_1(y)=f_2(y) }[/math], ושתיהן פונקציות מB לA. יהי [math]\displaystyle{ x\in B }[/math], אזי

[math]\displaystyle{ f_1(y)(x)=h(f_1)(x,y)=h(f_2)(x,y)=f_2(y)(x) }[/math]

ולכן [math]\displaystyle{ f_1(y)=f_2(y) }[/math] לכל [math]\displaystyle{ y\in C }[/math], כלומר [math]\displaystyle{ f_1=f_2 }[/math].

h על: תהי [math]\displaystyle{ g:B\times C\to A }[/math]; צריך למצוא [math]\displaystyle{ f:C\to A^B }[/math] כך ש־[math]\displaystyle{ h(f)=g }[/math]. לכל [math]\displaystyle{ y\in C }[/math] נבחר את [math]\displaystyle{ f(y):B\to A }[/math] להיות הפונקציה

[math]\displaystyle{ f(y)(x)=g(x,y) }[/math]

ואכן [math]\displaystyle{ h(f)(x,y)=f(y)(x)=g(x,y) }[/math] לכל [math]\displaystyle{ (x,y)\in B\times C }[/math], כלומר [math]\displaystyle{ h(f)=g }[/math].

▶ ההוכחה בהרצאה מ־5.8.26, החל מהדקה 2:44:09

• • [math]\displaystyle{ a^b\cdot c^b = (a\cdot c)^b }[/math]

הוכחה. נבחר נציגות A,B,C לעוצמות a,b,c. לפי ההגדרות [math]\displaystyle{ a^b\cdot c^b=|A^B\times C^B| }[/math] ו־[math]\displaystyle{ (a\cdot c)^b=|(A\times C)^B| }[/math], ולכן צריך להוכיח

[math]\displaystyle{ (A\times C)^B\sim A^B\times C^B }[/math]

נבנה פונקציה הפיכה [math]\displaystyle{ h:(A\times C)^B\to A^B\times C^B }[/math]. תהי [math]\displaystyle{ f:B\to A\times C }[/math]. נגדיר [math]\displaystyle{ h(f)=(l,r) }[/math], כאשר [math]\displaystyle{ l:B\to A }[/math] ו־[math]\displaystyle{ r:B\to C }[/math] הן "רכיבי" f: לכל [math]\displaystyle{ x\in B }[/math], אם [math]\displaystyle{ f(x)=(u,v) }[/math] אזי [math]\displaystyle{ l(x)=u }[/math] ו־[math]\displaystyle{ r(x)=v }[/math].

h חח"ע: תהיינה [math]\displaystyle{ f_1\neq f_2 }[/math], ונסמן [math]\displaystyle{ h(f_1)=(l_1,r_1) }[/math], [math]\displaystyle{ h(f_2)=(l_2,r_2) }[/math]. קיים [math]\displaystyle{ x\in B }[/math] כך ש־[math]\displaystyle{ f_1(x)\neq f_2(x) }[/math], כלומר אחד מרכיבי הזוג שונה; נניח שהראשון (המקרה השני דומה). אזי [math]\displaystyle{ l_1(x)\neq l_2(x) }[/math], ולכן [math]\displaystyle{ l_1\neq l_2 }[/math] ו־[math]\displaystyle{ h(f_1)\neq h(f_2) }[/math].

h על: יהי זוג פונקציות [math]\displaystyle{ (l,r)\in A^B\times C^B }[/math]. נגדיר [math]\displaystyle{ f:B\to A\times C }[/math] ע"י [math]\displaystyle{ f(x)=(l(x),r(x)) }[/math], ואכן [math]\displaystyle{ h(f)=(l,r) }[/math].

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

• [math]\displaystyle{ |P(A)|=2^{|A|} }[/math]

הוכחה. [math]\displaystyle{ 2^{|A|} }[/math] היא חזקת עוצמות, ולכן ניקח נציגה לעוצמה 2, למשל [math]\displaystyle{ \{0,1\} }[/math]. אזי [math]\displaystyle{ 2^{|A|}=|\{0,1\}^A| }[/math], וצריך להוכיח [math]\displaystyle{ P(A)\sim\{0,1\}^A }[/math].

לכל [math]\displaystyle{ X\subseteq A }[/math] נגדיר את פונקציית האינדיקטור [math]\displaystyle{ D_X:A\to\{0,1\} }[/math] ע"י

[math]\displaystyle{ D_X(a)=\begin{cases}1 & a\in X\\ 0 & a\notin X\end{cases} }[/math]

למשל [math]\displaystyle{ D_{\emptyset} }[/math] היא הפונקציה הקבועה 0, ו־[math]\displaystyle{ D_A }[/math] היא הפונקציה הקבועה 1.

נגדיר [math]\displaystyle{ f:P(A)\to\{0,1\}^A }[/math] ע"י [math]\displaystyle{ f(X)=D_X }[/math], כלומר נשלח כל תת־קבוצה לאינדיקטור שלה.

f חח"ע: תהיינה [math]\displaystyle{ X_1,X_2\subseteq A }[/math] כך ש־[math]\displaystyle{ f(X_1)=f(X_2) }[/math], כלומר [math]\displaystyle{ D_{X_1}=D_{X_2} }[/math]. יהי [math]\displaystyle{ a\in X_1 }[/math]; אזי [math]\displaystyle{ D_{X_1}(a)=1 }[/math], לכן [math]\displaystyle{ D_{X_2}(a)=1 }[/math], ולכן [math]\displaystyle{ a\in X_2 }[/math]. כלומר [math]\displaystyle{ X_1\subseteq X_2 }[/math], וההכלה בכיוון ההפוך דומה. לכן [math]\displaystyle{ X_1=X_2 }[/math].

f על: תהי [math]\displaystyle{ g:A\to\{0,1\} }[/math]; צריך למצוא [math]\displaystyle{ X\subseteq A }[/math] כך ש־[math]\displaystyle{ D_X=g }[/math]. נבחר [math]\displaystyle{ X=g^{-1}[\{1\}]=\{a\in A\mid g(a)=1\} }[/math]. לכל [math]\displaystyle{ a\in X }[/math] מתקיים [math]\displaystyle{ D_X(a)=1=g(a) }[/math], ולכל [math]\displaystyle{ a\notin X }[/math] מתקיים [math]\displaystyle{ g(a)\neq 1 }[/math], כלומר [math]\displaystyle{ g(a)=0=D_X(a) }[/math]. לכן [math]\displaystyle{ f(X)=D_X=g }[/math].

▶ ההוכחה בהרצאה מ־5.8.26, החל מהדקה 2:28:59

• בפרט [math]\displaystyle{ |P(\mathbb{N})|=2^{\aleph_0} }[/math].
• שימו לב: חשבון עושים בין עוצמות או בין קבוצות, ולא מערבבים. למשל הביטוי [math]\displaystyle{ \aleph^A }[/math] (עוצמה בחזקת קבוצה) חסר משמעות.

השוואת חשבון עוצמות

• עיקרון עזר: תהיינה עוצמות [math]\displaystyle{ a\leq b }[/math], אזי אפשר לבחור נציגות [math]\displaystyle{ A\subseteq B }[/math] (כלומר [math]\displaystyle{ |A|=a }[/math], [math]\displaystyle{ |B|=b }[/math]).
  • שימו לב: אין זה אומר שכל שתי נציגות מוכלות זו בזו. למשל [math]\displaystyle{ |\{1,2\}|\leq |\{x,y,z\}| }[/math], אך [math]\displaystyle{ \{1,2\}\not\subseteq\{x,y,z\} }[/math].

הוכחה. תהי B נציגה כלשהי של b, ותהי C נציגה כלשהי של a. אזי [math]\displaystyle{ |C|=a\leq b=|B| }[/math], ולכן קיימת [math]\displaystyle{ f:C\to B }[/math] חח"ע. לכן [math]\displaystyle{ f:C\to Im(f) }[/math] חח"ע ועל, כלומר [math]\displaystyle{ |Im(f)|=|C|=a }[/math].

נבחר [math]\displaystyle{ A=Im(f) }[/math]. אכן [math]\displaystyle{ |A|=a }[/math], וגם [math]\displaystyle{ A\subseteq B }[/math] (כי התמונה מוכלת בטווח).

▶ ההוכחה בהרצאה מ־5.8.26, החל מהדקה 3:05:36

• תהיינה עוצמות a,b,c,d כך ש [math]\displaystyle{ a\leq c }[/math] וכן [math]\displaystyle{ b\leq d }[/math] אזי:
  • [math]\displaystyle{ a+b\leq c+d }[/math]
  • [math]\displaystyle{ a\cdot b\leq c\cdot d }[/math]
• אם בנוסף נתון כי [math]\displaystyle{ c\neq 0 }[/math] אזי
  • [math]\displaystyle{ a^b\leq c^d }[/math]

הוכחה. נוכיח את אי־השוויון השלישי (שני הראשונים: תרגיל). נתון [math]\displaystyle{ a\leq c }[/math], [math]\displaystyle{ b\leq d }[/math] ו־[math]\displaystyle{ c\neq 0 }[/math]. לפי עיקרון העזר נבחר נציגות [math]\displaystyle{ A\subseteq C }[/math] ו־[math]\displaystyle{ B\subseteq D }[/math] (עם [math]\displaystyle{ |A|=a }[/math], [math]\displaystyle{ |B|=b }[/math], [math]\displaystyle{ |C|=c }[/math], [math]\displaystyle{ |D|=d }[/math]), ונבנה פונקציה חח"ע

[math]\displaystyle{ f:A^B\to C^D }[/math]

כיוון ש־[math]\displaystyle{ c\neq 0 }[/math], הקבוצה C אינה ריקה, ולכן קיים [math]\displaystyle{ x\in C }[/math]; נקבע אותו.

תהי [math]\displaystyle{ g:B\to A }[/math]. צריך להגדיר את [math]\displaystyle{ f(g):D\to C }[/math]. לכל [math]\displaystyle{ s\in D }[/math] נגדיר

[math]\displaystyle{ f(g)(s)=\begin{cases}g(s) & s\in B\\ x & s\notin B\end{cases} }[/math]

זה מוגדר היטב: אם [math]\displaystyle{ s\in B }[/math] אזי [math]\displaystyle{ g(s)\in A\subseteq C }[/math], ואחרת [math]\displaystyle{ x\in C }[/math]. זה בדיוק המקום שבו משתמשים בנתון [math]\displaystyle{ c\neq 0 }[/math]: אם C ריקה, אין לאן לשלוח את איברי [math]\displaystyle{ D\setminus B }[/math].

f חח"ע: תהיינה [math]\displaystyle{ g_1,g_2\in A^B }[/math] כך ש־[math]\displaystyle{ f(g_1)=f(g_2) }[/math]; צריך להוכיח [math]\displaystyle{ g_1=g_2 }[/math]. יהי [math]\displaystyle{ t\in B }[/math]. כיוון ש־[math]\displaystyle{ B\subseteq D }[/math], גם [math]\displaystyle{ t\in D }[/math], ולכן [math]\displaystyle{ f(g_1)(t)=f(g_2)(t) }[/math]. כיוון ש־[math]\displaystyle{ t\in B }[/math], לפי ההגדרה זה אומר [math]\displaystyle{ g_1(t)=g_2(t) }[/math], בדיוק כפי שרצינו.

▶ ההוכחה בהרצאה מ־5.8.26, החל מהדקה 3:11:18

• התנאי [math]\displaystyle{ c\neq 0 }[/math] הכרחי: עבור [math]\displaystyle{ a=b=c=0 }[/math] ו־[math]\displaystyle{ d=1 }[/math] מתקיים [math]\displaystyle{ a\leq c }[/math] וגם [math]\displaystyle{ b\leq d }[/math], אבל [math]\displaystyle{ a^b=0^0=1>0=0^1=c^d }[/math].

דוגמה: חשבו את [math]\displaystyle{ \aleph_0^{\aleph_0} }[/math], כלומר את עוצמת קבוצת כל הפונקציות מהטבעיים אל הטבעיים.

מצד אחד, לפי משפט קנטור [math]\displaystyle{ \aleph_0=|\mathbb{N}|<|P(\mathbb{N})|=2^{\aleph_0} }[/math]. לפי השוואת חשבון עוצמות (עם [math]\displaystyle{ 2\leq\aleph_0 }[/math], [math]\displaystyle{ \aleph_0\leq\aleph_0 }[/math] ו־[math]\displaystyle{ \aleph_0\neq 0 }[/math]):

[math]\displaystyle{ \aleph_0<2^{\aleph_0}\leq\aleph_0^{\aleph_0} }[/math]

מצד שני, שוב לפי השוואת חשבון עוצמות (הפעם עם [math]\displaystyle{ \aleph_0\leq 2^{\aleph_0} }[/math]), חוקי החזקות ו־[math]\displaystyle{ \aleph_0\cdot\aleph_0=\aleph_0 }[/math]:

[math]\displaystyle{ \aleph_0^{\aleph_0}\leq\left(2^{\aleph_0}\right)^{\aleph_0}=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0} }[/math]

לכן לפי משפט קנטור־שרדר־ברנשטיין (להלן):

[math]\displaystyle{ \aleph_0^{\aleph_0}=2^{\aleph_0} }[/math]

בפרט זו עוצמה גדולה ממש מ־[math]\displaystyle{ \aleph_0 }[/math].

▶ הפתרון בהרצאה מ־5.8.26, החל מהדקה 3:23:02

משפט קנטור-שרדר-ברנשטיין

• אם [math]\displaystyle{ |A|\leq |B| }[/math] וגם [math]\displaystyle{ |B|\leq |A| }[/math] אזי [math]\displaystyle{ A\sim B }[/math]

למת נקודת השבת

• תהי פונקציה עולה [math]\displaystyle{ h:P(A)\to P(A) }[/math] כלומר המקיימת לכל [math]\displaystyle{ X_1\subseteq X_2 }[/math] כי [math]\displaystyle{ h(X_1)\subseteq h(X_2) }[/math]
• אזי קיימת נק' שבת [math]\displaystyle{ K\subseteq A }[/math] כך ש [math]\displaystyle{ h(K)=K }[/math].

הוכחה. נגדיר את [math]\displaystyle{ K }[/math] להיות האיחוד של כל תתי הקבוצות של [math]\displaystyle{ A }[/math] המוכלות בתמונה של עצמן:

[math]\displaystyle{ K=\bigcup\left\{X\subseteq A\mid X\subseteq h(X)\right\} }[/math]

נוכיח כי [math]\displaystyle{ h(K)=K }[/math] בהכלה דו כיוונית.

• [math]\displaystyle{ K\subseteq h(K) }[/math]: יהי [math]\displaystyle{ a\in K }[/math]. לכן קיימת [math]\displaystyle{ X\subseteq A }[/math] המקיימת [math]\displaystyle{ X\subseteq h(X) }[/math] כך ש [math]\displaystyle{ a\in X }[/math]. כמו כן [math]\displaystyle{ X\subseteq K }[/math] (כל קבוצה מוכלת באיחוד כולו), וכיוון ש [math]\displaystyle{ h }[/math] עולה נובע כי [math]\displaystyle{ h(X)\subseteq h(K) }[/math]. סה"כ

[math]\displaystyle{ a\in X\subseteq h(X)\subseteq h(K) }[/math]

• [math]\displaystyle{ h(K)\subseteq K }[/math]: בכיוון הקודם הוכחנו כי [math]\displaystyle{ K\subseteq h(K) }[/math], ולכן כיוון ש [math]\displaystyle{ h }[/math] עולה נובע כי

[math]\displaystyle{ h(K)\subseteq h(h(K)) }[/math]

כלומר הקבוצה [math]\displaystyle{ h(K) }[/math] מוכלת בתמונה של עצמה, ולכן היא אחת הקבוצות באיחוד המגדיר את [math]\displaystyle{ K }[/math]. לכן [math]\displaystyle{ h(K)\subseteq K }[/math].

▶ ההוכחה בהרצאה מ־10.8.26, החל מהדקה 46:22

• הערה: הטענה המקבילה עבור פונקציות ממשיות עולות אינה נכונה. למשל הפונקציה [math]\displaystyle{ f:\mathbb{R}\to\mathbb{R} }[/math] המוגדרת ע"י [math]\displaystyle{ f(x)=x+1 }[/math] עולה, אך לכל [math]\displaystyle{ x\in\mathbb{R} }[/math] מתקיים [math]\displaystyle{ f(x)\neq x }[/math].

הוכחת המשפט

הוכחה. נתון שקיימות פונקציות חח"ע [math]\displaystyle{ f:A\to B }[/math] וכן [math]\displaystyle{ g:B\to A }[/math].

הרעיון: נניח שמצאנו קבוצה [math]\displaystyle{ K\subseteq A }[/math] עבורה

[math]\displaystyle{ g[B\setminus f[K]]=A\setminus K }[/math]

אזי [math]\displaystyle{ f }[/math] מתאימה באופן חח"ע ועל בין [math]\displaystyle{ K }[/math] לבין [math]\displaystyle{ f[K] }[/math], ו-[math]\displaystyle{ g }[/math] מתאימה באופן חח"ע ועל בין [math]\displaystyle{ B\setminus f[K] }[/math] לבין [math]\displaystyle{ A\setminus K }[/math]. כיוון שמדובר באיחודים זרים, נקבל

[math]\displaystyle{ |A|=|K|+|A\setminus K| }[/math]

[math]\displaystyle{ =|f[K]|+|B\setminus f[K]|=|B| }[/math]

(במפורש: הפונקציה השולחת כל [math]\displaystyle{ x\in K }[/math] אל [math]\displaystyle{ f(x) }[/math], וכל [math]\displaystyle{ x\in A\setminus K }[/math] אל המקור היחיד שלו לפי [math]\displaystyle{ g }[/math], היא פונקציה הפיכה מ-[math]\displaystyle{ A }[/math] ל-[math]\displaystyle{ B }[/math].)

מציאת K: נעשה משלים ב-[math]\displaystyle{ A }[/math] לשני הצדדים; מספיק להוכיח שקיימת [math]\displaystyle{ K\subseteq A }[/math] עבורה

[math]\displaystyle{ K=A\setminus g[B\setminus f[K]] }[/math]

נביט בפונקציה [math]\displaystyle{ h:P(A)\to P(A) }[/math] המוגדרת ע"י

[math]\displaystyle{ h(X)=A\setminus g[B\setminus f[X]] }[/math]

אם [math]\displaystyle{ h }[/math] עולה, אזי לפי למת נקודת השבת קיימת [math]\displaystyle{ K }[/math] כך ש [math]\displaystyle{ h(K)=K }[/math], וזו בדיוק הקבוצה הדרושה.

נותר להוכיח ש-[math]\displaystyle{ h }[/math] עולה. אכן, יהיו [math]\displaystyle{ X_1\subseteq X_2\subseteq A }[/math], אזי

[math]\displaystyle{ f[X_1]\subseteq f[X_2] }[/math]

[math]\displaystyle{ B\setminus f[X_1]\supseteq B\setminus f[X_2] }[/math]

[math]\displaystyle{ g[B\setminus f[X_1]]\supseteq g[B\setminus f[X_2]] }[/math]

[math]\displaystyle{ A\setminus g[B\setminus f[X_1]]\subseteq A\setminus g[B\setminus f[X_2]] }[/math]

כלומר [math]\displaystyle{ h(X_1)\subseteq h(X_2) }[/math], כפי שרצינו. ▶ ההוכחה בהרצאה מ־10.8.26, החל מהדקה 17:53

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

• [math]\displaystyle{ |\mathbb{R}|=|[a,\infty)|=|[a,b]|=|(a,b)|=\aleph }[/math] (עבור [math]\displaystyle{ a<b }[/math])

הוכחה. יהיו [math]\displaystyle{ a<b }[/math]. כיוון ש

[math]\displaystyle{ (a,b)\subseteq [a,b]\subseteq [a,\infty)\subseteq\mathbb{R} }[/math]

ופונקציית ההכלה חח"ע, מתקיים

[math]\displaystyle{ |(a,b)|\leq|[a,b]|\leq|[a,\infty)|\leq|\mathbb{R}| }[/math]

מצד שני, הפונקציה [math]\displaystyle{ \tan:\left(-\frac{\pi}{2},\frac{\pi}{2}\right)\to\mathbb{R} }[/math] הפיכה (ההופכית שלה היא [math]\displaystyle{ \arctan }[/math]), והפונקציה הלינארית

[math]\displaystyle{ \varphi(x)=a+\frac{b-a}{\pi}\left(x+\frac{\pi}{2}\right) }[/math]

היא פונקציה הפיכה מהקטע [math]\displaystyle{ \left(-\frac{\pi}{2},\frac{\pi}{2}\right) }[/math] אל הקטע [math]\displaystyle{ (a,b) }[/math]. לכן

[math]\displaystyle{ |\mathbb{R}|=\left|\left(-\frac{\pi}{2},\frac{\pi}{2}\right)\right|=|(a,b)| }[/math]

ביחד:

[math]\displaystyle{ |\mathbb{R}|=|(a,b)|\leq|[a,b]|\leq|[a,\infty)|\leq|\mathbb{R}| }[/math]

ולפי משפט ק.ש.ב כל העוצמות בשרשרת שוות ל-[math]\displaystyle{ |\mathbb{R}|=\aleph }[/math]. באותו אופן מוכיחים שגם לקטעים מהצורה [math]\displaystyle{ [a,b),(a,b],(a,\infty),(-\infty,a] }[/math] יש עוצמה [math]\displaystyle{ \aleph }[/math].

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

אקסיומת הבחירה

• תהי S קבוצת קבוצות לא ריקות, ונסמן את האיחוד הכללי ב [math]\displaystyle{ U=\cup_{X\in S}X }[/math].
• אזי קיימת פונקצית בחירה [math]\displaystyle{ f:S\to U }[/math] הבוחרת איבר מתוך כל קבוצה, כלומר:
  • [math]\displaystyle{ \forall X\in S: f(X)\in X }[/math]

• הערות:
  • כאשר יש כלל מפורש לבחירה, אין צורך באקסיומה. למשל אם כל קבוצה ב-S היא זוג של מספרים טבעיים, אפשר לבחור את הקטן מבין השניים (כמו לבחור מכל זוג נעליים את הנעל השמאלית). אבל אם S היא קבוצה של זוגות של איברים מקבוצה כלשהי, אין לנו דרך לבנות פונקציה הבוחרת איבר מכל זוג (כמו בזוגות גרביים). אקסיומת הבחירה מבטיחה שפונקציה כזו קיימת, גם אם איננו יודעים לבנות אותה.
  • לא ניתן להוכיח או להפריך את אקסיומת הבחירה מיתר האקסיומות של המתמטיקה; פשוט מניחים שהיא נכונה.
  • השערת הרצף שואלת האם קיימת קבוצה A כך ש [math]\displaystyle{ \aleph_0<|A|<\aleph }[/math]. הוכח שגם טענה זו בלתי תלויה ביתר האקסיומות של המתמטיקה (כולל אקסיומת הבחירה).

• דוגמא:
  • תהי פונקציה על [math]\displaystyle{ f:A\to B }[/math] אזי קיימת תת קבוצה [math]\displaystyle{ X\subseteq A }[/math] כך ש [math]\displaystyle{ f:X\to B }[/math] חח"ע ועל.

הוכחה. כיוון ש-[math]\displaystyle{ f }[/math] על, לכל [math]\displaystyle{ b\in B }[/math] הקבוצה [math]\displaystyle{ f^{-1}[\{b\}] }[/math] אינה ריקה. לפי אקסיומת הבחירה קיימת פונקצית בחירה [math]\displaystyle{ c }[/math] על האוסף [math]\displaystyle{ \left\{f^{-1}[\{b\}]\mid b\in B\right\} }[/math]. נסמן [math]\displaystyle{ x_b=c(f^{-1}[\{b\}]) }[/math]; זהו המקור של [math]\displaystyle{ b }[/math] שבחרנו, כלומר [math]\displaystyle{ x_b\in A }[/math] וכן [math]\displaystyle{ f(x_b)=b }[/math].

נגדיר [math]\displaystyle{ X=\{x_b\mid b\in B\}\subseteq A }[/math], ונביט בצמצום של [math]\displaystyle{ f }[/math] לתחום [math]\displaystyle{ X }[/math], כלומר [math]\displaystyle{ f_{|X}=f\cap(X\times B) }[/math] (משאירים רק את הזוגות שהאיבר השמאלי בהם שייך ל-[math]\displaystyle{ X }[/math]).

• על: לכל [math]\displaystyle{ b\in B }[/math] מתקיים [math]\displaystyle{ x_b\in X }[/math] וכן [math]\displaystyle{ f(x_b)=b }[/math].
• חח"ע: יהיו [math]\displaystyle{ x,x'\in X }[/math] כך ש [math]\displaystyle{ f(x)=f(x')=b }[/math]. לפי הגדרת [math]\displaystyle{ X }[/math] קיים [math]\displaystyle{ b_1\in B }[/math] כך ש [math]\displaystyle{ x=x_{b_1} }[/math], ואז [math]\displaystyle{ b_1=f(x_{b_1})=f(x)=b }[/math], כלומר [math]\displaystyle{ x=x_b }[/math]. באותו אופן [math]\displaystyle{ x'=x_b }[/math], ולכן [math]\displaystyle{ x=x' }[/math].

▶ ההוכחה בהרצאה מ־10.8.26, החל מהדקה 2:29:05

• תהיינה [math]\displaystyle{ A,B\neq\emptyset }[/math] אזי [math]\displaystyle{ |A|\leq |B| }[/math] אם ורק אם קיימת [math]\displaystyle{ g:B\to A }[/math] על.

• בכיוון ראשון:
  • תהי [math]\displaystyle{ f:A\to B }[/math] חח"ע
  • כיוון ש[math]\displaystyle{ A\neq \emptyset }[/math] קיים [math]\displaystyle{ a\in A }[/math]
  • נגדיר פונקציה [math]\displaystyle{ g:B\to A }[/math] באופן הבא:
    • לכל [math]\displaystyle{ b\in B }[/math]
    • אם קיים [math]\displaystyle{ x\in A }[/math] כך ש [math]\displaystyle{ f(x)=b }[/math] נגדיר [math]\displaystyle{ g(b)=x }[/math] (בגלל החח"ע זה מוגדר היטב)
    • אם [math]\displaystyle{ b\not\in Im(f) }[/math] נגדיר [math]\displaystyle{ g(b)=a }[/math]
  • הפונקציה [math]\displaystyle{ g }[/math] שהגדרנו היא אכן על, כי לכל [math]\displaystyle{ x\in A }[/math] מתקיים כי [math]\displaystyle{ g(f(x))=x }[/math]
• בכיוון שני:
  • תהי [math]\displaystyle{ g:B\to A }[/math] על, אזי כל הקבוצות באוסף [math]\displaystyle{ U=\left\{g^{-1}[\{a\}]|a\in A\right\} }[/math] אינן ריקות.
  • ניקח פונקצית בחירה [math]\displaystyle{ h:U\to B }[/math] ונגדיר [math]\displaystyle{ f:A\to B }[/math] ע"י [math]\displaystyle{ f(a)=h(g^{-1}[\{a\}]) }[/math]
  • אכן [math]\displaystyle{ f }[/math] חח"ע כי אם [math]\displaystyle{ f(a_1)=f(a_2)=b }[/math] אזי [math]\displaystyle{ b\in g^{-1}[\{a_1\}] }[/math] וכן [math]\displaystyle{ b\in g^{-1}[\{a_2\}] }[/math]
  • ולכן [math]\displaystyle{ g(b)=a_1 }[/math] וכן [math]\displaystyle{ g(b)=a_2 }[/math], כלומר [math]\displaystyle{ a_1=a_2 }[/math]

דוגמה: האם הטענה שלעיל ([math]\displaystyle{ |A|\leq |B| }[/math] אם ורק אם קיימת [math]\displaystyle{ g:B\to A }[/math] על) נכונה גם ללא ההנחה שהקבוצות אינן ריקות?

לא. למשל [math]\displaystyle{ |\emptyset|\leq|\{1\}| }[/math] (הפונקציה הריקה מ-[math]\displaystyle{ \emptyset }[/math] ל-[math]\displaystyle{ \{1\} }[/math] היא חח"ע), אבל לא קיימת אף פונקציה [math]\displaystyle{ g:\{1\}\to\emptyset }[/math], כי אין לאן לשלוח את האיבר 1; בפרט לא קיימת פונקציה על כזו.

בהוכחה שלעיל משתמשים בכך ש-[math]\displaystyle{ A\neq\emptyset }[/math] בכיוון הראשון, כדי שיהיה לאן לשלוח את איברי [math]\displaystyle{ B }[/math] שאינם בתמונה של [math]\displaystyle{ f }[/math]. שימו לב גם שבכיוון הראשון אין צורך באקסיומת הבחירה (לכל איבר בתמונה יש מקור יחיד, ובוחרים איבר אחד בלבד מ-[math]\displaystyle{ A }[/math]), ואילו בכיוון השני בוחרים בבת אחת מקור לכל איבר של [math]\displaystyle{ A }[/math], ולשם כך דרושה אקסיומת הבחירה. ▶ הפתרון בהרצאה מ־10.8.26, החל מהדקה 2:08:59

דוגמה: הוכיחו כי [math]\displaystyle{ |\mathbb{Q}|=\aleph_0 }[/math].

מצד אחד [math]\displaystyle{ \mathbb{N}\subseteq\mathbb{Q} }[/math] ולכן [math]\displaystyle{ \aleph_0\leq|\mathbb{Q}| }[/math].

מצד שני, נביט בפונקציה [math]\displaystyle{ f:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Q} }[/math] המוגדרת ע"י

[math]\displaystyle{ f(p,q)=\begin{cases}\frac{p}{q} & q\neq 0\\ 0 & q=0\end{cases} }[/math]

זו פונקציה על, כי כל מספר רציונלי הוא מנה [math]\displaystyle{ \frac{p}{q} }[/math] של שלמים עם [math]\displaystyle{ q\neq 0 }[/math]. לפי הטענה לעיל (הקבוצות אינן ריקות) נובע כי [math]\displaystyle{ |\mathbb{Q}|\leq|\mathbb{Z}\times\mathbb{Z}| }[/math]. לכן

[math]\displaystyle{ \aleph_0\leq|\mathbb{Q}|\leq|\mathbb{Z}\times\mathbb{Z}|=\aleph_0\cdot\aleph_0=\aleph_0 }[/math]

ולפי משפט ק.ש.ב [math]\displaystyle{ |\mathbb{Q}|=\aleph_0 }[/math]. ▶ הפתרון בהרצאה מ־10.8.26, החל מהדקה 1:13:05

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

• תהי קבוצה A עם יחס סדר חלקי, תת קבוצה [math]\displaystyle{ S\subseteq A }[/math] נקראת שרשרת אם היחס מלא עליה (ניתן להשוות בין כל שני איברים בS).
• שרשרת נקראת מקסימלית בA אם היא אינה מוכלת באף שרשרת אחרת.
• עקרון המקסימום של האוסדורף אומר שכל שרשרת מוכלת בשרשרת מקסימלית.

• ניסוח שקול: בכל קבוצה סדורה חלקית קיימת שרשרת מקסימלית.

דוגמה: נביט ביחס "מחלק את" על הטבעיים (כולל 0). האם השרשרת [math]\displaystyle{ \{2,4,8\} }[/math] מקסימלית? האם השרשרת [math]\displaystyle{ \{2^n\mid n\in\mathbb{N}\} }[/math] מקסימלית?

• [math]\displaystyle{ \{2,4,8\} }[/math] אינה מקסימלית, כי היא מוכלת ממש בשרשרת [math]\displaystyle{ \{2,4,8,16\} }[/math].
• גם [math]\displaystyle{ \{2^n\mid n\in\mathbb{N}\} }[/math] אינה מקסימלית: כל מספר מחלק את 0 (כי [math]\displaystyle{ 0=0\cdot x }[/math]), ולכן [math]\displaystyle{ C=\{2^n\mid n\in\mathbb{N}\}\cup\{0\} }[/math] היא שרשרת המכילה אותה ממש.
• השרשרת [math]\displaystyle{ C }[/math] כבר מקסימלית: יהי [math]\displaystyle{ x\in\mathbb{N} }[/math] הניתן להשוואה עם כל איברי [math]\displaystyle{ C }[/math]. אם [math]\displaystyle{ x }[/math] מחלק חזקה כלשהי [math]\displaystyle{ 2^n }[/math], אזי [math]\displaystyle{ x }[/math] עצמו חזקה של 2 ולכן [math]\displaystyle{ x\in C }[/math]. אחרת, כל החזקות [math]\displaystyle{ 2^n }[/math] מחלקות את [math]\displaystyle{ x }[/math]; אם [math]\displaystyle{ x\neq 0 }[/math] אז בפרט [math]\displaystyle{ 2^x }[/math] מחלק את [math]\displaystyle{ x }[/math], אבל [math]\displaystyle{ 0<x<2^x }[/math], סתירה. לכן [math]\displaystyle{ x=0\in C }[/math]. כלומר כל שרשרת המכילה את [math]\displaystyle{ C }[/math] שווה לה.

כאן ראינו בנייה מפורשת של שרשרת מקסימלית. לרוב לא נדע לבנות שרשרת כזו במפורש, ועקרון המקסימום של האוסדורף מבטיח שהיא קיימת. ▶ הפתרון בהרצאה מ־12.8.26, החל מהדקה 17:36

• תבנית פתרון לשאלות רבות בעזרת עקרון המקסימום:

1. נותנים שם (מצחיק) לאיברים המקיימים את התכונה הבסיסית של השאלה.
2. לפי עקרון המקסימום של האוסדורף קיימת שרשרת מקסימלית (לרוב ביחס ההכלה) של איברים המקיימים את התכונה.
3. מסתכלים על החסם העליון של השרשרת (לרוב האיחוד שלה), ומראים שגם הוא מקיים את התכונה.
4. מראים שהחסם העליון הוא האיבר שעונה על השאלה (לרוב בעזרת המקסימליות של השרשרת).

דוגמה (בה התבנית נכשלת): קבוצה נקראת "שניצלון" אם יש בה מספר סופי של איברים. האם קיים שניצלון מקסימלי ביחס ההכלה מבין תתי הקבוצות של [math]\displaystyle{ \mathbb{N} }[/math]?

לא. לכל תת קבוצה סופית [math]\displaystyle{ X\subseteq\mathbb{N} }[/math] קיים [math]\displaystyle{ n\in\mathbb{N}\setminus X }[/math], והקבוצה [math]\displaystyle{ X\cup\{n\} }[/math] היא שניצלון המכיל את [math]\displaystyle{ X }[/math] ממש.

לכן התבנית חייבת להיכשל כאן, והיא נכשלת בשלב 3: האיחוד של שרשרת שניצלונים אינו בהכרח שניצלון. למשל עבור השרשרת

[math]\displaystyle{ C=\left\{\emptyset,\{1\},\{1,2\},\{1,2,3\},\ldots\right\} }[/math]

מתקיים [math]\displaystyle{ \bigcup C=\mathbb{N}\setminus\{0\} }[/math], שאינה קבוצה סופית. ▶ הפתרון בהרצאה מ־12.8.26, החל מהדקה 28:40

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

הוכחה (שאוסף כזה קיים). נאמר שקבוצה של עיגולים מלאים במישור בעלי רדיוס חיובי היא שומרת נגיעה אם החיתוך בין כל שני עיגולים שונים בה ריק. נביט באוסף כל הקבוצות שומרות הנגיעה, הסדור ביחס ההכלה. לפי עקרון המקסימום של האוסדורף קיימת בו שרשרת מקסימלית [math]\displaystyle{ C }[/math] (למשל שרשרת מקסימלית המכילה את השרשרת [math]\displaystyle{ \{\emptyset\} }[/math]). איברי [math]\displaystyle{ C }[/math] הם קבוצות של עיגולים; נסמן את האיחוד הכללי שלהם

[math]\displaystyle{ U=\bigcup_{S\in C}S }[/math]

זו קבוצה של עיגולים.

• [math]\displaystyle{ U }[/math] שומרת נגיעה: יהיו [math]\displaystyle{ X_1\neq X_2\in U }[/math] שני עיגולים. קיימות [math]\displaystyle{ S_1,S_2\in C }[/math] כך ש [math]\displaystyle{ X_1\in S_1 }[/math] וכן [math]\displaystyle{ X_2\in S_2 }[/math]. כיוון ש-[math]\displaystyle{ C }[/math] שרשרת, [math]\displaystyle{ S_1\subseteq S_2 }[/math] (או ההפך), ולכן [math]\displaystyle{ X_1,X_2\in S_2 }[/math]. כיוון ש-[math]\displaystyle{ S_2 }[/math] שומרת נגיעה, נובע כי [math]\displaystyle{ X_1\cap X_2=\emptyset }[/math].
• [math]\displaystyle{ U }[/math] שומרת נגיעה מקסימלית: נב"ש שקיימת קבוצה שומרת נגיעה [math]\displaystyle{ D }[/math] כך ש [math]\displaystyle{ U\subseteq D }[/math] וגם [math]\displaystyle{ U\neq D }[/math]. נביט ב-[math]\displaystyle{ C'=C\cup\{D\} }[/math].
  • [math]\displaystyle{ C' }[/math] שרשרת, כי לכל [math]\displaystyle{ S\in C }[/math] מתקיים [math]\displaystyle{ S\subseteq U\subseteq D }[/math].
  • [math]\displaystyle{ C'\neq C }[/math], כי אחרת [math]\displaystyle{ D\in C }[/math] ולכן [math]\displaystyle{ D\subseteq U }[/math], כלומר [math]\displaystyle{ U=D }[/math], בסתירה.
  • לכן [math]\displaystyle{ C' }[/math] שרשרת המכילה ממש את [math]\displaystyle{ C }[/math], בסתירה למקסימליות של [math]\displaystyle{ C }[/math].
• לכן לא ניתן להוסיף ל-[math]\displaystyle{ U }[/math] אף עיגול: אם עיגול [math]\displaystyle{ Y\notin U }[/math] היה זר לכל העיגולים ב-[math]\displaystyle{ U }[/math], אזי [math]\displaystyle{ U\cup\{Y\} }[/math] הייתה שומרת נגיעה ומכילה ממש את [math]\displaystyle{ U }[/math].

▶ ההוכחה בהרצאה מ־12.8.26, החל מהדקה 38:02

דוגמה: הוכיחו שכל אוסף של עיגולים מלאים במישור (בעלי רדיוס חיובי) שאינם חותכים זה את זה הוא בן מנייה.

בתוך כל עיגול יש נקודה ששתי הקואורדינטות שלה רציונליות: על הקוטר של העיגול המקביל לציר ה-x יש נקודה פנימית שקואורדינטת ה-x שלה רציונלית (בין כל שני מספרים ממשיים יש מספר רציונלי). המיתר המקביל לציר ה-y העובר דרך נקודה זו הוא קטע באורך חיובי, ולכן יש עליו נקודה שגם קואורדינטת ה-y שלה רציונלית.

נתאים לכל עיגול באוסף נקודה כזו מתוך [math]\displaystyle{ \mathbb{Q}\times\mathbb{Q} }[/math] (אפשר אף בלי אקסיומת הבחירה: נמספר את [math]\displaystyle{ \mathbb{Q}\times\mathbb{Q} }[/math] ונבחר את הנקודה הראשונה במספור הנמצאת בעיגול). כיוון שהעיגולים זרים, לעיגולים שונים מתאימות נקודות שונות, כלומר זו פונקציה חח"ע מהאוסף אל [math]\displaystyle{ \mathbb{Q}\times\mathbb{Q} }[/math]. לכן עוצמת האוסף קטנה או שווה ל-

[math]\displaystyle{ |\mathbb{Q}\times\mathbb{Q}|=\aleph_0\cdot\aleph_0=\aleph_0 }[/math]

בפרט, האוסף המקסימלי מהדוגמה לעיל הוא בן מנייה. ▶ הפתרון בהרצאה מ־10.8.26, החל מהדקה 3:21:31

• טענות שימושיות להמשך:
• תהי [math]\displaystyle{ U }[/math] קבוצה של יחסים מ[math]\displaystyle{ A }[/math] ל [math]\displaystyle{ B }[/math], תהי [math]\displaystyle{ M\subseteq U }[/math] שרשרת ביחס ההכלה ונסמן את האיחוד הכללי של השרשרת ב[math]\displaystyle{ f=\cup_{R\in M} R }[/math]
• אזי:
  • אם כל היחסים ב[math]\displaystyle{ M }[/math] ח"ע, אז גם [math]\displaystyle{ f }[/math] ח"ע
    • אכן, יהיו [math]\displaystyle{ (a,b_1),(a,b_2)\in f }[/math]
    • לכן קיימים [math]\displaystyle{ R_1,R_2\in M }[/math] כך ש [math]\displaystyle{ (a,b_1)\in R_1 }[/math] וכן [math]\displaystyle{ (a,b_2)\in R_2 }[/math]
    • כיוון ש[math]\displaystyle{ M }[/math] שרשרת, אזי [math]\displaystyle{ R_1\subseteq R_2 }[/math] (או ההפך) ולכן [math]\displaystyle{ (a,b_1),(a,b_2)\in R_2 }[/math]
    • כיוון ש[math]\displaystyle{ R_2 }[/math] ח"ע נובע כי [math]\displaystyle{ b_1=b_2 }[/math] כפי שרצינו.
  • אם כל היחסים ב[math]\displaystyle{ M }[/math] חח"ע, אזי גם [math]\displaystyle{ f }[/math] חח"ע
    • הוכחה דומה לח"ע

הוכחה. יהיו [math]\displaystyle{ (a_1,b),(a_2,b)\in f }[/math]. לכן קיימים [math]\displaystyle{ R_1,R_2\in M }[/math] כך ש [math]\displaystyle{ (a_1,b)\in R_1 }[/math] וכן [math]\displaystyle{ (a_2,b)\in R_2 }[/math]. כיוון ש-[math]\displaystyle{ M }[/math] שרשרת, [math]\displaystyle{ R_1\subseteq R_2 }[/math] (או ההפך) ולכן [math]\displaystyle{ (a_1,b),(a_2,b)\in R_2 }[/math]. כיוון ש-[math]\displaystyle{ R_2 }[/math] חח"ע נובע כי [math]\displaystyle{ a_1=a_2 }[/math], כפי שרצינו. ▶ ההוכחה בהרצאה מ־12.8.26, החל מהדקה 1:21:55

איחוד בן מנייה של קבוצות בנות מנייה

(בהנחת אקסיומת הבחירה)

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

הוכחה. נסמן [math]\displaystyle{ U=\cup_{X\in S}X }[/math]. לאורך ההוכחה כדאי לחשוב על אנלוגיה: כל [math]\displaystyle{ X\in S }[/math] הוא אוטובוס, ואיבריו הם הנוסעים בו (אדם יכול לנסוע בכמה אוטובוסים). [math]\displaystyle{ U }[/math] היא קבוצת כל הנוסעים מכל האוטובוסים.

• כיוון ש-[math]\displaystyle{ S }[/math] בת מנייה, קיימת פונקציה חח"ע [math]\displaystyle{ f:S\to\mathbb{N} }[/math] (מספר הקו של כל אוטובוס).
• לכל [math]\displaystyle{ X\in S }[/math] קיימות פונקציות חח"ע מ-[math]\displaystyle{ X }[/math] ל-[math]\displaystyle{ \mathbb{N} }[/math]. נבחר לכל [math]\displaystyle{ X\in S }[/math] פונקציה כזו [math]\displaystyle{ g_X:X\to\mathbb{N} }[/math] (מספר המושב של כל נוסע באוטובוס). כאן השתמשנו באקסיומת הבחירה, כי בחרנו בבת אחת פונקציה לכל אחת מהקבוצות.
• לכל [math]\displaystyle{ x\in U }[/math] נסמן ב-[math]\displaystyle{ X_x }[/math] את הקבוצה ב-[math]\displaystyle{ S }[/math] המכילה את [math]\displaystyle{ x }[/math] שעבורה [math]\displaystyle{ f(X_x) }[/math] מינימלי (האוטובוס בעל מספר הקו הקטן ביותר מבין האוטובוסים שבהם [math]\displaystyle{ x }[/math] נוסע). קבוצה כזו קיימת כי לכל תת קבוצה לא ריקה של הטבעיים יש מינימום, והיא יחידה כי [math]\displaystyle{ f }[/math] חח"ע.
• נגדיר [math]\displaystyle{ h:U\to\mathbb{N}\times\mathbb{N} }[/math] ע"י (מספר הקו, מספר המושב):

[math]\displaystyle{ h(x)=\left(f(X_x),g_{X_x}(x)\right) }[/math]

• [math]\displaystyle{ h }[/math] חח"ע: יהיו [math]\displaystyle{ x_1,x_2\in U }[/math] כך ש [math]\displaystyle{ h(x_1)=h(x_2) }[/math]. אז [math]\displaystyle{ f(X_{x_1})=f(X_{x_2}) }[/math], וכיוון ש-[math]\displaystyle{ f }[/math] חח"ע נובע [math]\displaystyle{ X_{x_1}=X_{x_2} }[/math]; נסמן קבוצה זו ב-[math]\displaystyle{ X }[/math]. כעת [math]\displaystyle{ g_X(x_1)=g_X(x_2) }[/math], וכיוון ש-[math]\displaystyle{ g_X }[/math] חח"ע נובע [math]\displaystyle{ x_1=x_2 }[/math].

לכן

[math]\displaystyle{ |U|\leq|\mathbb{N}\times\mathbb{N}|=\aleph_0\cdot\aleph_0=\aleph_0 }[/math]

▶ ההוכחה בהרצאה מ־10.8.26, החל מהדקה 2:46:17

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

הוכחה. נסמן ב-[math]\displaystyle{ D }[/math] את אוסף תתי הקבוצות הסופיות של [math]\displaystyle{ \mathbb{N} }[/math], ולכל [math]\displaystyle{ n\in\mathbb{N} }[/math] נגדיר

[math]\displaystyle{ A_n=\{X\subseteq\mathbb{N}\mid |X|=n\} }[/math]

לפי ההגדרה [math]\displaystyle{ D=\bigcup_{n\in\mathbb{N}}A_n }[/math], וזהו איחוד של מספר בן מנייה של קבוצות. לכן לפי המשפט מספיק להוכיח שכל [math]\displaystyle{ A_n }[/math] בת מנייה.

• [math]\displaystyle{ A_0=\{\emptyset\} }[/math] סופית.
• יהי [math]\displaystyle{ n\geq 1 }[/math], ונגדיר [math]\displaystyle{ B_n=\{X\subseteq\mathbb{N}\mid 1\leq|X|\leq n\} }[/math]. ברור כי [math]\displaystyle{ A_n\subseteq B_n }[/math] ולכן [math]\displaystyle{ |A_n|\leq|B_n| }[/math].
• נביט בפונקציה [math]\displaystyle{ F:\mathbb{N}^n\to B_n }[/math] המוגדרת ע"י [math]\displaystyle{ F(x_1,\ldots,x_n)=\{x_1,\ldots,x_n\} }[/math]. ייתכן שחלק מה-[math]\displaystyle{ x_i }[/math] שווים זה לזה, ואז הקבוצה קטנה יותר; למשל [math]\displaystyle{ F(5,5,\ldots,5)=\{5\} }[/math].
• [math]\displaystyle{ F }[/math] על: אם [math]\displaystyle{ X=\{y_1,\ldots,y_k\}\in B_n }[/math] כאשר [math]\displaystyle{ 1\leq k\leq n }[/math], אזי [math]\displaystyle{ X=F(y_1,\ldots,y_k,y_k,\ldots,y_k) }[/math].
• לפי הטענה שהוכחנו בעזרת אקסיומת הבחירה (קיימת פונקציה על מ-[math]\displaystyle{ \mathbb{N}^n }[/math] אל [math]\displaystyle{ B_n }[/math], ושתיהן אינן ריקות) נובע כי

[math]\displaystyle{ |A_n|\leq|B_n|\leq|\mathbb{N}^n|=\aleph_0^n=\aleph_0 }[/math]

לכן [math]\displaystyle{ D }[/math] בת מנייה (ואף [math]\displaystyle{ |D|=\aleph_0 }[/math], כי [math]\displaystyle{ D }[/math] אינסופית). לעומת זאת, אוסף כל תתי הקבוצות של [math]\displaystyle{ \mathbb{N} }[/math] אינו בן מנייה: [math]\displaystyle{ |P(\mathbb{N})|=2^{\aleph_0}>\aleph_0 }[/math]. ▶ ההוכחה בהרצאה מ־10.8.26, החל מהדקה 3:02:25

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

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

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

• תהיינה שתי קבוצות A,B אזי [math]\displaystyle{ |A|\leq|B| }[/math] או [math]\displaystyle{ |A|\geq |B| }[/math]

• נביט ב[math]\displaystyle{ U }[/math] אוסף היחסים הח"ע והחח"ע מ[math]\displaystyle{ A }[/math] ל[math]\displaystyle{ B }[/math], וניקח שרשרת מקסימלית ביחס ההכלה [math]\displaystyle{ M\subseteq U }[/math]
• נסמן ב[math]\displaystyle{ f }[/math] את האיחוד הכללי על השרשרת [math]\displaystyle{ M }[/math]
• ראינו שנובע במקרה זה כי [math]\displaystyle{ f }[/math] יחס ח"ע וחח"ע מ[math]\displaystyle{ A }[/math] ל[math]\displaystyle{ B }[/math].
  • אם [math]\displaystyle{ f }[/math] שלם, אזי [math]\displaystyle{ f:A\to B }[/math] פונקציה חח"ע ולכן [math]\displaystyle{ |A|\leq |B| }[/math]
  • אם [math]\displaystyle{ f }[/math] על, אזי [math]\displaystyle{ f:X\to B }[/math] פונקציה על עבור [math]\displaystyle{ X\subseteq A }[/math] ולכן [math]\displaystyle{ |B|\leq |X|\leq |A| }[/math]
  • אחרת, קיים זוג [math]\displaystyle{ (a,b)\in A\times B }[/math] כך ש [math]\displaystyle{ f\cup\{(a,b)\} }[/math] יחס ח"ע וחח"ע שניתן להוסיף לשרשרת [math]\displaystyle{ M }[/math] בסתירה למקסימליות שלה.

הוכחה (פירוט של ההוכחה שלעיל).

• כל יחס ב-[math]\displaystyle{ U }[/math] מוכל ב-[math]\displaystyle{ A\times B }[/math], ולכן גם [math]\displaystyle{ f\subseteq A\times B }[/math]. לפי הטענות השימושיות לעיל [math]\displaystyle{ f }[/math] ח"ע וחח"ע, כלומר [math]\displaystyle{ f\in U }[/math].
• נסמן [math]\displaystyle{ X=\{a\in A\mid \exists b\in B:(a,b)\in f\} }[/math] ו-[math]\displaystyle{ Y=\{b\in B\mid \exists a\in A:(a,b)\in f\} }[/math]. אז [math]\displaystyle{ f:X\to Y }[/math] פונקציה חח"ע ועל.
• אם [math]\displaystyle{ X=A }[/math] (כלומר [math]\displaystyle{ f }[/math] שלם), אזי [math]\displaystyle{ f:A\to B }[/math] חח"ע ולכן [math]\displaystyle{ |A|\leq|B| }[/math].
• אם [math]\displaystyle{ Y=B }[/math] (כלומר [math]\displaystyle{ f }[/math] על), אזי [math]\displaystyle{ f:X\to B }[/math] חח"ע ועל ולכן [math]\displaystyle{ |B|=|X|\leq|A| }[/math].
• אחרת קיימים [math]\displaystyle{ a\in A\setminus X }[/math] ו-[math]\displaystyle{ b\in B\setminus Y }[/math], כלומר [math]\displaystyle{ a }[/math] ו-[math]\displaystyle{ b }[/math] אינם מופיעים באף זוג של [math]\displaystyle{ f }[/math]. נגדיר [math]\displaystyle{ f'=f\cup\{(a,b)\} }[/math].
  • [math]\displaystyle{ f' }[/math] ח"ע: יהיו [math]\displaystyle{ (x,y_1),(x,y_2)\in f' }[/math]. אם [math]\displaystyle{ x=a }[/math], שני הזוגות שווים ל-[math]\displaystyle{ (a,b) }[/math] (כי [math]\displaystyle{ a }[/math] אינו מופיע ב-[math]\displaystyle{ f }[/math]) ולכן [math]\displaystyle{ y_1=y_2 }[/math]. אחרת שני הזוגות שייכים ל-[math]\displaystyle{ f }[/math], ו-[math]\displaystyle{ f }[/math] ח"ע.
  • [math]\displaystyle{ f' }[/math] חח"ע: באותו אופן, כי [math]\displaystyle{ b }[/math] אינו מופיע ב-[math]\displaystyle{ f }[/math].
  • לכן [math]\displaystyle{ f'\in U }[/math].
• [math]\displaystyle{ M'=M\cup\{f'\} }[/math] היא שרשרת, כי לכל [math]\displaystyle{ T\in M }[/math] מתקיים [math]\displaystyle{ T\subseteq f\subseteq f' }[/math].
• [math]\displaystyle{ M'\neq M }[/math], כי אחרת [math]\displaystyle{ f'\in M }[/math] ולכן [math]\displaystyle{ f'\subseteq f }[/math], בסתירה לכך ש-[math]\displaystyle{ (a,b)\in f'\setminus f }[/math].
• לכן [math]\displaystyle{ M' }[/math] שרשרת המכילה ממש את [math]\displaystyle{ M }[/math], בסתירה למקסימליות של [math]\displaystyle{ M }[/math]. כלומר המקרה האחרון אינו אפשרי, ותמיד [math]\displaystyle{ |A|\leq|B| }[/math] או [math]\displaystyle{ |B|\leq|A| }[/math].

▶ ההוכחה בהרצאה מ־12.8.26, החל מהדקה 1:03:59

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

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

• תהי A קבוצה אינסופית, אזי [math]\displaystyle{ \aleph_0\leq |A| }[/math]

• דרך נוספת לזו המופיעה בסרטון:
  • נוכיח בהמשך כי ניתן להשוות עוצמה בין כל שתי קבוצות
  • אם [math]\displaystyle{ |A|\leq |\mathbb{N}| }[/math], כיוון ש[math]\displaystyle{ A }[/math] אינסופית נובע כי [math]\displaystyle{ |A|=\aleph_0 }[/math]
  • אחרת, [math]\displaystyle{ |\mathbb{N}|\leq |A| }[/math] ולכן [math]\displaystyle{ \aleph_0\leq |A| }[/math] כפי שרצינו.

• טענת עזר (בה משתמשים בדרך הנוספת): תהי [math]\displaystyle{ B\subseteq\mathbb{N} }[/math] קבוצה אינסופית, אזי [math]\displaystyle{ |B|=\aleph_0 }[/math].

הוכחה. הרעיון: בקבוצת הראשוניים [math]\displaystyle{ \{2,3,5,7,11,\ldots\} }[/math] נשלח את 2 ל-0, את 3 ל-1, את 5 ל-2 וכן הלאה; כל מספר נשלח לכמות המספרים בקבוצה שקטנים ממנו.

נגדיר [math]\displaystyle{ f:B\to\mathbb{N} }[/math] ע"י

[math]\displaystyle{ f(b)=\left|\{x\in B\mid x<b\}\right| }[/math]

(זו קבוצה סופית, כי היא מוכלת ב-[math]\displaystyle{ \{0,1,\ldots,b-1\} }[/math]). נוכיח כי [math]\displaystyle{ f }[/math] חח"ע ועל.

• חח"ע: יהיו [math]\displaystyle{ b_1<b_2 }[/math] ב-[math]\displaystyle{ B }[/math]. כל איבר של [math]\displaystyle{ B }[/math] שקטן מ-[math]\displaystyle{ b_1 }[/math] קטן גם מ-[math]\displaystyle{ b_2 }[/math], ובנוסף [math]\displaystyle{ b_1 }[/math] עצמו קטן מ-[math]\displaystyle{ b_2 }[/math]. לכן [math]\displaystyle{ f(b_2)\geq f(b_1)+1 }[/math], ובפרט [math]\displaystyle{ f(b_1)\neq f(b_2) }[/math].
• על: נב"ש שלא, ויהי [math]\displaystyle{ n\in\mathbb{N} }[/math] המספר הקטן ביותר שאין לו מקור.
  • [math]\displaystyle{ n\neq 0 }[/math]: האיבר הקטן ביותר [math]\displaystyle{ m }[/math] של [math]\displaystyle{ B }[/math] (קיים כי [math]\displaystyle{ B\neq\emptyset }[/math]) מקיים [math]\displaystyle{ f(m)=0 }[/math].
  • לכן [math]\displaystyle{ n\geq 1 }[/math], ולפי המינימליות של [math]\displaystyle{ n }[/math] יש ל-[math]\displaystyle{ n-1 }[/math] מקור [math]\displaystyle{ a\in B }[/math]. כלומר [math]\displaystyle{ |\{y\in B\mid y<a\}|=n-1 }[/math], ולכן [math]\displaystyle{ |\{y\in B\mid y\leq a\}|=n }[/math].
  • הקבוצה [math]\displaystyle{ \{y\in B\mid y>a\} }[/math] אינה ריקה, כי אחרת [math]\displaystyle{ B\subseteq\{0,1,\ldots,a\} }[/math] הייתה סופית. יהי [math]\displaystyle{ x }[/math] האיבר הקטן ביותר בה.
  • האיברים של [math]\displaystyle{ B }[/math] הקטנים מ-[math]\displaystyle{ x }[/math] הם בדיוק האיברים של [math]\displaystyle{ B }[/math] הקטנים או שווים ל-[math]\displaystyle{ a }[/math] (כי [math]\displaystyle{ x }[/math] הוא האיבר הקטן ביותר ב-[math]\displaystyle{ B }[/math] שגדול מ-[math]\displaystyle{ a }[/math]). לכן [math]\displaystyle{ f(x)=n }[/math], בסתירה לכך שאין ל-[math]\displaystyle{ n }[/math] מקור.

השלמת הדרך הנוספת: אם [math]\displaystyle{ |A|\leq|\mathbb{N}| }[/math], קיימת [math]\displaystyle{ g:A\to\mathbb{N} }[/math] חח"ע, ולכן [math]\displaystyle{ A\sim g[A] }[/math] כאשר [math]\displaystyle{ g[A]\subseteq\mathbb{N} }[/math]. כיוון ש-[math]\displaystyle{ A }[/math] אינסופית גם [math]\displaystyle{ g[A] }[/math] אינסופית, ולפי טענת העזר [math]\displaystyle{ |A|=|g[A]|=\aleph_0 }[/math]. ▶ ההוכחה בהרצאה מ־12.8.26, החל מהדקה 2:58:05

• תהי A קבוצה אינסופית, ותהי B קבוצה סופית, אזי:
  • [math]\displaystyle{ |A|=|A\cup B|=|A\setminus B| }[/math]

• דרך נוספת לזו המופיעה בסרטון:
  • בהמשך נוכיח כי לכל קבוצה אינסופית [math]\displaystyle{ X }[/math] מתקיים כי [math]\displaystyle{ |X|+|X|=|X| }[/math]
  • לכן [math]\displaystyle{ |A|\leq |A\cup B|=|A|+|B\setminus A|\leq |A|+|A|=|A| }[/math] ולפי ק.ש.ב [math]\displaystyle{ |A|=|A\cup B| }[/math].
    • שימו לב כי [math]\displaystyle{ B\setminus A }[/math] סופית ולכן קטנה יותר מהקבוצה האינסופית [math]\displaystyle{ A }[/math].
  • כמו כן [math]\displaystyle{ |A|=|A\setminus B|+|B\cap A| }[/math]
  • כעת [math]\displaystyle{ |A\setminus B|\leq|A\setminus B|+|B\cap A|\leq |A\setminus B|+|A\setminus B|=|A\setminus B| }[/math].
    • שימו לב כי [math]\displaystyle{ B\cap A }[/math] סופית ולכן קטנה יותר מהקבוצה האינסופית [math]\displaystyle{ A\setminus B }[/math].
  • לכן לפי ק.ש.ב [math]\displaystyle{ |A|=|A\setminus B|+|B\cap A|=|A\setminus B| }[/math]

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

• תהיינה עוצמות [math]\displaystyle{ a\leq b }[/math] אזי:
  • [math]\displaystyle{ b\leq a+b }[/math]

הוכחה. נבחר נציגות זרות [math]\displaystyle{ A,B }[/math] כך ש [math]\displaystyle{ |A|=a }[/math] וכן [math]\displaystyle{ |B|=b }[/math]. כיוון ש [math]\displaystyle{ B\subseteq A\cup B }[/math], פונקציית ההכלה חח"ע, ולכן

[math]\displaystyle{ b=|B|\leq|A\cup B|=a+b }[/math]

• נניח בנוסף כי [math]\displaystyle{ 2\leq a\leq b }[/math] אזי:
  • [math]\displaystyle{ a+b\leq a\cdot b }[/math]

הוכחה. נבחר נציגות זרות [math]\displaystyle{ A,B }[/math] כך ש [math]\displaystyle{ |A|=a }[/math] וכן [math]\displaystyle{ |B|=b }[/math]. כיוון ש [math]\displaystyle{ 2\leq a,b }[/math] קיימים [math]\displaystyle{ a_1\neq a_2\in A }[/math] וכן [math]\displaystyle{ b_1\neq b_2\in B }[/math]. נבנה פונקציה [math]\displaystyle{ f:A\cup B\to A\times B }[/math]:

[math]\displaystyle{ f(x)=\begin{cases}(x,b_1) & x\in A\setminus\{a_1,a_2\}\\ (a_1,x) & x\in B\setminus\{b_1,b_2\}\\ (a_1,b_1) & x=a_1\\ (a_2,b_1) & x=a_2\\ (a_1,b_2) & x=b_1\\ (a_2,b_2) & x=b_2\end{cases} }[/math]

(כיוון ש-[math]\displaystyle{ A,B }[/math] זרות, כל [math]\displaystyle{ x\in A\cup B }[/math] נופל בדיוק במקרה אחד.)

[math]\displaystyle{ f }[/math] חח"ע: ארבעת האיברים [math]\displaystyle{ a_1,a_2,b_1,b_2 }[/math] נשלחים לארבעה זוגות שונים מתוך [math]\displaystyle{ \{a_1,a_2\}\times\{b_1,b_2\} }[/math]. איבר [math]\displaystyle{ x\in A\setminus\{a_1,a_2\} }[/math] נשלח לזוג שהרכיב השני שלו [math]\displaystyle{ b_1 }[/math] והראשון הוא [math]\displaystyle{ x }[/math] עצמו, השונה מ-[math]\displaystyle{ a_1,a_2 }[/math]. איבר [math]\displaystyle{ y\in B\setminus\{b_1,b_2\} }[/math] נשלח לזוג שהרכיב השני שלו הוא [math]\displaystyle{ y }[/math] עצמו, השונה מ-[math]\displaystyle{ b_1,b_2 }[/math]. לכן זוגות משלושת הסוגים שונים זה מזה, ובתוך כל סוג הזוג קובע את המקור. מכאן

[math]\displaystyle{ a+b=|A\cup B|\leq|A\times B|=a\cdot b }[/math]

הדרישה [math]\displaystyle{ 2\leq a }[/math] הכרחית: למשל [math]\displaystyle{ 1+2=3>2=1\cdot 2 }[/math]. ▶ ההוכחה בהרצאה מ־12.8.26, החל מהדקה 2:36:19

• נניח בנוסף כי b אינסופית, ונקבל ביחד
  • [math]\displaystyle{ b\leq a+b \leq a\cdot b\leq b\cdot b =b }[/math] (המעבר [math]\displaystyle{ b\cdot b=b }[/math] מוכח בסרטון השני).
• ולכן לפי משפט ק.ש.ב נקבל כי
  • [math]\displaystyle{ a+b=a\cdot b = b }[/math]

• הערה: אם [math]\displaystyle{ b }[/math] אינסופית ו-[math]\displaystyle{ a\leq b }[/math], אזי [math]\displaystyle{ a+b=b }[/math] גם ללא ההנחה [math]\displaystyle{ 2\leq a }[/math]. אם בנוסף [math]\displaystyle{ 1\leq a }[/math], אזי [math]\displaystyle{ a\cdot b=b }[/math] (ועבור [math]\displaystyle{ a=0 }[/math] כמובן [math]\displaystyle{ 0\cdot b=0 }[/math]).

הוכחה. כיוון ש-[math]\displaystyle{ b }[/math] אינסופית, [math]\displaystyle{ 2\leq b }[/math]. לפי הטענות לעיל (עם [math]\displaystyle{ b }[/math] במקום [math]\displaystyle{ a }[/math]), לפי [math]\displaystyle{ b\cdot b=b }[/math] ולפי השוואת חשבון עוצמות:

[math]\displaystyle{ b\leq a+b\leq b+b\leq b\cdot b=b }[/math]

ולפי ק.ש.ב [math]\displaystyle{ a+b=b }[/math]. כמו כן [math]\displaystyle{ 1\cdot b=b }[/math] (עבור [math]\displaystyle{ |B|=b }[/math], הפונקציה [math]\displaystyle{ x\mapsto(p,x) }[/math] הפיכה מ-[math]\displaystyle{ B }[/math] אל [math]\displaystyle{ \{p\}\times B }[/math]), ולכן אם [math]\displaystyle{ 1\leq a }[/math]:

[math]\displaystyle{ b=1\cdot b\leq a\cdot b\leq b\cdot b=b }[/math]

ולפי ק.ש.ב [math]\displaystyle{ a\cdot b=b }[/math].

• דוגמא - מה היא עוצמת קבוצת המספרים האי-רציונאליים?
• [math]\displaystyle{ \mathbb{R}=\mathbb{Q}\cup (\mathbb{R}\setminus\mathbb{Q}) }[/math] (איחוד זר כמובן)
• לכן [math]\displaystyle{ |\mathbb{R}|=|\mathbb{Q}|+ |(\mathbb{R}\setminus\mathbb{Q})| }[/math]
• לכן [math]\displaystyle{ \aleph=\aleph_0 +|(\mathbb{R}\setminus\mathbb{Q})| }[/math]
• לפי המשפט לעיל, סכום העוצמות הוא העוצמה הגדולה מבין השתיים.
• כיוון ש [math]\displaystyle{ \aleph\neq \aleph_0 }[/math] נקבל כי [math]\displaystyle{ |(\mathbb{R}\setminus\mathbb{Q})|=\aleph }[/math]

עוצמה כפול עצמה

• תהי קבוצה אינסופית [math]\displaystyle{ B }[/math] אזי [math]\displaystyle{ B\times B\sim B }[/math]

• הוכחה:
• תהי [math]\displaystyle{ S }[/math] קבוצת כל היחסים [math]\displaystyle{ R\subseteq (B\times B)\times B }[/math], כך שקיימת תת קבוצה [math]\displaystyle{ X\subseteq B }[/math] כך ש [math]\displaystyle{ R:X\times X\to X }[/math] פונקציה הפיכה.
• כיוון ש[math]\displaystyle{ B }[/math] אינסופית, יש לה תת קבוצה [math]\displaystyle{ Y\subseteq B }[/math] כך ש [math]\displaystyle{ |Y|=\aleph_0 }[/math].
• כיוון ש [math]\displaystyle{ \aleph_0\cdot\aleph_0=\aleph_0 }[/math] קיימת פונקציה הפיכה [math]\displaystyle{ R:Y\times Y\to Y }[/math].
• נביט ביחס ההכלה על [math]\displaystyle{ S }[/math]. לפי עקרון המקסימום של האוסדורף, קיימת שרשרת מקסימלית [math]\displaystyle{ \{R\}\subseteq M\subseteq S }[/math].
• נסמן ב[math]\displaystyle{ f }[/math] את האיחוד הכללי של השרשרת [math]\displaystyle{ f=\cup_{T\in M} T }[/math].
• נוכיח כי קיימת [math]\displaystyle{ D\subseteq B }[/math] כך ש [math]\displaystyle{ f:D\times D\to D }[/math] פונקציה הפיכה, ואף [math]\displaystyle{ |D|=|B| }[/math] וכך נסיים את ההוכחה.

• הוכחה כי [math]\displaystyle{ f\in S }[/math] פונקציה הפיכה [math]\displaystyle{ f:D\times D\to D }[/math] עבור תת קבוצה [math]\displaystyle{ D\subseteq B }[/math]:
• ראשית, נגדיר את [math]\displaystyle{ D=\{d\in B | \exists a,b\in B:((a,b),d)\in f\} }[/math]
• נוכיח כי [math]\displaystyle{ f\subseteq (D\times D)\times D }[/math]:
  • יהי זוג [math]\displaystyle{ ((a,b),d)\in f }[/math], לפי ההגדרה [math]\displaystyle{ d\in D }[/math]
  • כמו כן, לפי הגדרת האיחוד קיים [math]\displaystyle{ T\in M }[/math] כך ש [math]\displaystyle{ ((a,b),d)\in T }[/math].
  • קיימת [math]\displaystyle{ X\subseteq B }[/math] כך ש [math]\displaystyle{ T:X\times X\to X }[/math] פונקציה הפיכה.
  • כיוון ש [math]\displaystyle{ T }[/math] על, לכל [math]\displaystyle{ x\in X }[/math] קיימים [math]\displaystyle{ p,q\in X }[/math] כך ש [math]\displaystyle{ ((p,q),x)\in T }[/math] ולכן [math]\displaystyle{ ((p,q),x)\in f }[/math] ולכן [math]\displaystyle{ x\in D }[/math]
  • ביחד עם העובדה ש [math]\displaystyle{ a,b\in X }[/math] נובע כי [math]\displaystyle{ a,b\in D }[/math]
• כיוון שכל איברי השרשרת הם יחסים ח"ע, גם [math]\displaystyle{ f }[/math] ח"ע.
• כיוון שכל איברי השרשרת הם יחסים חח"ע, גם [math]\displaystyle{ f }[/math] חח"ע.
• כעת נוכיח כי [math]\displaystyle{ f:D\times D\to D }[/math] יחס שלם:
  • יהיו [math]\displaystyle{ d_1,d_2\in D }[/math].
  • ראינו כי קיימים [math]\displaystyle{ T_1,T_2\in M }[/math] ואיברים [math]\displaystyle{ a_1,b_1,a_2,b_2\in D }[/math] כך ש [math]\displaystyle{ ((a_1,b_1),d_1)\in T_1 }[/math] וכן [math]\displaystyle{ ((a_2,b_2),d_2)\in T_2 }[/math]
  • כיוון ש[math]\displaystyle{ M }[/math] שרשרת, [math]\displaystyle{ T_1\subseteq T_2 }[/math] (או ההפך), ולכן [math]\displaystyle{ ((a_1,b_1),d_1),((a_2,b_2),d_2)\in T_2 }[/math]. קיימת תת קבוצה [math]\displaystyle{ X\subseteq D }[/math] כך ש [math]\displaystyle{ T_2:X\times X\to X }[/math] פונקציה הפיכה, ולכן [math]\displaystyle{ d_1,d_2\in X }[/math].
  • לכן קיים [math]\displaystyle{ d_3\in X\subseteq D }[/math] כך ש [math]\displaystyle{ ((d_1,d_2),d_3)\in T_2 }[/math] ולכן [math]\displaystyle{ ((d_1,d_2),d_3)\in f }[/math] כלומר [math]\displaystyle{ f }[/math] שלם.
• הוכחנו כי [math]\displaystyle{ f:D\times D\to D }[/math] היא פונקציה (יחס ח"ע ושלם) חח"ע, נותר להוכיח כי היא על:
  • יהי [math]\displaystyle{ d\in D }[/math]. ראינו כי קיים [math]\displaystyle{ T\in M }[/math] וקיימים [math]\displaystyle{ a,b\in D }[/math] כך ש [math]\displaystyle{ ((a,b),d)\in T }[/math] ולכן [math]\displaystyle{ ((a,b),d)\in f }[/math] ולכן הפונקציה על.

• הוכחה כי [math]\displaystyle{ |D|=|B| }[/math]:
• ראשית, נשים לב כי [math]\displaystyle{ Y\subseteq D }[/math] כיוון ש [math]\displaystyle{ R:Y\times Y\to Y }[/math] פונקציה הפיכה וכן [math]\displaystyle{ R\in M }[/math], ולכן [math]\displaystyle{ D }[/math] אינסופית.
• כעת, נזכור שהוכחנו כי [math]\displaystyle{ |D\times D|=|D| }[/math].
• נביט ב [math]\displaystyle{ B\setminus D }[/math] ונחלק למקרים:
• אם [math]\displaystyle{ |B\setminus D|\leq |D| }[/math] אזי:
  • [math]\displaystyle{ |B|=|D|+|B\setminus D|\leq |D|+|D|\leq |D|\times |D| =|D| }[/math]
  • כמובן ש [math]\displaystyle{ |D|\leq |B| }[/math] ולפי ק.ש.ב נסיק כי במקרה זה [math]\displaystyle{ |B|=|D| }[/math] וסיימנו.
• אם [math]\displaystyle{ |B\setminus D|\geq |D| }[/math] נראה כי נגיע לסתירה, ולכן מקרה זה בלתי אפשרי:
  • ניקח תת קבוצה [math]\displaystyle{ U\subseteq B\setminus D }[/math] כך ש [math]\displaystyle{ |U|=|D| }[/math].
  • לכן [math]\displaystyle{ |(U\times D) \cup (D\times U) \cup (U\times U)|=|D|+|D|+|D|=|D| }[/math] (הרי ראינו מקודם כי [math]\displaystyle{ |D|+|D|=|D| }[/math])
  • לכן קיימת פונקציה הפיכה [math]\displaystyle{ g:(U\times D) \cup (D\times U) \cup (U\times U)\to U }[/math].
  • האיחוד [math]\displaystyle{ h=f\cup g }[/math] הוא פונקציה הפיכה [math]\displaystyle{ h:(U\cup D)\times (U\cup D)\to (U\cup D) }[/math], ולכן [math]\displaystyle{ h\in S }[/math].
  • ניתן להוסיף את [math]\displaystyle{ h }[/math] לשרשרת [math]\displaystyle{ M }[/math] ולהגדיל אותה, בסתירה למקסימליות שלה.

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

• [math]\displaystyle{ 2^{\aleph_0}=\aleph }[/math] כלומר [math]\displaystyle{ P(\mathbb{N})\sim\mathbb{R} }[/math]

הוכחה. [math]\displaystyle{ 2^{\aleph_0}=|\{0,1\}^{\mathbb{N}}| }[/math] היא עוצמת קבוצת הסדרות הבינאריות, וכן [math]\displaystyle{ |P(\mathbb{N})|=2^{\aleph_0} }[/math]. לפי עוצמות קטעים ממשיים [math]\displaystyle{ |[0,1)|=\aleph }[/math].

• [math]\displaystyle{ 2^{\aleph_0}\leq\aleph }[/math]: נתאים לכל סדרה בינארית [math]\displaystyle{ (s_0,s_1,s_2,\ldots) }[/math] את המספר שהפיתוח העשרוני שלו הוא [math]\displaystyle{ 0.s_0s_1s_2\ldots }[/math], כלומר [math]\displaystyle{ \sum_{n=0}^{\infty}s_n\cdot 10^{-(n+1)} }[/math]; זהו מספר בקטע [math]\displaystyle{ [0,1) }[/math]. ההתאמה חח"ע: אם שתי סדרות נבדלות לראשונה במקום ה-[math]\displaystyle{ k }[/math], כאשר באחת מופיע 1 ובשנייה 0, אזי ההפרש בין המספרים המתאימים הוא לפחות

[math]\displaystyle{ 10^{-(k+1)}-\sum_{n>k}10^{-(n+1)}=\frac{8}{9}\cdot 10^{-(k+1)}>0 }[/math]

לכן [math]\displaystyle{ 2^{\aleph_0}\leq|[0,1)|=\aleph }[/math].

• [math]\displaystyle{ \aleph\leq 2^{\aleph_0} }[/math]: לכל מספר בקטע [math]\displaystyle{ [0,1) }[/math] יש פיתוח עשרוני יחיד [math]\displaystyle{ 0.d_0d_1d_2\ldots }[/math] שאינו מסתיים ברצף אינסופי של הספרה 9. נתאים לכל מספר את סדרת הספרות שלו [math]\displaystyle{ (d_0,d_1,d_2,\ldots)\in\{0,1,\ldots,9\}^{\mathbb{N}} }[/math]; זו התאמה חח"ע, כי סדרת הספרות קובעת את המספר. לכן

[math]\displaystyle{ \aleph=|[0,1)|\leq 10^{\aleph_0}\leq 16^{\aleph_0} }[/math]

[math]\displaystyle{ =(2^4)^{\aleph_0}=2^{4\cdot\aleph_0}=2^{\aleph_0} }[/math]

• לפי משפט ק.ש.ב [math]\displaystyle{ 2^{\aleph_0}=\aleph }[/math].

▶ ההוכחה בהרצאה מ־12.8.26, החל מהדקה 2:29:25

תרגול

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