עוצמות[עריכה]

הגדרה. יהיו A,B שתי קבוצות. אזי:

אם קיימת [math]\displaystyle{ f:A\to B }[/math] חח"ע ועל אז אומרים של A ולB יש אותה עוצמה (סימון [math]\displaystyle{ |A|=|B| }[/math])
אם קיימת [math]\displaystyle{ f:A\to B }[/math] חח"ע אז אומרים כי העוצמה של A קטנה או שווה לזו של B. (סימון [math]\displaystyle{ |A|\leq|B| }[/math])
אם [math]\displaystyle{ |A|\leq|B| }[/math] וגם [math]\displaystyle{ |A|\not=|B| }[/math] אזי אומרים כי העוצמה של A קטנה ממש מהעצמה של B (סימון [math]\displaystyle{ |A|\lt |B| }[/math])

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

דוגמא. יהיו A וB שתי קבוצות סופיות. אזי אם מספר האיברים בהן שווה עוצמתן שווה, ואם מספר האיברים בA גדול מזה של B אזי עוצמתה של A גדולה יותר.

לכל קבוצה סופית בעלת n איברים, נאמר שעוצמתה הינה n. למשל [math]\displaystyle{ |\{1,2,3\}|=|\{1,5,100\}| }[/math]

טענה. אם [math]\displaystyle{ A\subseteq B }[/math] אזי [math]\displaystyle{ |A|\leq |B| }[/math].

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

תרגיל[עריכה]

הוכיחו כי [math]\displaystyle{ |P(\mathbb{N})|=|P(\mathbb{N})-\{\emptyset\}| }[/math]

פתרון: נגדיר פונקציה [math]\displaystyle{ f:P(\mathbb{N})\to P(\mathbb{N})-\{\emptyset\} }[/math] ע"י [math]\displaystyle{ \{n\}\mapsto \{n+1\},\emptyset \mapsto \{1\} }[/math] וכל B שאינה נקודון ואינה קבוצה ריקה נשלחת לעצמה.

תרגיל[עריכה]

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

הוכחה: נגדיר [math]\displaystyle{ f:A\to A/R }[/math] ע"י [math]\displaystyle{ f(a)=[a]_R }[/math]. הפונקציה על ולכן [math]\displaystyle{ |A/R|\leq |A| }[/math]

תרגיל[עריכה]

אם [math]\displaystyle{ |A|=|A'|,\;\; |B|=|B'| }[/math] אזי [math]\displaystyle{ |A\times B|=|A'\times B'| }[/math]. באותו אופן עם "קטן שווה".

הוכחה: קיימות פונקציות חח"ע ועל [math]\displaystyle{ f_1:A\to A'.\;\;f_2:B\to B' }[/math]

נגדיר פונקציה [math]\displaystyle{ f:A\times B \to A'\times B' }[/math] ע"י [math]\displaystyle{ (a,b)\mapsto (f_1(a),f_2(b)) }[/math] כיוון ש [math]\displaystyle{ f_1,f_2 }[/math] חח"ע ועל גם [math]\displaystyle{ f }[/math] כזאת.

למשל [math]\displaystyle{ |\mathbb{N} \times \{1,2,3\}|=|(\mathbb{N}\cup\{0\}) \times \{1,5,100\}| }[/math]

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

תרגיל[עריכה]

תהא A קבוצה. הוכח כי [math]\displaystyle{ |A|\leq |P(A)| }[/math]

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

תהא A קבוצה. הוכח כי [math]\displaystyle{ |A|\neq |P(A)| }[/math]

