תרגול 8 מדמח קיץ תשעז

חזרה למערכי התרגול

עוצמות

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

• אם קיימת $f:A\to B$ חח"ע ועל אז אומרים של A ולB יש אותה עוצמה (סימון $|A|=|B|$)
• אם קיימת $f:A\to B$ חח"ע אז אומרים כי העוצמה של A קטנה או שווה לזו של B. (סימון $|A|\leq|B|$)
• אם $|A|\leq|B|$ וגם $|A|\not=|B|$ אזי אומרים כי העוצמה של A קטנה ממש מהעצמה של B (סימון $|A|<|B|$)

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

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

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

טענה. אם $A\subseteq B$ אזי $|A|\leq |B|$.

הוכחה: נגדיר $f:A\to B$ פונקצית ההכלה השולחת כל איבר לעצמו. פונקציה זו חח"ע ולכן $|A|\leq|B|$

תרגיל

הוכיחו כי $|P(\mathbb{N})|=|P(\mathbb{N})-\{\emptyset\}|$

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

תרגיל

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

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

תרגיל

אם $|A|=|A'|,\;\; |B|=|B'|$ אזי $|A\times B|=|A'\times B'|$. באותו אופן עם "קטן שווה".

הוכחה: קיימות פונקציות חח"ע ועל $f_1:A\to A'.\;\;f_2:B\to B'$

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

למשל $|\mathbb{N} \times \{1,2,3\}|=|(\mathbb{N}\cup\{0\}) \times \{1,5,100\}|$

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

תרגיל

תהא A קבוצה. הוכח כי $|A|\leq |P(A)|$

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

תהא A קבוצה. הוכח כי $|A|\neq |P(A)|$

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

תרגיל

ראינו בעבר את הדוגמא הבאה: תהי $A$ קבוצה ותהי תת קבוצה $B\subseteq A$. נגדיר יחס $R\subseteq P(A)\times P(A)$ ע"י:

$XRY \iff X\cap B=Y\cap B$

ראינו:

א. $R$ יחס שקילות.

ב. לכל $X\subseteq A$ קיימת $C\subseteq B$ כך ש $[X]_R=[C]_R$.

ג. אם $C,D\subseteq B$ שונות, אז $[C]\neq [D]$.

הוכיחו:

$|P(A)/R|=|P(B)|$

פתרון:

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

תרגיל

הוכיחו כי $|A\times A| = |A^{\{1,2\}}|$

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

תרגיל

הוכיחו כי אם $|A|=|B|$ אזי $|P(A)|=|P(B)|$

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

משפט (קנטור- שרדר-ברנשטיין) אם $|B|\leq|A|$ וגם $|A|\leq|B|$ אז $|B|=|A|$

$\aleph_0$

הגדרה

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

תרגיל

תהיינה $A,B$ קבוצות בנות מניה, אזי גם הקבוצות $A\cap B,A\cup B,A\times B$ בנות מניה.

פתרון

לגבי $A\times B$ כמו בתרגיל לעיל.

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

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

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

עוצמת הממשיים

תרגיל

הוכח כי עוצמת כל הקבוצות הבאות שווה - כל קטעים מהצורה $[a,b],(a,b),[a,b),(a,b]$ כאשר $a<b$ ממשיים.

פתרון

נראה שכולם שווי עוצמה לקטע $(0,1)$.

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

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

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

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

הגדרה: העוצמה של הממשיים מסומנת $\aleph$.

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

הוכחה:

לפי נתון קיימות 2 פונקציות חח"ע ועל $f_1:A\to X,\;\;f_2:B\to Y$

נגדיר $f:C\to W$ ע"י $f|_A=f_1,\;\;f|_B=f_2$. בידקו שאכן f חח"ע ועל.

תרגיל

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

פתרון

לפי ק.ש.ב. כי מוכל ברציונאליים ומכיל $\aleph_0$ שברים מהצורה $\frac{1}{n}$.

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

תרגיל.

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

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

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

פתרון.

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

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

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

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