עוצמות של קבוצות
עוצמה (cardinality) של קבוצה היא הכללה של מושג "מספר האיברים" גם לקבוצות אינסופיות, ונלמדת בפרק 5 של הקורס מתמטיקה בדידה - ארז שיינר. הנושא מכונה בפי הסטודנטים גם "עוצמות", "השוואת עוצמות", "קבוצה בת מנייה", "עוצמת הרצף", "חשבון עוצמות" (או אריתמטיקה של עוצמות), "אלף אפס" ו"עוצמת קבוצת החזקה" - כל אלו הם היבטים שונים של אותו נושא, ומטרת דף זה לרכז אותם יחד.
הגדרה
- תהיינה [math]\displaystyle{ A,B }[/math] קבוצות. אומרים ש-[math]\displaystyle{ A,B }[/math] שוות עוצמה (או שקולות עוצמה), ומסמנים [math]\displaystyle{ A\sim B }[/math] או [math]\displaystyle{ |A|=|B| }[/math], אם קיימת פונקציה [math]\displaystyle{ f:A\to B }[/math] הפיכה (חד-חד-ערכית ועל).
- אומרים כי עוצמתה של [math]\displaystyle{ A }[/math] קטנה או שווה לזו של [math]\displaystyle{ B }[/math], ומסמנים [math]\displaystyle{ |A|\leq|B| }[/math], אם קיימת פונקציה חד-חד-ערכית [math]\displaystyle{ f:A\to B }[/math]. אם בנוסף [math]\displaystyle{ |A|\neq|B| }[/math] כותבים [math]\displaystyle{ |A|<|B| }[/math].
- אם [math]\displaystyle{ A\subseteq B }[/math] אז פונקציית ההכלה [math]\displaystyle{ f(x)=x }[/math] חד-חד-ערכית, ולכן [math]\displaystyle{ |A|\leq|B| }[/math].
- שקילות עוצמה מקיימת רפלקסיביות (פונקציית הזהות), סימטריות (הפונקציה ההופכית) וטרנזיטיביות (הרכבת פונקציות) - ממש כמו יחס שקילות, אלא שטכנית אין "קבוצת כל הקבוצות" שעליה אפשר להגדיר יחס במובן הפורמלי.
- קבוצה בת מנייה היא קבוצה [math]\displaystyle{ A }[/math] המקיימת [math]\displaystyle{ |A|\leq\aleph_0 }[/math], כאשר [math]\displaystyle{ \aleph_0:=|\mathbb{N}| }[/math] היא עוצמת הטבעיים. קבוצה בת מנייה אינסופית מקיימת [math]\displaystyle{ |A|=\aleph_0 }[/math] (ראו משפט להלן).
- כל קבוצה השקולה עוצמה לממשיים מסומנת [math]\displaystyle{ |A|=\aleph }[/math] ("עוצמת הרצף"). ההבדל בין [math]\displaystyle{ \aleph_0 }[/math] ל-[math]\displaystyle{ \aleph }[/math]: [math]\displaystyle{ \aleph_0 }[/math] היא עוצמת הטבעיים (וכל קבוצה בת מנייה אינסופית), ואילו [math]\displaystyle{ \aleph }[/math] היא עוצמת הממשיים - וזו עוצמה גדולה ממש: [math]\displaystyle{ \aleph_0<\aleph }[/math] (לפי הלכסון של קנטור; ראו גם "עוצמת הרצף" בהמשך).
משפטים ותכונות
- משפט קנטור. לכל קבוצה [math]\displaystyle{ A }[/math] מתקיים [math]\displaystyle{ |A|<|P(A)| }[/math] (עוצמת קבוצת החזקה גדולה ממש מעוצמת הקבוצה).
- הוכחה: הפונקציה [math]\displaystyle{ x\mapsto\{x\} }[/math] חד-חד-ערכית מ-[math]\displaystyle{ A }[/math] ל-[math]\displaystyle{ P(A) }[/math], ולכן [math]\displaystyle{ |A|\leq|P(A)| }[/math]. אילו הייתה קיימת [math]\displaystyle{ f:A\to P(A) }[/math] הפיכה, נגדיר [math]\displaystyle{ D=\{x\in A: x\notin f(x)\}\subseteq A }[/math]. כיוון ש-[math]\displaystyle{ f }[/math] על, קיים [math]\displaystyle{ x_0 }[/math] עם [math]\displaystyle{ f(x_0)=D }[/math]. אם [math]\displaystyle{ x_0\in D }[/math] אז לפי הגדרת [math]\displaystyle{ D }[/math], [math]\displaystyle{ x_0\notin f(x_0)=D }[/math] - סתירה; ואם [math]\displaystyle{ x_0\notin D=f(x_0) }[/math] אז לפי הגדרת [math]\displaystyle{ D }[/math], [math]\displaystyle{ x_0\in D }[/math] - סתירה. לכן [math]\displaystyle{ f }[/math] אינה יכולה להיות על.
- עוצמת קבוצת החזקה. [math]\displaystyle{ |P(A)|=2^{|A|} }[/math]. ההוכחה בונה התאמה הפיכה בין [math]\displaystyle{ P(A) }[/math] לקבוצת הפונקציות המציינות [math]\displaystyle{ \{0,1\}^A }[/math]: לכל [math]\displaystyle{ D\subseteq A }[/math] מתאימים את [math]\displaystyle{ \chi_D }[/math], המוגדרת [math]\displaystyle{ \chi_D(x)=1 }[/math] אם [math]\displaystyle{ x\in D }[/math] ו-[math]\displaystyle{ 0 }[/math] אחרת. יחד עם משפט קנטור מקבלים [math]\displaystyle{ |A|<2^{|A|} }[/math].
- משפט קנטור-שרדר-ברנשטיין (ק.ש.ב). אם [math]\displaystyle{ |A|\leq|B| }[/math] וגם [math]\displaystyle{ |B|\leq|A| }[/math] אזי [math]\displaystyle{ |A|=|B| }[/math]. זהו המשפט השימושי ביותר בנושא: כדי להוכיח שוויון עוצמות, במקום לבנות פונקציה הפיכה אחת (לעיתים קשה), מספיק למצוא שתי פונקציות חד-חד-ערכיות בכיוונים הפוכים. ההוכחה נשענת על למת נקודת השבת: לכל פונקציה עולה [math]\displaystyle{ h:P(A)\to P(A) }[/math] (כלומר [math]\displaystyle{ X_1\subseteq X_2\Rightarrow 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{ X\subseteq h(X) }[/math]). ההוכחה המלאה של המשפט מהלמה מובאת בהרצאה.
- קבוצות בנות מנייה. כל תת-קבוצה אינסופית של [math]\displaystyle{ \mathbb{N} }[/math] היא מעוצמה [math]\displaystyle{ \aleph_0 }[/math] (סופרים את איברי הקבוצה לפי גודלם). מסקנה: כל קבוצה בת מנייה אינסופית מקיימת [math]\displaystyle{ |A|=\aleph_0 }[/math], וכל קבוצה אינסופית מקיימת [math]\displaystyle{ \aleph_0\leq|A| }[/math] (בהנחת עקרון המקסימום של האוסדורף). כמו כן [math]\displaystyle{ |\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|=|\mathbb{N}\times\mathbb{N}|=\aleph_0 }[/math].
- חשבון עוצמות. עבור עוצמות [math]\displaystyle{ a=|A|,b=|B| }[/math] עם [math]\displaystyle{ A,B }[/math] זרות מגדירים [math]\displaystyle{ a+b:=|A\cup B| }[/math] ו-[math]\displaystyle{ a\cdot b:=|A\times B| }[/math], ועבור [math]\displaystyle{ A,B }[/math] כלשהן [math]\displaystyle{ a^b:=|A^B| }[/math] כאשר [math]\displaystyle{ A^B }[/math] אוסף הפונקציות מ-[math]\displaystyle{ B }[/math] ל-[math]\displaystyle{ A }[/math]. ניתן להראות שההגדרות אינן תלויות בבחירת הנציגות (וכל שתי קבוצות אפשר להחליף בנציגות זרות, למשל [math]\displaystyle{ A\times\{1\},B\times\{0\} }[/math]).
- חוקי חזקות. לכל עוצמות [math]\displaystyle{ a,b,c }[/math]: [math]\displaystyle{ a^b\cdot a^c=a^{b+c} }[/math], [math]\displaystyle{ (a^b)^c=a^{bc} }[/math], [math]\displaystyle{ a^b\cdot c^b=(ac)^b }[/math]. מקרי קצה: [math]\displaystyle{ a^0=1 }[/math], [math]\displaystyle{ 0^0=1 }[/math], [math]\displaystyle{ 1^a=1 }[/math], ואם [math]\displaystyle{ a\neq0 }[/math] אז [math]\displaystyle{ 0^a=0 }[/math]. שימו לב: אין פעולת חיסור על עוצמות.
- אריתמטיקה של עוצמות אינסופיות (בהנחת אקסיומת הבחירה): אם [math]\displaystyle{ a\leq b }[/math] ו-[math]\displaystyle{ b }[/math] אינסופית אז [math]\displaystyle{ a+b=b }[/math], ואם בנוסף [math]\displaystyle{ a\neq0 }[/math] אז גם [math]\displaystyle{ a\cdot b=b }[/math] (כלומר [math]\displaystyle{ a+b=\max\{a,b\} }[/math], ולעוצמות שונות מ-0 גם [math]\displaystyle{ a\cdot b=\max\{a,b\} }[/math]). מסקנה: אם [math]\displaystyle{ 2\leq a\leq b }[/math] ו-[math]\displaystyle{ b }[/math] אינסופית אז [math]\displaystyle{ a^b=2^b }[/math].
- עוצמת הרצף. [math]\displaystyle{ 2^{\aleph_0}=\aleph }[/math] (כלומר [math]\displaystyle{ P(\mathbb{N})\sim\mathbb{R} }[/math]), וכן [math]\displaystyle{ |\mathbb{R}|=|[a,b]|=|(a,b)|=|[a,\infty)|=\aleph }[/math] לכל קטע לא מנוון.
שיטה / איך מוכיחים
איך מוכיחים ששתי קבוצות שקולות עוצמה? שתי דרכים עיקריות:
- בנייה ישירה - להגדיר פונקציה [math]\displaystyle{ f:A\to B }[/math] מפורשת ולהוכיח שהיא חד-חד-ערכית ועל.
- סנדוויץ' עם ק.ש.ב - למצוא פונקציה חד-חד-ערכית [math]\displaystyle{ f:A\to B }[/math] ופונקציה חד-חד-ערכית [math]\displaystyle{ g:B\to A }[/math] (או לשרשר אי-שוויונות [math]\displaystyle{ |A|\leq\ldots\leq|B|\leq\ldots\leq|A| }[/math] דרך קבוצות ביניים ידועות), ולהסיק [math]\displaystyle{ |A|=|B| }[/math] ממשפט קנטור-שרדר-ברנשטיין. זו הדרך המועדפת כשקשה לבנות התאמה הפיכה ישירה.
איך מוכיחים שקבוצה [math]\displaystyle{ A }[/math] בת מנייה (כלומר [math]\displaystyle{ |A|\leq\aleph_0 }[/math])?
- למצוא פונקציה חד-חד-ערכית [math]\displaystyle{ f:A\to\mathbb{N} }[/math], או באופן שקול (עבור [math]\displaystyle{ A\neq\emptyset }[/math]), לסדר את איברי [math]\displaystyle{ A }[/math] בסדרה [math]\displaystyle{ a_1,a_2,a_3,\ldots }[/math] שבה כל איבר של [math]\displaystyle{ A }[/math] מופיע לפחות פעם אחת (זו פונקציה על מ-[math]\displaystyle{ \mathbb{N} }[/math] ל-[math]\displaystyle{ A }[/math]; אם כל איבר מופיע פעם אחת בדיוק זו התאמה הפיכה ו-[math]\displaystyle{ |A|=\aleph_0 }[/math]).
- להראות ש-[math]\displaystyle{ A }[/math] מוכלת בקבוצה שכבר ידוע שהיא בת מנייה (כי הכלה גוררת [math]\displaystyle{ \leq }[/math]).
- להשתמש בכך שאיחוד בן מנייה של קבוצות בנות מנייה הוא בן מנייה, ושמכפלה קרטזית סופית של קבוצות בנות מנייה היא בת מנייה (למשל [math]\displaystyle{ |\mathbb{N}\times\mathbb{N}|=\aleph_0 }[/math]).
איך מחשבים חזקה (או כל ביטוי אריתמטי) של עוצמות אינסופיות?
- להשתמש בנוסחאות [math]\displaystyle{ a+b=\max\{a,b\} }[/math] ו-[math]\displaystyle{ a\cdot b=\max\{a,b\} }[/math] כאשר לפחות אחת העוצמות אינסופית (ובמכפלה - שתיהן שונות מ-0).
- להציג את הבסיס או המעריך באמצעות [math]\displaystyle{ 2^{\aleph_0}=\aleph }[/math] ואז להפעיל את חוקי החזקות (למשל [math]\displaystyle{ \aleph^{\aleph_0}=(2^{\aleph_0})^{\aleph_0}=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}=\aleph }[/math]).
- כשאין נוסחה ישירה - לסגור בין שני חסמים ידועים ולהפעיל ק.ש.ב (כפי שנעשה כדי להוכיח [math]\displaystyle{ 2^{\aleph_0}=\aleph }[/math] עצמו).
דוגמאות
דוגמה 1 - השוואת עוצמות בהתאמה מפורשת. קבוצת המספרים הזוגיים וקבוצת הכפולות של 3 שקולות עוצמה: מתאימים לכל זוג [math]\displaystyle{ 2n }[/math] את הכפולה [math]\displaystyle{ 3n }[/math]. ההתאמה [math]\displaystyle{ 2n\mapsto 3n }[/math] חד-חד-ערכית ועל, אף שאינטואיטיבית "נדמה" שיש יותר זוגיים - אבל שתי הקבוצות אינסופיות בנות מנייה, ושתיהן מעוצמה [math]\displaystyle{ \aleph_0 }[/math].
דוגמה 2 - חיבור עוצמות. [math]\displaystyle{ \aleph_0+\aleph_0=\aleph_0 }[/math]: לוקחים כנציגות זרות את קבוצת הזוגיים ואת קבוצת האי-זוגיים, שתיהן מעוצמה [math]\displaystyle{ \aleph_0 }[/math] (כתת-קבוצות אינסופיות של [math]\displaystyle{ \mathbb{N} }[/math]) וזרות זו לזו; האיחוד שלהן הוא [math]\displaystyle{ \mathbb{N} }[/math] כולו, שעוצמתו [math]\displaystyle{ \aleph_0 }[/math].
דוגמה 3 - עוצמת האי-רציונליים. [math]\displaystyle{ \mathbb{R}=\mathbb{Q}\cup(\mathbb{R}\setminus\mathbb{Q}) }[/math] (איחוד זר), ולכן [math]\displaystyle{ \aleph=|\mathbb{R}|=|\mathbb{Q}|+|\mathbb{R}\setminus\mathbb{Q}|=\aleph_0+|\mathbb{R}\setminus\mathbb{Q}| }[/math]. לפי נוסחת החיבור לעוצמות אינסופיות, סכום זה שווה ל-[math]\displaystyle{ \max\{\aleph_0,|\mathbb{R}\setminus\mathbb{Q}|\} }[/math]. הסכום הזה שווה [math]\displaystyle{ \aleph }[/math], וכיוון ש-[math]\displaystyle{ \aleph\neq\aleph_0 }[/math] המקסימום לא יכול להתקבל מהאיבר [math]\displaystyle{ \aleph_0 }[/math] - כלומר בהכרח [math]\displaystyle{ |\mathbb{R}\setminus\mathbb{Q}|=\aleph }[/math].
דוגמה 4 - חזקה של עוצמות אינסופיות. מה עוצמת [math]\displaystyle{ \mathbb{N}^{\mathbb{N}} }[/math] (כל הפונקציות מ-[math]\displaystyle{ \mathbb{N} }[/math] ל-[math]\displaystyle{ \mathbb{N} }[/math])? לפי ההגדרה זו [math]\displaystyle{ \aleph_0^{\aleph_0} }[/math]. מכיוון ש-[math]\displaystyle{ \aleph_0\leq2^{\aleph_0} }[/math], מתקיים [math]\displaystyle{ \aleph_0^{\aleph_0}\leq(2^{\aleph_0})^{\aleph_0}=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}=\aleph }[/math] (חסם עליון), ומצד שני [math]\displaystyle{ \aleph_0^{\aleph_0}\geq2^{\aleph_0}=\aleph }[/math] (חסם תחתון, כי [math]\displaystyle{ 2\leq\aleph_0 }[/math]). לפי ק.ש.ב, [math]\displaystyle{ \aleph_0^{\aleph_0}=\aleph }[/math].
שאלות תרגול
שאלה 1. הוכיחו כי [math]\displaystyle{ |\mathbb{N}\times\mathbb{N}|=|\mathbb{N}| }[/math].
פתרון
נגדיר [math]\displaystyle{ f:\mathbb{N}\to\mathbb{N}\times\mathbb{N} }[/math] על-ידי מספור האלכסונים: מחלקים את הזוגות הסדורים לקבוצות לפי סכום הרכיבים - בקבוצה הראשונה הזוג [math]\displaystyle{ (1,1) }[/math], בשנייה [math]\displaystyle{ (1,2),(2,1) }[/math], בשלישית [math]\displaystyle{ (1,3),(2,2),(3,1) }[/math] וכן הלאה, וממספרים את כל הזוגות לפי הסדר הזה. כל מספר טבעי מגיע לזוג יחיד וכל זוג מקבל מספר יחיד (יש רק מספר סופי של זוגות בכל קבוצה, כך שהתהליך מוגדר היטב), ולכן [math]\displaystyle{ f }[/math] חד-חד-ערכית ועל, כלומר [math]\displaystyle{ |\mathbb{N}\times\mathbb{N}|=\aleph_0=|\mathbb{N}| }[/math].
שאלה 2. חשבו את עוצמת [math]\displaystyle{ A=\mathbb{Q}\cap[0,1] }[/math].
פתרון
מצד אחד [math]\displaystyle{ A\subseteq\mathbb{Q} }[/math] ולכן [math]\displaystyle{ |A|\leq|\mathbb{Q}|=\aleph_0 }[/math]. מצד שני, הקבוצה [math]\displaystyle{ B=\{\frac{1}{n}:n\in\mathbb{N}\}\subseteq A }[/math] מעוצמה [math]\displaystyle{ \aleph_0 }[/math] (התאמה [math]\displaystyle{ n\mapsto\frac1n }[/math] חד-חד-ערכית), ולכן [math]\displaystyle{ |A|\geq|B|=\aleph_0 }[/math]. לפי ק.ש.ב, [math]\displaystyle{ |A|=\aleph_0 }[/math].
שאלה 3. מה עוצמת האוסף [math]\displaystyle{ F }[/math] של כל תתי-הקבוצות הסופיות של [math]\displaystyle{ \mathbb{N} }[/math]?
פתרון
לכל [math]\displaystyle{ i\in\mathbb{N}\cup\{0\} }[/math] נסמן [math]\displaystyle{ F_i=\{X\subseteq\mathbb{N}:|X|=i\} }[/math] (תתי-הקבוצות בגודל [math]\displaystyle{ i }[/math] בדיוק). כל [math]\displaystyle{ X\in F_i }[/math] נקבע על-ידי פונקציה חד-חד-ערכית מ-[math]\displaystyle{ \{1,\ldots,i\} }[/math] ל-[math]\displaystyle{ \mathbb{N} }[/math], ולכן [math]\displaystyle{ |F_i|\leq\aleph_0^i\leq\aleph_0 }[/math]. מכיוון ש-[math]\displaystyle{ F=\bigcup_{i}F_i }[/math] הוא איחוד בן-מנייה של קבוצות בנות מנייה, [math]\displaystyle{ |F|\leq\aleph_0\cdot\aleph_0=\aleph_0 }[/math]. מנגד [math]\displaystyle{ F }[/math] אינסופית (מכילה את כל הקבוצות בגודל 1), ולכן [math]\displaystyle{ |F|=\aleph_0 }[/math].
שאלה 4. חשבו את [math]\displaystyle{ {\aleph_0}^{\aleph} }[/math].
פתרון
נשתמש בזהות [math]\displaystyle{ \aleph=2^{\aleph_0} }[/math]. מצד אחד, מכיוון ש-[math]\displaystyle{ \aleph_0\leq\aleph }[/math], מתקיים [math]\displaystyle{ {\aleph_0}^{\aleph}\leq{\aleph}^{\aleph}=(2^{\aleph_0})^{\aleph}=2^{\aleph_0\cdot\aleph}=2^{\aleph} }[/math] (השתמשנו בכך ש-[math]\displaystyle{ \aleph_0\cdot\aleph=\aleph }[/math], מכפלה של עוצמות אינסופיות). מצד שני, מכיוון ש-[math]\displaystyle{ \aleph_0\geq2 }[/math], מתקיים [math]\displaystyle{ {\aleph_0}^{\aleph}\geq2^{\aleph} }[/math]. לפי ק.ש.ב, [math]\displaystyle{ {\aleph_0}^{\aleph}=2^{\aleph} }[/math].
טעויות נפוצות
- לחשוב ש-[math]\displaystyle{ |A|\leq|B| }[/math] מחייב שממש [math]\displaystyle{ A\subseteq B }[/math]; בפועל דרוש רק שתקיים פונקציה חד-חד-ערכית כלשהי מ-[math]\displaystyle{ A }[/math] ל-[math]\displaystyle{ B }[/math], גם אם הקבוצות שונות לגמרי במבנה שלהן.
- לחשוב שאם [math]\displaystyle{ |A|\leq|B| }[/math] וגם [math]\displaystyle{ |B|\leq|A| }[/math] אז [math]\displaystyle{ A=B }[/math] ממש כקבוצות. לפי ק.ש.ב מקבלים רק ש-[math]\displaystyle{ |A|=|B| }[/math] (שקילות עוצמה), לא שוויון קבוצות - למשל שתי קבוצות סופיות שונות עם אותו מספר איברים.
- להתייחס לעוצמות אינסופיות כמו למספרים רגילים ולנסות "לחסר": אין פעולת חיסור בין עוצמות (אם הייתה, מ-[math]\displaystyle{ \aleph_0+1=\aleph_0 }[/math] היינו "מקבלים" [math]\displaystyle{ 1=0 }[/math]).
- לחשוב שצריך למצוא דווקא פונקציה "טבעית" או "יפה" כדי להוכיח שקילות עוצמה. כל פונקציה הפיכה, קסומה ככל שתהיה, מספיקה - ולעיתים משתמשים בק.ש.ב במקום להתאמץ למצוא התאמה ישירה בכלל.
- לבלבל בין [math]\displaystyle{ A^B }[/math] (אוסף הפונקציות מ-[math]\displaystyle{ B }[/math] ל-[math]\displaystyle{ A }[/math]) לבין מכפלה קרטזית או בין חזקה של מספרים רגילים; ההגדרה [math]\displaystyle{ a^b=|A^B| }[/math] היא הכללה, ומקרי הקצה ([math]\displaystyle{ a^0=1 }[/math], [math]\displaystyle{ 0^0=1 }[/math]) נובעים ממנה ולא צריך "לשנן" בנפרד.
שאלות ממבחנים
- מועד א' סמסטר א' (חורף) תשפ"ה 2025, שאלה 2.ג — מבחן · פתרון (עוצמת מחלקת השקילות של יחס השקילות מודולו 3 על ℝ (=ℵ0))
- מועד א' סמסטר א' (חורף) תשפ"ה 2025, שאלה 5 — מבחן · פתרון (עוצמת קבוצות פונקציות מ-ℝ ל-ℝ: תמונה⊆ℚ, תמונה=ℝ)
- מועד ב' סמסטר א' (חורף) תשפ"ה 2025, שאלה 2.ב-ג — מבחן · פתרון (עוצמת מחלקת שקילות ועוצמת קבוצת המנה של יחס |a|=|b| על ℝ)
- מועד ב' סמסטר א' (חורף) תשפ"ה 2025, שאלה 5 — מבחן · פתרון (עוצמת קבוצות פונקציות מ-ℝ ל-ℝ עם תמונה נתונה (תמונה={0,1}; תמונה=קבוע יחיד))
- מועד א' קיץ תשפ"ב 2022, שאלה 3ב-ג — מבחן · פתרון (עוצמת קבוצת האיברים המקסימליים והמינימליים ביחס הסדר הנ"ל (סופית, ℵ0 או ℵ))
- מועד א' קיץ תשפ"ב 2022, שאלה 4 — מבחן · פתרון (קס"ח של תתי-הקבוצות בנות-המנייה של R ביחס הכלה: אין איבר מקסימלי, ובניית שרשרת שאינה בת-מנייה לפי עקרון המקסימום של האוסדורף)
- מועד ב' קיץ תשפ"ב 2022, שאלה 3.ב-ג — מבחן · פתרון (עוצמת מחלקת שקילות (רביע במישור, =ℵ) ועוצמת קבוצת המנה (4 רביעים) של היחס S)
- מועד ב' קיץ תשפ"ב 2022, שאלה 5 — מבחן · פתרון (קבוצות 'שבורות מבפנים' (x·y∉ℤ לכל שני איברים שונים) מקסימליות ביחס להכלה - שימוש בעקרון המקסימום של האוסדורף)
- מועד ג' קיץ תשפ"ב 2022, שאלה 3.ב-ד — מבחן · פתרון (עוצמות מחלקות שקילות ב-ℝ×ℝ: לפי מרחק מהראשית (מעגלים), לפי קואורדינטת x (ישרים אנכיים), ולפי חיתוך שני היחסים)
- מועד ג' קיץ תשפ"ב 2022, שאלה 4.ג — מבחן · פתרון (עוצמת קבוצת כל הפונקציות המזגזגות מהטבעיים לטבעיים (=ℵ))
- מועד ג' קיץ תשפ"ב 2022, שאלה 5 — מבחן · פתרון (קבוצות 'ריקות באופן כללי' (חיתוך זוגי לא ריק, חיתוך כללי ריק) מקסימליות - שימוש בעקרון המקסימום של האוסדורף)
- מועד א' קיץ תשפ"א 2021, שאלה 4ד — מבחן · פתרון (חישוב עוצמת התמונה של H (התשובה 2^ℵ) בעזרת חשבון עוצמות וקנטור-שרדר-ברנשטיין)
- מועד א' קיץ תשפ"א 2021, שאלה 5 — מבחן · פתרון (קבוצות "מגניבות" ב-R (הפרש בין איברים אינו רציונלי): קיום קבוצה מגניבה מקסימלית, התאמה חח"ע ועל בין S×Q ל-R, והסקת |S|=ℵ)
- מועד ג' קיץ תשפ"א 2021, שאלה 4ג-ד — מבחן · פתרון (עוצמת קבוצת נקודות השבת של פונקציה במחלקת הזהות (ℵ0), ועוצמת מחלקת השקילות עצמה [I] (ℵ0))
- מועד ג' קיץ תשפ"א 2021, שאלה 5 — מבחן · פתרון (קבוצות "מבודדות" ב-R (x∈A⇒x+1∉A): שרשראות, קיום קבוצה מבודדת מקסימלית לפי עקרון האוסדורף, ועוצמתה ℵ לפי קש"ב)
- מועד ב' קיץ תש"פ 2020, שאלה 5ב-ג — מבחן · פתרון (עוצמת מחלקת שקילות בודדת (1 או ℵ לפי מקרים) ועוצמת קבוצת המנה R×R/R (ℵ) עבור היחס מסעיף 4)
הרשימה המלאה, לפי מבחן ולפי נושא: מתמטיקה בדידה/אינדקס שאלות.
סרטונים
מבוא להגדרות שקילות עוצמה והשוואת עוצמות, כולל הדוגמה של הזוגיים מול הכפולות של 3:
הוכחת משפט קנטור: [math]\displaystyle{ |A|<|P(A)| }[/math], באמצעות קבוצת האיברים שאינם שייכים לתמונת עצמם:
הוכחה שכל תת-קבוצה אינסופית של הטבעיים מעוצמה [math]\displaystyle{ \aleph_0 }[/math] (קבוצות בנות מנייה):
הגדרת חיבור עוצמות, הוכחת אי-התלות בבחירת הנציגות, והדוגמה [math]\displaystyle{ \aleph_0+\aleph_0=\aleph_0 }[/math]:
הגדרת כפל עוצמות והוכחת אי-התלות בבחירת הנציגות:
הוכחה ש-[math]\displaystyle{ |P(A)|=2^{|A|} }[/math] באמצעות פונקציות מציינות:
למת נקודת השבת, השלב המרכזי בהוכחת משפט קנטור-שרדר-ברנשטיין:
הוכחת הקשר [math]\displaystyle{ 2^{\aleph_0}=\aleph }[/math] בין עוצמת הטבעיים לעוצמת הממשיים, ושימושים לחישוב חזקות עוצמה:
