פתרון: נגדיר פונקציה <math>f:P(\mathbb{N})\to P(\mathbb{N})-\{\emptyset\} </math> ע"י <math>\{n\}\mapsto \{n+1\},\emptyset \mapsto \{1\}</math> וכל B שאינה נקודות ואינה קבוצה ריקה נשלחת לעצמה.
=== תרגיל ===
נסמן <math>A=\{\{n\}\mid n\in \mathbb{N}\}</math> קבוצת הנקודונים הטבעיים. הוכיחו כי <math>|P(\mathbb{N})|=|P(\mathbb{N})-A|</math>
פתרון: נגדיר פונקציה <math>f:P(\mathbb{N})-A\to P(\mathbb{N}) </math> ע"י
<math>\{2n,4n\}\mapsto \{n,2n\},\{2n-1,2(2n-1)\}\mapsto \{n\}</math> וכל B שאינה מהצורה <math>\{k,2k\}</math> נשלחת לעצמה.
=== תרגיל ===
תהא <math>A</math> קבוצה . הוכיחו כי <math>|A^{\mathbb{N}}\times A^{\mathbb{N}}|=|A^{\mathbb{N}}|</math>
פתרון: נגדיר פונקציה <math>F:A^{\mathbb{N}}\times A^{\mathbb{N}}\to A^{\mathbb{N}} </math> ע"י
<math>(f,g)\mapsto \{(2n,f(n)),(2n-1,g(n))\mid n\in \mathbb{N}\}</math>
'''טענה.''' אם A קבוצה וR יחס שקילויות על הקבוצה אזי עוצמת קבוצת המנה קטנה או שווה לעוצמה של A.
אם נסתכל על קבוצה של קבוצות ניתן להגדיר עליה יחס "עוצמות שוות" והוא יהיה יחס רפלקסיבי, סימטרי וטרנזיטיבי. עם זאת, לא ניתן להגדיר יחס זה על כל הקבוצות כולם בשל הסיבה שלא קיימת קבוצת כל הקבוצות.
נראה שימוש בתכונות אלו בתרגילים הבאים.
=== תרגיל ===
תהא <math>(A,\leq)</math> קבוצה סדורה קווית לא סופית. נגיד שתת קבוצה <math>X</math> של <math>A</math> היא תת קבוצה יורדת אם מתקיים
<math>\forall a\in A\forall x\in X \,(a<x) \to (a\in X)</math> (כאשר הסימון <math>a<x</math> פירושו ש <math>a\leq x</math> וגם <math>a\neq x</math>
נסמן ב <math>D</math> את קבוצת כל תתי הקבוצות היורדות של <math>A</math> האם <math>|A|=|D|</math> ?
פתרון: אמרו לי שכן. למה? כי נגדיר פונקציה <math>f:A\to D</math> המוגדרת ע"י <math>f(x)=\{a\in A\mid a<x\}</math> והיא חח"ע ועל.
#מצאו את הטעות בהוכחה.
# האם ואיך אפשר לתקן את הפתרון המוצע?
===תרגיל ===
פתרון: מניחים כי קיימת <math>f:A\to B</math> הפיכה. נגדיר <math>g:P(A)\to P(B)</math> ע"י <math>A'\mapsto f[A']</math> הפיכה.
האם הכיוון ההפוך נכון? אם ידוע <math>|P(A)|=|P(B)|</math> האם ניתן להסיק כי <math>|A|=|B|</math>?
=== תרגיל חשוב! ===
תהא <math>X,Y</math> קבוצות. הוכיחו כי <math>P(Y)^{X}</math> שקולת עוצמה ל <math>P(X\times Y)</math>
תשובה: יש לקחת <math>F(f)=\{(x,y)|y \in f(x)\}</math>
=== תרגיל ===
נגדיר <math>A=\{f\in \mathbb{N}^{\mathbb{N}}\mid \forall n\in \mathbb{N}: \,f(n)<f(n+1)\}</math> הוכיחו כי אם <math>|A|=|\mathbb{N}^{\mathbb{N}}|</math>
פתרון: נגדיר פונקציה <math>F:A\to \mathbb{N}^{\mathbb{N}}</math> ע"י
<math>F(f)(n)=\begin{cases} f(n)-f(n-1) & \text{if }n>1\\
f(1) & \text{if }n=1
\end{cases}</math>
נוכיח כי F חח"ע ועל.
חח"ע: נניח <math>F(f_1)=F(f_2)</math> אזי <math>f_1(1)=F(f_1)(1)=F(f_2)(1)=f_2(1)</math> ואז מהשיוויון
<math>f_1(2)-f_1(1)=F(f_1)(2)=F(f_2)(2)=f_2(2)-f_2(1)</math> נקבל כי <math>f_1(2)=f_2(2)</math> כעת נניח כי <math>f_1(n)=f_2(n)</math> ונוכיח שיוויון בקלט <math>n+1</math>. אכן מהשיוויון <math>f_1(n+1)-f_1(n)=F(f_1)(n+1)=F(f_2)(n+1)=f_2(n+1)-f_2(n)</math> נצמצם את ההנחה כי <math>f_1(n)=f_2(n)</math> ונקבל כי <math>f_1(n+1)=f_2(n+1)</math>
על: תהא <math>g\in \mathbb{N}\to \mathbb{N}</math> נמצא לה מקור. נגדיר <math>f(n)=\sum_{k=1}^ng(k)</math> ואז
<math>F(f)(n)=\begin{cases} f(n)-f(n-1)=g(n) & \text{if }n>1\\
f(1)=g(1) & \text{if }n=1
\end{cases}</math>
ולכן <math>F(f)=g</math>
שאלה: מה היה קורה אם היינו מגדירים את A בעזרת קטן שווה ולא קטן ממש? כלומר
נגדיר <math>A=\{f\in \mathbb{N}^{\mathbb{N}}\mid \forall n\in \mathbb{N}: \,f(n)\leq f(n+1)\}</math> האם <math>|A|=|\mathbb{N}^{\mathbb{N}}|</math> ?
== עוצמת הטבעיים ==
===טענה.===
מתקיים ש <math>|\mathbb{N}|=|\mathbb{N}\times \mathbb{N}|</math>.
'''הוכחה.'''
=== <math>\aleph_0 \cdot \aleph_0=\aleph_0</math> ===
'''הגדרה'''
* העוצמה של הטבעיים מסומנת <math>\aleph_0</math>
* קבוצה A המקיימת <math>|A|\leq \aleph_0 </math> נקראת '''בת מנייה''' (מקור השם כי ניתן למנות/ למספר את האיברים בה ע"י התאמה חח"ע ועל מהטבעיים במקרה האין סופי או במקרה הסופי פשוט למספר עד n )
טענה <math>B=\{2n-1 | n\in \mathbb{N}\}</math> קבוצת האי זוגיים היא בת מנייה
לפי הגדרת f רואים כי <math>(\frac{n}{2^k},k)</math> מקור ל n. וסיימנו.
==== תרגיל ====
הוכיחו כי לכל <math>0<n</math> טבעי מתקיים כי <math>\mathbb{N}^n=\mathbb{N}\times\mathbb{N}\times \cdots \times \mathbb{N} </math> מעוצמה <math>\aleph_0</math>
===משפט (קנטור- שרדר-ברנשטיין)=== אם פתרון: באינדוקציה. בסיס: ברור. צעד: <math>|B\mathbb{N}^{n+1}=|\leqmathbb{N}^n\times \mathbb{N}|A|</math> וגם <math>|A=|\leq|B|</math> אז <math>|Bmathbb{N}\times \mathbb{N}|=|A\mathbb{N}|</math>
==משפט קנטור- שרדר-ברנשטיין==
אם <math>|B|\leq|A|</math> וגם <math>|A|\leq|B|</math> אז <math>|B|=|A|</math>
===תרגיל===
<math>|\mathbb{Q}|=\aleph_0</math>.
====פתרון====
'''טענה.''' מתקיים ש <math>|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Z}\times \mathbb{Z}|</math>.
<math>|\mathbb{N}|=|\mathbb{N}\times \mathbb{N}|=|\mathbb{Z}\times \mathbb{Z}|</math>
כעת, נזכר ש <math> \mathbb{Q}</math> הם קבוצת מנה של <math>\mathbb{Z} \times \mathbb{N}</math>
ולכן
<math>|\mathbb{N}|\leq |\mathbb{Q}|\leq |\mathbb{Z} \times \mathbb{N}|\leq |\mathbb{Z}\times \mathbb{Z}|=|\mathbb{N}| </math>
לפי קנטור ברנשטיין נקבל ש <math>|\mathbb{Q}|= |\mathbb{N}|=\aleph_0</math>.
===תרגיל===
'''הגדרה'''חשבו את עוצמת <math>A=\mathbb{Q}\cap [0,1]</math>.* העוצמה של הטבעיים מסומנת ====פתרון====מצד אחד <math>A\subseteq \mathbb{Q}</math> ולכן <math>|A|\leq \aleph_0</math>.* קבוצה מצד שני, נגדיר <math>B=\{\frac{1}{n}:n\in \mathbb{N}\}\subseteq A המקיימת </math>, קל לראות ש- <math>|A|\leq geq |B|=\aleph_0 </math> נקראת '''בת מנייה''' . לפי ק.ש.ב. סיימנו. ===תרגיל===נסמן <math>A=\{1,2,3,4\}</math>. א. חשבו את עוצמת <math>\{f\in \mathbb{N}^A:f\text{ is 1-1}\}</math>. ב. חשבו את עוצמת <math>\{f\in \mathbb{N}^A:f\text{ is not 1-1}\}</math>. ===תרגיל===נסמן ב-<math>S</math> את קבוצת יחסי השקילות על הטבעיים <math>S=\{R\subseteq \mathbb{N}\times \mathbb{N}:R\text{ is an equivalence relation}\}</math>. א. הראו ש- <math>|S|\leq |P(מקור השם כי ניתן למנות\mathbb{N})|</ למספר math>. ב. נסמן <math>A=\mathbb{N}\smallsetminus \{1,2\}</math>, ונסמן ב-<math>T</math> את האיברים בה אוסף החלוקות של הטבעיים <math>T=\{\mathcal{F}:\mathcal {F} \text{ is a partition of }\mathbb{N}\}</math>. נגדיר <math>f:P(A)\to T</math> ע"י התאמה : <math>f(X)=\{X\cup \{1\},(A\smallsetminus X)\cup \{2\}</math>. הוכיחו שהיא חח"ע ועל מהטבעיים במקרה האין סופי או במקרה הסופי פשוט למספר עד n . ג. הוכיחו <math>|S|=|P(\mathbb{N})|</math>. ===תרגיל===תהיינה <math>A,B,C,D</math> קבוצות כך ש- <math>|A|=|C|,|B|=|D|</math>. הוכיחו: <math>|A^B|=|C^D|</math> ====פתרון====קיימות פונקציות הפיכות <math>f:A\to C,g:B\to D</math>. נגדיר פונקציה <math>\varphi :A^B\to C^D</math> ע"י: <math>\varphi(h)=\{(g(b),f(h(b))\in D\times C:b\in B\}</math>. כלומר, שלחנו פונקציה לקבוצות זוגות סדורים, והיחס המתקבל הוא, מסתבר, פונקציה (דורש הוכחה כמובן). אפשר להסתכל על זה גם באופן הבא: בהינתן פונקציה<math>h:B\to A</math> נשלח אותה לפוננקציה <math>h':D\to C</math> המוגדרת <math>h'(d)=f\circ h\circ g^{-1}(d)</math>. ניתן לראות שהיא חח"ע ועל.
== עוצמת הממשיים==
'''תרגיל ממבחן.'''
א. (ב XI) יהיו A,B קבוצות כך ש <math>|A/B|=|B/A|</math>. הוכח ש <math>|A|=|B|</math>.
ב. מצא קבוצות A וB כך ש <math>|A|=|B|</math> אבל <math>|A/B|\neq |B/A|</math>.
א. בהנתן שמיניה מסוימת באוסף, נבחר נקודה רציונאלית אחת ממעגל אחד, ואחת מהמעגל השני. זה נותן לנו פונקציה מהאוסף אל הזוגות הסדורים של מספרים רציונאליים.
כעת, נוכיח כי פונקציה זו הינה חח"ע. נניח בשלילה כי לשתי שמיניות שונות יש נקודות משותפים בשני המעגלים. אם כן, המעגל של האחת נמצא במעגל של האחרת ולכן גם נקודת ההשקה נמצאת בתוך המעגל האחד. מכיוון שמעגל שהמעגל השני מכיל נקודה משותפת עם המעגל השני של השמיניה השנייה, חייב להיות חיתוך בינהם בסתירה (ציור פה יקל ממש על ההבנה שלכם...).
לכן עוצמת האוסף קטנה מעוצמת הזוגות הסדורים של הרציונאליים, ולמדנו שזוגות סדורים של קבוצה בת מנייה היא קבוצה בת מנייה. לכן עוצמת האוסף קטנה מבת מנייה אבל מכיוון שהיא אינסופית היא גדולה מבת מנייה ולכן בת מנייה כדרוש.
ב. ניקח את אוסף המעגלים עם מרכז בראשית ורדיוס ממשי חיובי. אין בינהם חיתוך, והכמות שלהם זהה לחצי ציר הממשיים והוא כמובן מעוצמת אלף.