'''דוגמא.''' יהיו A וB שתי קבוצות סופיות. אזי אם מספר האיברים בהן שווה עוצמתן שווה, ואם מספר האיברים בA גדול מזה של B אזי עוצמתה של A גדולה יותר.
לכל קבוצה סופית בעלת n איברים, נאמר שעוצמתה הינה n.למשל <math>|\{1,2,3\}|=|\{1,5,100\}|</math>
'''טענה.''' אם <math>A\subseteq B</math> אזי <math>|A|\leq |B|</math>.
הוכחה: נגדיר <math>f:A\to B </math> פונקצית ההכלה השולחת כל איבר לעצמו. פונקציה זו חח"ע ולכן <math>|A|\leq|B|</math>
'''===תרגיל''' ===הוכח כי עוצמת <math>\mathbb{N}</math> שווה ל -<math>\mathbb{N}\cup\{0\}</math>
הוכחה: נגדיר <math>f:\mathbb{N}\to \mathbb{N}\cup\{0\} </math> ע"י <math>f(n)=n-1 </math>.
<math>f</math> חח"ע ועל כי יש לה הופכית <math>g(n)=n+1\;\;\;\;\;g:\mathbb{N}\cup\{0\} \to \mathbb{N}</math>
=== תרגיל ===
הוכיחו כי <math>|P(\mathbb{N})|=|P(\mathbb{N})-\{\emptyset\}|</math>
פתרון: נגדיר פונקציה <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>f:A\to A/R </math> ע"י <math>f(a)=[a]_R</math>. הפונקציה על ולכן <math> |A/R|\leq |A| </math>
'''טענה''' אם <math>|A|=|A'|,\;\; |B|=|B'|</math> אזי <math>|A\times B|=|A'\times B'|</math>
הוכחה: קיימות פונקציות חח"ע ועל <math>f_1:A\to A'.\;\;f_2:B\to B'</math>
נגדיר פונקציה <math>f:A\times B \to A'\times B'</math> ע"י <math>(a,b)\mapsto (f_1(a),f_2(b))</math>
כיוון ש <math>f_1,f_2</math> חח"ע ועל גם <math>f</math> כזאת.
למשל <math>|\mathbb{N} \times \{1,2,3\}|=|(\mathbb{N}\cup\{0\}) \times \{1,5,100\}|</math>
'''הערה'''
אם נסתכל על קבוצה של קבוצות ניתן להגדיר עליה יחס "עוצמות שוות" והוא יהיה יחס רפלקסיבי, סימטרי וטרנזיטיבי. אם עם זאת, לא ניתן להגדיר יחס זה על כל הקבוצות כולם בשל הסיבה שלא קיימת קבוצת כל הקבוצות.
נראה שימוש בתכונות אלו בתרגילים הבאים.
=== תרגיל ===תהא <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> והיא חח"ע ועל. #מצאו את הטעות בהוכחה. # האם ואיך אפשר לתקן את הפתרון המוצע? ===תרגיל ===תהא A קבוצה. הוכח כי <math>|A|\leq |P(A)|</math> פתרון: נגדיר את הפונקציה <math>f:A|\to P(A)</math> ע"י <math>a \mapsto \{a\}</math> היא חח"ע. תהא A קבוצה. הוכח כי <math>|A|\neq |P(A)|</math> פתרון: נניח בשלילה כי <math>|A|= |P(A)|</math> אזי קיימת <math>f: A\to P(A)</math> הפיכה, בפרט על. נגדיר <math>X=\{a\in A: a\notin f(a)\}</math>. זוהי תת קבוצה של A ולכן, מכיוון ש f על, קיים <math>x\in A</math> כך ש <math>f(x)=X</math>. האם <math>x\in X</math>? אם לא, לפי הגדרת X נקבל כי <math>x\notin f(x)=x</math> סתירה. אם כן אז <math>x\in X=f(x)</math> אבל לפי הגדרת X מתקיים <math>x\notin f(x)</math> סתירה. משל ===תרגיל ===נגדיר <math>A=\{f: \{1,2,3\}\to \{1,2,3,4,5\} : f \text{ is a function}\}, B=\{(x,y,z): 1\leq x,y,z \leq 5\}</math> הוכח כי A ו B שוות עוצמה פתרון: נגדיר פונצקיה <math>F:A\to B</math> ע"י <math>f\mapsto (f(1),f(2),f(3))</math>. הוכיחו/השתכנעו/נסביר <math>F</math> חח"ע ועל ===תרגיל ===הוכיחו כי <math>|A\times A| = |A^{\{1,2\}}|</math> פתרון: הפונקציה <math>F:A^{\{1,2\}}\to A\times A</math> המוגדרת <math>f\mapsto (f(1),f(2))</math> הפיכה. === תרגיל ===הוכיחו כי אם <math>|A|=|B|</math> אזי <math>|P(A)|=|P(B)|</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{Z},\mathbb{Q}</math>
'''===טענה.''' ===מתקיים ש <math>|\mathbb{N}|=|\mathbb{N}\times \mathbb{N}|</math>.
'''הוכחה.'''
כמו כן קל לראות שפונקציה זו חח"ע וגם על.
'''משפט (קנטור- שרדר-ברנשטיין)''' אם <math>|B|\leq|A|</math> וגם <math>|A|\leq|B|</math> אז <math>|B|=|A|</math> '''טענה.''' מתקיים ש <math>|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Z}\times \mathbb{Z}|</math>. הוכחה: נגדיר <math>f:\mathbb{Z}aleph_0 \to cdot \mathbb{N}\times \{0,1aleph_0=\}aleph_0</math> ע"י <math>f(z)=(|z|,sgn(z))</math>.פונקציה זו חח"ע ולכן<math>|\mathbb{N}|\leq |\mathbb{Z}|\leq|\mathbb{Z}\times \mathbb{Z}|\leq|(\mathbb{N}\times \{0,1\})\times (\mathbb{N}\times \{0,1\})| \leq |(\mathbb{N}\times \mathbb{N})\times (\mathbb{N}\times \mathbb{N})|= |\mathbb{N}\times \mathbb{N}|= |\mathbb{N}| </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}|</math>
'''הגדרה'''
* העוצמה של הטבעיים מסומנת <math>\aleph_0</math>
* קבוצה A המקיימת <math>|A|\leq \aleph_0 </math> נקראת '''בת מנייה''' (מקור השם כי ניתן למנות/ למספר את האיברים בה ע"י התאמה חח"ע ועל מהטבעיים במקרה האין סופי או במקרה הסופי פשוט למספר עד n )
טענה <math>B== עוצמת הממשיים==\{2n-1 | n\in \mathbb{N}\}</math> קבוצת האי זוגיים היא בת מנייה
'''תרגיל''' הוכחה : נגדיר פונצקיה <math>f:\mathbb{N}\to B </math> ע"י <math>n\mapsto 2n-1</math>
הוכח כי עוצמת כל הקבוצות הבאות שווה - כל קטעים מהצורה טענה <math>[a,b],(a,b),[a,b),(a,b]C=\mathbb{N}\cup\{0\}</math> כאשר קבוצת הטבעיים עם <math>a<b</math> ואפשר כי <math>a=-\infty , b=\infty0</math>בת מנייה
הוכחה:קל לראות כי כל הקטעים הסופיים מהצורה נגדיר פונצקיה <math>[a,b]f:\mathbb{N}\to C </math>. בעלי אותה עוצמה ע"י הפונקציה<math>n\mapsto n-1</math>
[[קובץ:EqveOfTowIntervals.jpeg]]טענה <math>\aleph_0 \cdot \aleph_0=\aleph_0</math>
באותו אופן כל הקטעים הסופיים מהצורה הוכחה: נגדיר <math>(a,b)f:B\times C\to \mathbb{N}</math> או ע"י <math>(ax,b]</math> או <math>[a,bk)\mapsto x\cdot 2^k</math> בעלי אותה עוצמה (כל הקטעים מאותו "סוג")
נמשיך- טטענה: הקטע <math>[0,1]</math> בעל עוצמה שווה ל <math>[0,1)</math>. ה: נגדיר <math>f:[0,1)\rightarrow [0,1]</math> על ידי:חח"ע
*אם הוכחה נניח <math>\nexists n\in\mathbb{N}:xf(x_1,k_1)=\frac{1}{n}f(x_2,k_2)</math> אזי נגדיר <math>f(x)x_1 \cdot 2^{k_1} =xx_2 \cdot 2^{k_2}</math>
*אחרת נגדיר בה"כ <math>f(k_1\frac{1}{n})=\frac{1}leq k_2</math> ונחלק את שני האגפים ב <math>2^{n-1k_1}</math>
למעשהנקבל כי<math>x_1 =x_2 \cdot 2^{k_2-k_1}</math>. כעת צד שמאל לא מתחלק ב 2 (כי <math>x_1</math> אי זוגי) ולכן גם אגף ימין לא מתחלק ב -2. הדבר יכול לקרות רק אם <math>k_2-k_1=0</math> או במילים אחרות <math>k_1=k_2</math>. כעת קיבלנו גם כי <math>x_1=x_2</math> ולכן בס"ה <math>(x_1, כל מספר כמעט נשלח לעצמו פרט לסדרה הבת מנייה k_1)=(x_2,k_2)</math>.
<math>\frac{1}{2},\frac{1}{3},\frac{1}{4},...</math> טענה: f על
הנשלחת לסדרה הוכחה: יהא n טבעי. יהיה <math>k\in C</math> כך ש <math>2^k</math> מחלק את n ואילו <math>2^{k+1}</math> אינו מחלק את n. כלומר החזקה הגדולה ביותר של 2 בפירוק של n למכפלת ראשונים זרים.
מהגדרת k נובע כי <math>\frac{1n}{12^k},\frac{1}{</math> אי זוגי (כי אחרת הוא זוגי ואז 2},\fracמחלק את המספר ואז <math>2^{k+1}{3},...</math>מחלק את n. סתירה).
זה פונקציה חח"ע ועללפי הגדרת f רואים כי <math>(\frac{n}{2^k},k)</math> מקור ל n. וסיימנו.
הערה: אותה פונקציה מוכיחה ==== תרגיל ====הוכיחו כי הקטע לכל <math>(0,1]<n</math> בעל עוצמה שווה ל טבעי מתקיים כי <math>(0,1)\mathbb{N}^n=\mathbb{N}\times\mathbb{N}\times \cdots \times \mathbb{N} </math> מעוצמה <math>\aleph_0</math>.
טפתרון: באינדוקציה. בסיס: ברור. צעד: הקטע <math>(-|\mathbb{N}^{n+1,0]}=|\mathbb{N}^n\times \mathbb{N}|=|\mathbb{N}\times \mathbb{N}|=|\mathbb{N}|</math> בעל עוצמה שווה ל <math>[0,1)</math>.
ה: ע"י הפונקציה ==משפט קנטור- שרדר-ברנשטיין==אם <math>f(x)|B|\leq|A|</math> וגם <math>|A|\leq|B|</math> אז <math>|B|=-x|A|</math>
ט: הקטע ===תרגיל===<math>(|\fracmathbb{-\piQ}{2},|=\frac{\pi}{2})</math> בעל עוצמה שווה ל <math>\mathbb{R}aleph_0</math>.
ה: הפונקציה ====פתרון===='''טענה.''' מתקיים ש <math>tan:(|\fracmathbb{-\piN}{2},|=|\fracmathbb{\piZ}|=|\mathbb{2Z})\to times \mathbb{RZ}|</math> הפיכה בתחום הזה ולכן חח"ע ועל.
לסיום נעיר כי כל קרן (קטע עם צד אחד אין סופי) ג"כ בעלת אותה עוצמה כי היא מכילה איזה שהוא קטע ומוכלת בממשיים ולכן עפ"י קנטור ברנשטיין בעלת אותה עוצמה.הוכחה: כיוון ש <math>|\mathbb{N}|=|\mathbb{Z}|</math> אזי לפי תרגיל ממקודם <math>|\mathbb{N}|=|\mathbb{N}\times \mathbb{N}|=|\mathbb{Z}\times \mathbb{Z}|</math>
'''הגדרה''': העוצמה כעת, נזכר ש <math> \mathbb{Q}</math> הם קבוצת מנה של הממשיים מסומנת <math>\alephmathbb{Z} \times \mathbb{N}</math>.ולכן
=== <math>|\aleph_0<mathbb{N}|\alephleq |\mathbb{Q}|\leq |\mathbb{Z} \times \mathbb{N}|\leq |\mathbb{Z}\times \mathbb{Z}|=|\mathbb{N}| </math>. ===
==השוואות עוצמות=='''תרגיל.''' נביט באוסף כל הסדרות הבינאריות (01110010101011011...). נתאר אוסף זה באופן מדוייק: לפי קנטור ברנשטיין נקבל ש <math>B=|\mathbb{f:Q}|= |\mathbb{N}|=\rightarrow \{0,1\}\}aleph_0</math>. השווה בין העוצמה של B לבין אלף אפס.
'''פתרון.'''קיימת פונקציה על מהסדרות אל המספרים הטבעיים: נשלח כל סדרה שהחל ממקום מסויים היא קבועה אפס אל המספר שהיא מייצגת בבסיס בינארי. כל סדרה אחרת נשלח לאחד. (שימו לב שאת הסדרה הקבועה אפס נשלח גם לאחד לפי הגדרה...).===תרגיל===
לכן חשבו את עוצמת B גדולה או שווה לאלף אפס. נוכיח כי היא גדולה ממש<math>A=\mathbb{Q}\cap [0,1]</math>.
נניח בשלילה שקיימת פונקציה g חח"ע ועל מהטבעיים אל B====פתרון====מצד אחד <math>A\subseteq \mathbb{Q}</math> ולכן <math>|A|\leq \aleph_0</math>. לכן ניתן "לסדר" את כל הסדרות אחת אחרי השנייה:
מצד שני, נגדיר <math>g(B=\{\frac{1)}{n}:n\in \mathbb{N}\}\subseteq A</math>, קל לראות ש- <math>|A|\geq |B|=0101010110110101001000100101...\aleph_0</math>.
<math>g(2)=1101010001010010100010101010לפי ק.ש.ב. סיימנו.</math>
===תרגיל===נסמן <math>g(3)A=0101010101011101010001010111...\{1,2,3,4\}</math>.
א. חשבו את עוצמת <math>\{f\in \mathbb{N}^A:f\text{ is 1-1}\}</math>.
נבנה סדרה בינארית שקיימת בB אך לא ייתכן שהיא מתקבלת על ידי הפונקציה g (כלומר היא אינה בסדרה, בסתירה)ב. חשבו את עוצמת <math>\{f\in \mathbb{N}^A:f\text{ is not 1-1}\}</math>.
נגדיר את הפונקציה f שנותנת ===תרגיל===נסמן ב-<math>S</math> את הסדרה קבוצת יחסי השקילות על הטבעיים <math>S=\forall n{R\insubseteq \mathbb{N}\times \mathbb{N}:f(n)= R\neg g(n)_ntext{ is an equivalence relation}\}</math>. כלומר לקחנו סדרה שהאיבר הראשון שלה שונה מהאיבר הראשון של הסדרה הראשונה, האיבר השני שונה מהאיבר השני של הסדרה השנייה וכן הלאה.
בדוגמא לעיל הסדרה תתחיל בשלושת האיברים א. הראו ש- <math>101|S|\leq |P(\mathbb{N})|</math> ולכן בוודאי לא תהיה אף אחת משלוש הסדרות הראשונות.
באופן כלליב. נסמן <math>A=\mathbb{N}\smallsetminus \{1, לא ייתכן שסדרה זו נמצאת במקום k כלשהו בסדרת הסדרות2\}</math>, כי האיבר הונסמן ב-k שלה שונה מהאיבר ה-k <math>T</math> את אוסף החלוקות של הסדרה ה-kהטבעיים <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>. הוכיחו שהיא חח"ע.
ג. הוכיחו <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\alephto 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>. ניתן לראות שהיא חח"ע ועל.
'''טענה.''' יהיו C,W קבוצות ויהיו <math>X,Y\subseteq W</math>, <math>A,B\subseteq C</math> תתי קבוצות כך ש <math>A\cap B=X\cap Y=\phi</math> וגם <math>A\cup B עוצמת הממשיים= C</math> וגם <math>X\cup Y = W</math>. אזי אם קיימות פונקציות חח"ע ועל <math>g:B\rightarrow Y</math>,<math>f:A\rightarrow X</math> מתקיים ש <math>|X|=|Y|</math>
'''תרגיל'''
'''תרגיל.''' הוכח שעוצמת הקטע כי עוצמת כל הקבוצות הבאות שווה - כל קטעים מהצורה <math>[0a,1b],(a,b),[a,b),(a,b]</math> זהה לעוצמת הקטע כאשר <math>[0a<b</math> ואפשר כי <math>a=-\infty ,1)b=\infty</math>
'''פתרוןהוכחה:קל לראות כי כל הקטעים הסופיים מהצורה <math>[a,b]</math>.'''בעלי אותה עוצמה ע"י הפונקציה
אמנם זה נובע מתכונות אחרות אשר נלמדות בהרצאה ובשיעורי הבית, אך בכל זאת נמצא פונקציה חח"ע בין שתי הקבוצות הללו[[קובץ:EqveOfTowIntervals.jpeg]]
'''הערה''': אפשר לעבור מכאן לק.ש.ב. ולא צריך את כל הפונקציות. באותו אופן כל הקטעים הסופיים מהצורה <math>(a,b)</math> או <math>(a,b]</math> או <math>[a,b)</math> בעלי אותה עוצמה (כל הקטעים מאותו "סוג") נמשיך- ט: הקטע <math>[0,1]</math> בעל עוצמה שווה ל <math>[0,1)</math>. ה: נגדיר <math>gf:[0,1)\rightarrow [0,1]</math> על ידי:
*אם <math>\nexists n\in\mathbb{N}:x=\frac{1}{n}</math> אזי נגדיר <math>f(x)=x</math>
<math>\frac{1}{1},\frac{1}{2},\frac{1}{3},...</math>.
זה פונקציה חח"ע ועל.
כך בעצם הוספנו את אחד לסדרה בת מנייה המוכלת בקטע. שימו לב שבכל קבוצה אינסופית קיימת תת קבוצה מעוצמת הערה: אותה פונקציה מוכיחה כי הקטע <math>\aleph_0(0,1]</math>. אפשר כך להוכיח, למשל, שאוסף הממשיים ללא המספרים השלמים הזוגיים הוא מאותה בעל עוצמה כמו אוסף הממשיים כולושווה ל <math>(0,1)</math>.
ט: הקטע <math>(קל להוכיח שהפונקציה שתארנו לעיל הינה חח"ע ועל.-1,0]</math> בעל עוצמה שווה ל <math>[0,1)</math>.
ה: ע"י הפונקציה <math>f(x)=-x</math>
'''תרגילט: הקטע <math>(\frac{-\pi}{2},\frac{\pi}{2})</math> בעל עוצמה שווה ל <math>\mathbb{R}</math>.''' הוכח שעוצמת קטע סופי בממשיים זהה לעוצמת כל הממשיים
'''הוכחה.''' קל מאד להראות שכל הקטעים הסופיים מאותה עוצמה, לכן מספיק להוכיח עבור קטע ספציפי. ניקח את ה: הפונקציה <math>ftan:(x)=\frac{1-\pi}{x2}</math> בקטע <math>(0,1]</math> התמונה שלה הינה <math>[1,\inftyfrac{\pi}{2})\to \mathbb{R}</math>. למעשה סיימנו פה את החלק העיקרי בתרגיל, שכן הפכנו קטע סופי לקטע אינסופי, כל שנותר לעשות הוא להשלים את מה שבנינו לפונקציה מקטע סופי לכל הממשייםהפיכה בתחום הזה ולכן חח"ע ועל.
לסיום נעיר כי כל קרן (קטע עם צד אחד אין סופי) ג"כ בעלת אותה עוצמה כי היא מכילה איזה שהוא קטע ומוכלת בממשיים ולכן עפ"י קנטור ברנשטיין בעלת אותה עוצמה.
ניקח פונקציה g השולחת את הקטע '''הגדרה''': העוצמה של הממשיים מסומנת <math>(\frac{1}{2},1]</math> לקטע <math>(0,1]</math>, על ידי <math>g(x)=2x-1</math> ומשם נעביר לקטע האינסופי על ידי f. את הקטע <math>[0,\frac{1}{2}]</math> היא שולחת לקטע <math>[0,1]</math> על ידי 2x. סה"כ הגענו לחצי הישר <math>[0,\infty)aleph</math>.
באופן דומה נשלח את === תרגיל ===הוכיחו כי <math>(-0,1,0)</math> לקטע <math>\cup (-\infty3,04)</math> וסה"כ קיבלנו פונקציה חח"ע ועל מקטע סופי לכל ציר הממשיים.שווה עוצמה לממשיים
פתרון: הוא מוכל בממשיים ומכיל את <math>(0,1)</math>
=== עוצמת הטבעיים קטנה ממש מעוצמת הממשיים ===
לשם הוכחת הטענה נשתמש בקבוצה המספרים <math>[0,1)</math> בכתיב עשרוני כלומר כל <math>x\in[0,1)</math>
הוא מהצורה <math>x=0.a_1a_2a_3...</math> כאשר <math>\forall i : a_i\in \{0,1\dots 9\}</math>
לשם נוחות התרגיל נזהה את x עם פונקציה <math>f:\mathbb{N}\to \{0,1\dots 9\}</math> המוגדרת <math>f(i)=a_i</math>
ט: <math>\aleph_0\leq\aleph</math>
'''תרגיל.''' ראינו ש ה: נגדיר פונקציה <math>|g=\mathbb{N}|\to [0,1)=|\{f:\mathbb{N}\timesto \mathbb{N0,1\dots 9\}\}|</math>. האם אותו דבר נכון גם לגבי הממשיים?
'''הוכחה.'''ע"י <math>\forall n\in \mathbb{N}:g(n)=e_n(m)=\delta_{n,m}</math> למשל 17 נשלח לפונקציה ששווה 0 בכל מקום פרט ל-17 ששם היא שווה 1
נניח שכל איבר ממשי הוא בעצם סדרה אינסופית של ספרות ממשיות (כולל אלו שלפני ואחרי הנקודה). נפרק כל סדרה כזו לשתי תתי סדרות - סדרת הזוגיים וסדרת האי זוגיים. כל תת סדרה שכזו מגדירה מספר ממשי, לכן שלחנו מספר ממשי בודד לזוג מספרים ממשייםקל לראות כי g חח"ע.
העתקה זו כעת נניח בשלילה כי <math>\aleph_0=\aleph</math> אזי יש פונקציה חח"ע ועל פרט לעובדה שהממשיים הם לא '''בדיוק''' אוסף הסדרות של ספרות עשרוניות<math>g=\mathbb{N}\to [0, אבל לא נתמודד כרגע עם הקושי המינורי הזה1)=\{f:\mathbb{N}\to \{0,1\dots 9\}\} </math>נסמן <math>g(n)=f_n</math>.נראה כי g אינה על ע"י שנבנה פונקציה f שאין לה מקור:
נגדיר <math>f(n)=1</math> אם <math>f_n(n)=0</math> ו <math>f(n)=0</math> אחרת.
כעת לכל n <math>f_n\not=f</math> כי <math>f_n(n)\not=f(n)</math> עפ"י הגדרת f. סתירה לכל ש g על.
'''תרגיל ממבחןהערה: הזיהוי <math> [0,1)=\{f:\mathbb{N}\to \{0,1\dots 9\}\} </math> אינו מדויק כי <math>0.01=0.00999...</math>ולכן צריך להשלח לאותה פונקציה. נשאיר כתרגיל את דיוק ההוכחה.'''
א== =='''טענה. ''' יהיו C,W קבוצות ויהיו <math>X,Y\subseteq W</math>, <math>A,B \subseteq C</math> תתי קבוצות כך ש <math>|A\cap B=X\cap Y=\phi</math> וגם <math>A\cup B|=|C</math> וגם <math>X\cup Y = W</math>. אזי אם קיימות פונקציות חח"ע ועל <math>g:B\rightarrow Y</math>,<math>f:A|\rightarrow X</math>. הוכח מתקיים ש <math>|AC|=|BW|</math>.
ב. מצא קבוצות A וB כך ש <math>|A|=|B|</math> אבל <math>|A/B|\neq |B/A|</math>.הוכחה:
לפי נתון קיימות 2 פונקציות חח"ע ועל <math>f_1:A\to X,\;\;f_2:B\to Y</math>
'''פתרוןנגדיר <math>f:C\to W</math> ע"י <math>f|_A=f_1,\;\;f|_B=f_2</math>. בידקו שאכן f חח"ע ועל.'''
א. לפי הנתון קיימת פונקציה חח"ע ועל f בין A/B לבין B/A. נגדיר פונקציה g מ-A לB'''תרגיל ממבחן.'''
אם <math>א.(a\in ב XI) יהיו A) \and (a\notin ,B) קבוצות כך ש </math> אזי נגדיר <math>g(a)|A/B|=f(a)|B/A|</math>. אם הוכח ש <math>(a\in |A) \and (a\in |=|B) |</math>, נגדיר <math>g(a)=a</math>. נותר להוכיח כי g הינה חח"ע ועל.
על: לכל איבר בB או שהוא בA או שלאב. אם לא, אזי מכיוון מצא קבוצות A וB כך ש<math>f|A|=|B|</math> אבל <math>|A/B|\neq |B/A|</math> על, יהיה לו מקור מתוך האיברים בA שאינם בB. אם הוא כן בA הוא ישלח לעצמו.
חח"ע: נניח בשלילה ששני איברים נשלחים לאותו מקום. באופן ברור זה דורש שאחד מהם יהיה בB ואחד לא. אם כן, האיבר שנמצא בB נשלח לעצמו ולכן גם השני נשלח לשם בסתירה לכך שהוא צריך להשלח לאיבר שאינו בA.
'''פתרון.'''
בא. ניקח את הטבעיים, ואת הטבעיים לאחר שזרקנו מהם את אחד. ברור שנשארנו עם קבוצות שוות עוצמה, אבל ההפרשים בינהם הם מתקיים <math>A=(A\{1cap B)\}cup A/B,\phi;\; B=(A\cap B)\cup B/A</math> לפי נתון <math>|A/B|=|B/A|</math> ואלו קבוצות מעוצמה שונה.כיוון ש <math>|A\cap B|=|A\cap B|</math> לפי תרגיל קודם סימנו.
ב. ניקח את הטבעיים, ואת הטבעיים לאחר שזרקנו מהם את אחד. ברור שנשארנו עם קבוצות שוות עוצמה, אבל ההפרשים בינהם הם <math>\{1\},\phi</math> ואלו קבוצות מעוצמה שונה.
== '''תרגילי העשרה''' (לא מומלץ להעביר בתירגול) ==
'''תרגיל.'''
נגדיר "שמיניה" בתור זוג עיגולים מעגלים בגדלים כלשהם המשיקים זה לזה בנקודה כלשהי. יהי אוסף אינסופי כלשהו של שמיניות במישור הזרות זו מזו (כלומר אין שתים עם נקודת חיתוך משותפת)
א. הוכח שעוצמת קבוצה זו הינה אלף אפס
ב. הוכח שקיימת קבוצה של אינסוף עיגולים מעגלים במרחב ללא חיתוך מעוצמת אלף
'''פתרון.'''
א. בהנתן שמיניה מסוימת באוסף, נבחר נקודה רציונאלית אחת מעיגול ממעגל אחד, ואחת מהעיגול מהמעגל השני. זה נותן לנו פונקציה מהאוסף אל הזוגות הסדורים של מספרים רציונאליים.
כעת, נוכיח כי פונקציה זו הינה חח"ע. נניח בשלילה כי לשתי שמיניות שונות יש נקודות משותפים בשני העיגוליםהמעגלים. אם כן, העיגול המעגל של האחת נמצא בעיגול במעגל של האחרת ולכן גם נקודת ההשקה נמצאת בתוך העיגול המעגל האחד. מכיוון שהעיגול שהמעגל השני מכיל נקודה משותפת עם העיגול המעגל השני של השמיניה השנייה, חייב להיות חיתוך בינהם בסתירה (ציור פה יקל ממש על ההבנה שלכם...).
לכן עוצמת האוסף קטנה מעוצמת הזוגות הסדורים של הרציונאליים, ולמדנו שזוגות סדורים של קבוצה בת מנייה היא קבוצה בת מנייה. לכן עוצמת האוסף קטנה מבת מנייה אבל מכיוון שהיא אינסופית היא גדולה מבת מנייה ולכן בת מנייה כדרוש.
ב. ניקח את אוסף העיגולים המעגלים עם מרכז בראשית ורדיוס ממשי חיובי. אין בינהם חיתוך, והכמות שלהם זהה לחצי ציר הממשיים והוא כמובן מעוצמת אלף.