פתרון: נניח בשלילה כי [math]\displaystyle{ |A|= |P(A)| }[/math] אזי קיימת [math]\displaystyle{ f: A\to P(A) }[/math] הפיכה, בפרט על. נגדיר [math]\displaystyle{ X=\{a\in A: a\notin f(a)\} }[/math]. זוהי תת קבוצה של A ולכן, מכיוון ש f על, קיים [math]\displaystyle{ x\in A }[/math] כך ש [math]\displaystyle{ f(x)=X }[/math]. האם [math]\displaystyle{ x\in X }[/math]? אם לא, לפי הגדרת X נקבל כי [math]\displaystyle{ x\notin f(x)=x }[/math] סתירה. אם כן אז [math]\displaystyle{ x\in X=f(x) }[/math] אבל לפי הגדרת X מתקיים [math]\displaystyle{ x\notin f(x) }[/math] סתירה. משל

תרגיל[עריכה]

ראינו בעבר את הדוגמא הבאה: תהי [math]\displaystyle{ A }[/math] קבוצה ותהי תת קבוצה [math]\displaystyle{ B\subseteq A }[/math]. נגדיר יחס [math]\displaystyle{ R\subseteq P(A)\times P(A) }[/math] ע"י:

[math]\displaystyle{ XRY \iff X\cap B=Y\cap B }[/math]

ראינו:

א. [math]\displaystyle{ R }[/math] יחס שקילות.

ב. לכל [math]\displaystyle{ X\subseteq A }[/math] קיימת [math]\displaystyle{ C\subseteq B }[/math] כך ש [math]\displaystyle{ [X]_R=[C]_R }[/math].

ג. אם [math]\displaystyle{ C,D\subseteq B }[/math] שונות, אז [math]\displaystyle{ [C]\neq [D] }[/math].

הוכיחו:

[math]\displaystyle{ |P(A)/R|=|P(B)| }[/math]

פתרון:

נגדיר [math]\displaystyle{ f:P(B)\rightarrow P(A)/R }[/math] ע"י [math]\displaystyle{ f(X)=[X]_R }[/math] לפי א מלעיל הפונקציה על, לפי ב היא חח"ע.

תרגיל[עריכה]

הוכיחו כי [math]\displaystyle{ |A\times A| = |A^{\{1,2\}}| }[/math]

פתרון: הפונקציה [math]\displaystyle{ F:A^{\{1,2\}}\to A\times A }[/math] המוגדרת [math]\displaystyle{ f\mapsto (f(1),f(2)) }[/math] הפיכה.

תרגיל[עריכה]

הוכיחו כי אם [math]\displaystyle{ |A|=|B| }[/math] אזי [math]\displaystyle{ |P(A)|=|P(B)| }[/math]

פתרון: מניחים כי קיימת [math]\displaystyle{ f:A\to B }[/math] הפיכה. נגדיר [math]\displaystyle{ g:P(B)\to P(A) }[/math] ע"י [math]\displaystyle{ B'\mapsto f^{-1}[B'] }[/math] הפיכה לפי מה שעשינו בכיתה ובש.ב..

משפט (קנטור- שרדר-ברנשטיין) אם [math]\displaystyle{ |B|\leq|A| }[/math] וגם [math]\displaystyle{ |A|\leq|B| }[/math] אז [math]\displaystyle{ |B|=|A| }[/math]

[math]\displaystyle{ \aleph_0 }[/math][עריכה]

הגדרה

העוצמה של הטבעיים מסומנת [math]\displaystyle{ \aleph_0 }[/math]
קבוצה A המקיימת [math]\displaystyle{ |A|\leq \aleph_0 }[/math] נקראת בת מנייה (מקור השם כי ניתן למנות/ למספר את האיברים בה ע"י התאמה חח"ע ועל מהטבעיים במקרה האין סופי או במקרה הסופי פשוט למספר עד n)

תרגיל[עריכה]

תהיינה [math]\displaystyle{ A,B }[/math] קבוצות בנות מניה, אזי גם הקבוצות [math]\displaystyle{ A\cap B,A\cup B,A\times B }[/math] בנות מניה.

פתרון[עריכה]

לגבי [math]\displaystyle{ A\times B }[/math] כמו בתרגיל לעיל.

לגבי האיחוד: יש פונקציה חח"ע [math]\displaystyle{ f:A\rightarrow 2\mathbb{N} }[/math], ופונקציה חח"ע [math]\displaystyle{ g:B\rightarrow 2\mathbb{N}-1 }[/math] נגדיר פונקציה [math]\displaystyle{ h:A\cup B\rightarrow \mathbb{N} }[/math] ע"י: [math]\displaystyle{ h(x)=\begin{cases} f(x) & x\in A\\ g(x) & x\in B\smallsetminus A \end{cases} }[/math]

היא חח"ע כמובן.

לגבי החיתוך: הוא מוכל באיחוד ו"קטן שווה" הוא טרנזיטיבי.

עוצמת הממשיים[עריכה]

תרגיל[עריכה]

הוכח כי עוצמת כל הקבוצות הבאות שווה - כל קטעים מהצורה [math]\displaystyle{ [a,b],(a,b),[a,b),(a,b] }[/math] כאשר [math]\displaystyle{ a\lt b }[/math] ממשיים.

פתרון[עריכה]

נראה שכולם שווי עוצמה לקטע [math]\displaystyle{ (0,1) }[/math].

ראשית נגדיר [math]\displaystyle{ f:(0,1)\rightarrow (a,b) }[/math] ע"י [math]\displaystyle{ f(x)=a+(b-a)x }[/math] חח"ע ועל. השאר עם ק.ש.ב.

ט: הקטע [math]\displaystyle{ (\frac{-\pi}{2},\frac{\pi}{2}) }[/math] בעל עוצמה שווה ל [math]\displaystyle{ \mathbb{R} }[/math].

ה: הפונקציה [math]\displaystyle{ tan:(\frac{-\pi}{2},\frac{\pi}{2})\to \mathbb{R} }[/math] הפיכה בתחום הזה ולכן חח"ע ועל.

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

הגדרה: העוצמה של הממשיים מסומנת [math]\displaystyle{ \aleph }[/math].

[עריכה]

טענה. יהיו C,W קבוצות ויהיו [math]\displaystyle{ X,Y\subseteq W }[/math], [math]\displaystyle{ A,B\subseteq C }[/math] תתי קבוצות כך ש [math]\displaystyle{ A\cap B=X\cap Y=\phi }[/math] וגם [math]\displaystyle{ A\cup B = C }[/math] וגם [math]\displaystyle{ X\cup Y = W }[/math]. אזי אם קיימות פונקציות חח"ע ועל [math]\displaystyle{ g:B\rightarrow Y }[/math],[math]\displaystyle{ f:A\rightarrow X }[/math] מתקיים ש [math]\displaystyle{ |C|=|W| }[/math]

הוכחה:

לפי נתון קיימות 2 פונקציות חח"ע ועל [math]\displaystyle{ f_1:A\to X,\;\;f_2:B\to Y }[/math]

נגדיר [math]\displaystyle{ f:C\to W }[/math] ע"י [math]\displaystyle{ f|_A=f_1,\;\;f|_B=f_2 }[/math]. בידקו שאכן f חח"ע ועל.

תרגיל[עריכה]

הוכיחו: [math]\displaystyle{ |\mathbb{Q}\cap [0,1]|=\aleph_0 }[/math]

פתרון[עריכה]

לפי ק.ש.ב. כי מוכל ברציונאליים ומכיל [math]\displaystyle{ \aleph_0 }[/math] שברים מהצורה [math]\displaystyle{ \frac{1}{n} }[/math].

תרגילי העשרה (לא מומלץ להעביר בתירגול)[עריכה]

תרגיל.

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

א. הוכח שעוצמת קבוצה זו הינה אלף אפס

ב. הוכח שקיימת קבוצה של אינסוף עיגולים במרחב ללא חיתוך מעוצמת אלף

פתרון.

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

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

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

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