'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
==אריתמטיקה של עוצמות==
'''הגדרה''' יהיו A,B קבוצות אזי <math>A^B:=\{f:B\rightarrow A\}</math>. ===תרגיל===יהיו A,B,C קבוצות כך ש <math>|A|\leq |B|</math>.הוכיחו כי <math>|A^C|\leq|B^C|</math>. פתרון: נתון שקיימת <math>f:A\to B</math> חח"ע. נגדיר <math>g:A^C\to B^C</math> ע"י <math>h:C\to A\mapsto f\circ h</math>. מתקיים כי g חח"ע כי f חח"ע ויש לה הפיכה שמאלית. הערה: <math>|A|< |B|</math> ''' לא''' גורר <math>|A^C|<|B^C|</math>. ===תרגיל===הוכח שעוצמת קבוצת החזקה של A תמיד גדולה מעוצמתה של A '''הוכחה.''' יש התאמה חח"ע ועל <math>g:P(A)\to \{0,1\}^A</math> ע"י <math>\forall B\subseteq A : g(B)=f_B=\chi_B</math> לפי תרגיל קודם <math>|A|<|\{0,1\}^A|=|P(A)|</math> '''הערה: (למי שלמד תורת הקבוצות)''' מסיבה זו אוסף העוצמות אינו קבוצה אלא מחלקה. שכן אם הוא היה קבוצה, הייתה לו עוצמה ===תרגיל===יהיו A,B קבוצות כך ש, עוצמת <math>|B גדולה מאחד|>1</math>. הוכח כי העוצמה של אוסף הפונקציות מA לB גדולה מעוצמת <math>|A|<|B^A|</math>.
'''פתרון.'''
נבחר 2 איברים שונים <math>b_0,b_1\in B</math> ונגדיר פונקציה חח"ע <math>g:A\to B^A</math> ע"י <math>g(a)=f_a</math> כאשר <math>f_a(a)=b_1</math> ו <math>\forall a'\not=a :f_a(a')=b_0</math>
ולכן <math>|A|\leq|B^A|</math>.
נניח בשלילה שקיים שיוויון אזי קיימת התאמה חח"ע ועל <math>g:A\to B^A</math>.
נסמן <math>\forall a\in A:g(a)=f_a</math>.
נראה באופן דומה לתירגול קודם כי g איננה על ע"י שנמצא פונקציה f שאין לה מקור:
נבחר 2 איברים שונים <math>b_0,b_1\in B</math>ונגדיר פונקציה באופן הבא <math>f:A\rightarrow B</math> ע"י
<math>f(a)=b_0</math> אם <math>f_a(a)=b_1</math>. ו- <math>f(a)=b_1</math> אחרת.
לפי הבנייה <math>\forall a\in A f\not=f_a</math> כיוון ש <math>f(a)\not=f_a(a)</math>. סתירה לכך ש g על.
הערה: התרגיל הזה הוא מסקנה מהתרגילים הקודמים כי <math>|\{0,1\}|\leq |B|</math> ולכן <math>|A|<|\{0,1\}^A|\leq |B^A|</math>
'''הגדרה:'''
יהיו שתי קבוצות '''זרות''' A,B כך ש <math>|A|=a, |B|=b</math>. אזי נגדיר פעולות בין עוצמות:
*<math>a+b:=|A\cup B|</math>
*<math>a\cdot b := |A\times B|</math>
*<math>a^b := |\{f:B\rightarrow A\}|</math>
דוגמא: ראינו בתירגול קודם את הזיהוי <math>[0,1)=\{f:\mathbb{N} \to \{0,1,...9\}\}</math>
לכן <math>\aleph=|\mathbb{R}|=|[0,1)|=|\{f:\mathbb{N} \to \{0,1,...9\}\}|=10^{\aleph_0}</math>
הערות:
*ההגדרות לעיל מוגדרות היטב, כלומר העוצמה נשארת זהה ללא תלות בבחירת הקבוצות המייצגות.
* בידקו שעבור המקרה הסופי מתקיים מה שמצופה.
למשל <math>2+1=|\{1,2\}\cup\{3\}|=3</math>
*'''שימו לב:''' מתוך הגדרה זו קל לראות את חוקי החזקות למקרי הקצה:
**<math>a^0=1</math> שכן יש פונקציה יחידה מהקבוצה הריקה לכל מקום - היחס שהוא הקבוצה הריקה.
**<math>0^0=1</math> זה מקרה פרטי של הסעיף הקודם, ועדיין מתקיים
**<math>1^a=1</math>
**<math>a\neq 0 \rightarrow 0^a=0</math> אין אף פונקציה מקבוצה לא ריקה אל קבוצה ריקה, שכן יחס כזה לא יכול להיות שלם.
===תכונות האריתמטיקה===
יהיו a,b,c עוצמות אזי מתקיים
*<math>ab=ba</math>
*<math>(ab)c=a(bc)</math>
*<math>a^ba^c=a^{b+c}</math>
*<math>a^cb^c=(ab)^c</math>
*<math>(a^b)^c=a^{bc}</math>
כלומר מתקיימים חוקי החזקות ה"רגילים"
נוכיח למשל <math>a^ba^c=a^{b+c}</math> יהיו <math>|A|=a,|B|=b,|C|=c</math> קבוצות זרות
נגדיר פונקציה מ <math>A^{B\cup C} \to A^B\times A^C</math> ע"י <math>f \mapsto (f|_B,f|_C)</math>. היא חח"ע ועל.
נוכיח למשל <math>(a^b)^c=a^{bc}</math> יהיו <math>|A|=a,|B|=b,|C|=c</math> קבוצות זרות
נגדיר פונקציה מ <math>(A^B)^C \to A^{B\times C} </math> ע"י <math>f \mapsto g(b,c)= f(c)(b)</math>. היא חח"ע ועל.
בנוסף אם מניחים את אקסיומת הבחירה אזי מתקיים עבור a,b עוצמות כאשר אחד מהם אין סופי
* <math>a+b=max\{a,b\}</math>
*אם שניהם אינם אפס אזי <math>a\cdot b=max\{a,b\}</math>
*מסקנה: אם <math>2\leq a \leq b</math> אזי <math>a^b=2^b</math>
הוכחה <math>2^b\leq a^b\leq (2^a)^b=2^{ab}=2^b</math>
===תרגיל===
הוכח כי <math>\aleph_0+\aleph=\aleph</math>
הוכחה: דרך א- ישירות מהגדרה. נבחר <math>A=[\frac{1}{4},\frac{1}{2}],B=\mathbb{N}</math> אזי
<math>\aleph=|A|\leq |A\cup B |\leq |\mathbb {R}|=\aleph</math>
דרך ב- מהנוסחא. <math>\aleph_0+\aleph=max\{\aleph_0,\aleph\}=\aleph </math>
===תרגיל===
הוכח כי <math>\aleph \cdot \aleph=\aleph </math>
הוכחה: <math>\aleph=|\{f:\mathbb{N}\to \{ 0,1\dots 9 \} \}|=10^{\aleph_0}=2^{\aleph_0}</math>
דרך א- ישירות מהגדרה. נבחר <math>A=\{f:\mathbb{N}\to \{0,1\dots 9\}\},B=A\times A</math> אזי
נגדיר פונקציה <math>A\to A\times A</math> ע"י <math>f(n)\mapsto (f(2n),f(2n+1))</math> . זו פונקציה חח" ועל.
דרך ב- אריתמטיקה-
<math>\aleph \cdot \aleph=2^{\aleph_0}\cdot 2^{\aleph_0}=2^{\aleph_0+\aleph_0}=2^{\aleph_0}=\aleph </math>
דרך ג- מהנוסחא- <math>\aleph \cdot \aleph=max\{\aleph,\aleph\}=\aleph </math>
===תרגיל===
הוכח כי <math>|\mathbb{R}\backslash \mathbb{Q}|=\aleph</math>
פתרון:
כיוון ש <math>\mathbb{R}\backslash \mathbb{Q}</math> מוכל בממשיים עוצמתה לכל היותר אלף. נניח בשלילה כי עוצמתה שווה a קטנה ממש מאלף אזי
<math>\aleph=|\mathbb{R}|=|\mathbb{R}\backslash \mathbb{Q}|+|\mathbb{Q}|=a+\aleph_0=a<\aleph</math>. סתירה
=== תרגיל ===
חשבו את <math>\aleph^{\aleph_0},{\aleph_0}^{\aleph}</math>
פתרון: <math>\aleph^{\aleph_0}=\aleph,{\aleph_0}^{\aleph}=2^{\aleph}</math>
הסיקו כי עוצמת קבוצת הפונקציות מהרציונאלים לממשיים היא <math>\aleph</math>.
===תרגיל===
תהא <math>A</math> קבוצה אינסופית ו <math>B\subseteq A</math> תת קבוצה.
הוכח/הפרך
1. <math>|A\backslash B|=|A|\Rightarrow |B|<|A|</math>
2. <math>|A\backslash B|=|A|\Leftarrow |B|<|A|</math>
פתרון:
1. הפרכה: ניקח את השלמים והטבעיים
2. נכון כי ניתן להציג A כאיחוד זר <math>A=A\backslash B \cup B</math>
ולכן <math>|A|=|A\backslash B| + |B|</math>. אם <math>|A\backslash B|<|A|</math> נקבל סתירה
=== תרגיל ===
1. מה עוצמת <math>\mathbb{N}^\mathbb{N}</math>
פתרון: <math>\aleph_0^{\aleph_0} =2^{\aleph_0} </math>
2. מה עוצמת <math>X=\{f\in \mathbb{N}^\mathbb{N}:f(1)\leq f(2)\}</math>
פתרון: לכל היותר <math>\mathbb{N}^\mathbb{N}</math> ולכל הפחות <math>\mathbb{N}^\mathbb{N}</math>
כי לכל <math>g\in \mathbb{N}^{\mathbb{N}\setminus \{1,2\}}</math> נתאים <math>f\in X</math> ע"י <math>f(1)=f(2)=1 </math> ועבור <math>x\neq 1,2</math> נגדיר <math>f(x)=g(x)</math> ולכן <math>|\mathbb{N}^{\mathbb{N}\setminus \{1,2\}}|\leq|X|\leq |\mathbb{N}^\mathbb{N}|</math> ולפי ק.ש.ב יש שיווון
3. מה עוצמת <math>X=\{f\in \mathbb{R}^\mathbb{R}:\forall x\notin \mathbb{Q} f(x)=1\}</math>
פתרון: X שווה עוצמה ל <math>\mathbb{R}^{\mathbb{Q}}</math> כי <math>g\in\mathbb{R}^{\mathbb{Q}}</math> ממופה ל <math>f\in X</math> המוגדרת <math>f|_{\mathbb{Q}}=g,f|_{\mathbb{R}\setminus\mathbb{Q}}=1</math>
=== תרגיל ===
תהי <math>\{A_i\}_{i\in I}</math> משפחה של קבוצות הזרות זו לזו כך שעוצמת כל אחת מהן ב<math>a</math>. נגדיר <math>\sum_{i\in I} a = |\bigcup_{i\in I}A_i|</math>.
הוכח כי <math>\sum_{i\in I} a = |I|\cdot a</math>
פתרון:
תהא <math>A</math> קבוצה נוספת מעוצמה <math>a</math>.
לכל <math>i\in I</math> קיימת פונקציה חח"ע ועל
<math>f_i:A\rightarrow A_i</math>.
כעת נגדיר פונקציה <math>g:I\times A\rightarrow\bigcup_{i\in I}A_i</math> ע"י <math>g(k,x)=f_k(x)</math>. מכיוון שהקבוצות זרות ו<math>f_k</math> חח"ע ברור שg חח"ע. מכיוון ש<math>f_k</math> על גם g על ולכן קיבלנו את המבוקש.
=== תרגיל ===
נגדיר <math>F</math> להיות אוסף תתי הקבוצות הסופיות של הטבעיים <math>F=\{X\subseteq \mathbb{N}:|X|<\aleph_0\}</math>. מה עוצמתה?
פתרון: לכל <math>i\in \mathbb{N}</math> נגדיר <math>F_i=\{X\subseteq \mathbb{N}:|X|=i\}</math> (אוסף תתי הקבוצות מגודל <math>i</math>). אזי <math>|F_i|\leq \aleph_0^i=\aleph_0</math>
ואז <math>|F|=|\cup_{i\in \mathbb{N}}F_i|\leq \aleph_0\cdot \aleph_0 =\aleph_0</math>
=== תרגיל (בש.ב.)===
נגדיר <math>A</math> להיות אוסף תתי הקבוצות האינסופיות של הטבעיים. מה עוצמתה?
פתרון: מתקיים כי <math>P(\mathbb{N})=A\cup A^c</math> כאשר A היא תתי הקבוצות הסופיות מתרגיל קודם שעוצמת <math>\aleph_0</math>
ולכן <math>2^{\aleph_0}=\aleph_0+|A^c|=\max\{\aleph_0,|A^c|\}=|A^c|</math>
=== תרגיל ===
נגדיר <math>A=\{X\subseteq \mathbb{R}: |X|=\aleph_0 \}</math> ,מה עוצמתה?
פתרון: לכל הפחות <math>2^{\aleph_0}</math> כי תתי הקבוצות האינסופיות של הטבעיים מעוצמה זאת. בצד שני נגדיר <math>F:\mathbb{R}^{\mathbb{N}}\to P(\mathbb{R})</math> ע"י
<math>f\mapsto Im(f)</math> טענה: <math>A\subseteq Im(F)</math> הוכחה: תהא <math>X\in A</math> ומהגדרת A, נסיק כי X מעוצמה הטבעיים ולכן קיימת <math>f:\mathbb{N}\to X</math> חח"ע ועל ולכן <math>F(f)=Im(f)=X</math>. מסקנה מכך <math>|A|\leq |Im(F)|\leq |\mathbb{R}^{\mathbb{N}}|=\aleph^{\aleph_0}=\aleph</math>. לפי ק.ש.ב <math>|A|=2^{\aleph_0}=\aleph</math>
=== תרגיל ===
נגדיר <math>A=\{X\subseteq \mathbb{R}: |X|=\aleph \}</math> ,מה עוצמתה?
פתרון: לכל היותר <math>2^\aleph</math> מצד שני <math>F:P((0,1))\to A </math> המוגדרת <math>B\mapsto B\cup (1,2)</math> חח"ע ולפי ק.ש.ב. סימנו
===תרגיל ממבחן תשסח מועד א (ד"ר שי סרוסי וד"ר אלי בגנו) ===
תהי A קבוצה אינסופית. נסמן <math>a=|A|,\;B=P(A),\;F=A\times P(A),\; C=P(A)^A,\; H=B^B</math>
:א. מצא את <math>|C|</math>
:ב. מצא את <math>|F\times H|</math>
:ג. מצא את <math>|\{R:|\mathbb{N}/R|=2\}|</math> המוכלת באוסף יחסי השקילות על הטבעיים.
'''פתרון.'''
א. <math>|C|=(2^a)^a=2^{aa}=2^a</math>
ב.<math>|F\times H|=|F||H|=a2^a(2^a)^{2^a}=2^{a2^a}=2^{2^a}</math>
ג. כל יחס שקילות שקבוצת המנה 2 מתאים לחלוקה של <math>\mathbb{N}</math> ל-2 קבוצות זרות.
ולכן יש התאמה חח"ע ועל <math>\{R:|\mathbb{N}/R|=2\} \leftrightarrow W=\{\{A,A^c\}|A\subseteq \mathbb{N}\}</math> ולכן 2 הקבוצות מאותה עוצמה.
ט: <math>|W|=2^{\aleph_0}</math>
ה: נסמן <math>|W|=a</math>. בנוסף <math>\bigcup_{\{A,A^c\}\in W}\{A,A^c\}=P(\mathbb{N})</math>
ולכן <math>2^{\aleph_0}=|P(\mathbb{N})|=2a=a</math>.
=== תרגיל ===
נגדיר <math>X=\left\{ 0,1\right\} ^{\mathbb{N}}</math> קבוצת כל הסדרות הבינאריות. נגדיר יחס <math>\sim</math> על <math>X</math> כך <math>f\sim g</math> אמ"מ הקבוצה<math>\left\{ n\in\mathbb{N}\mid f(n)\neq g(n)\right\}</math> סופית
הוכיחו כי <math>\sim</math> יח"ש
לכל <math>f\in X</math>, מצאו את העוצמה של <math>[f]</math>.
מצאו את העוצמה של קבוצת המנה.
=== תרגיל ===
תהא <math>X\subseteq P(\mathbb{N})</math>.
מצאו <math>X</math> המקיימת: כל <math>A,B\in X</math> שונות הן זרות (כלומר <math>A\cap B=\emptyset</math>).
ניח <math>X</math> מקיימת: כל <math>A,B\in X</math> שונות הן זרות. הוכיחו כי <math>X</math> בת מנייה.
תהא <math>C\subseteq\mathbb{N}</math>. נניח <math>X</math> מקיימת: החיתוך של <math>A,B\in X</math> שונות הוא <math>C</math> (כלומר <math>A\cap B=C</math>). הוכיחו כי <math>X</math> בת מנייה.
נניח <math>X</math> מקיימת: החיתוך של <math>A,B\in X</math> שונות הוא לכל היותר בן 10 איברים (כלומר <math>\left|A\cap B\right|\leq10</math> ). הוכיחו כי <math>X</math> בת מנייה.רמז: <math>\cup_{B\in I}X_{B}</math> כאשר <math>I=\left\{ B\subseteq\mathbb{N}\mid\left|B\right|=10\right\}</math> ו <math>X_{B}=\left\{ S\in X\mid B\subseteq S\right\}</math>
===תרגיל ממבחן תשע מועד א (ד"ר שי סרוסי וד"ר אפי כהן)===
יהי S יחס על <math>\mathbb{R}^\mathbb{R}</math> (קבוצת כל הפונקציות הממשיות), המוגדר על ידי <math>(f,g)\in S</math> אם"ם לכל <math>x\in\mathbb{R}</math> מתקיים <math>f(x)-g(x)\in\mathbb{Z}</math>
:1. הוכיחו ש S הינו יחס שקילות
:2. תהי <math>f\in\mathbb{R}^\mathbb{R}</math> מצאו את <math>|[f]|</math>
:3. מצאו את <math>|\mathbb{R}^\mathbb{R}/S|</math>
'''פתרון:'''
1.
*רפלקסיביות: <math>\forall x\in\mathbb{R} f(x)-f(x)=0\in\mathbb{Z}</math>
*סימטריות: <math>f(x)-g(x)\in\mathbb{Z}</math> גורר שגם <math>g(x)-f(x)\in\mathbb{Z}</math> כי יש נגדי לחיבור
*טרנזיטיביות: נובעת בקלות מסגירות לחיבור בשלמים: <math>f-h=f-g+g-h</math>
2.
עבור <math>[f]\in \mathbb{R}^\mathbb{R}/S </math>
נגדיר <math>F:[f] \to \mathbb{Z}^{\mathbb{R}}</math>.
ע"י <math>F(g):=f-g </math> נראה כי היא מוגדרת,חח"ע ועל.
מוגדרת: לפי ההגדרה של יחס השקילות אכן מתקיים <math>f-g\in \mathbb{Z}^{\mathbb{R}}</math>
נראה כי ל F קיימת הופכית. נגדיר <math>G: \mathbb{Z}^{\mathbb{R}} \to [f]</math>. ע"י <math>G(h):=f-h </math>. הפונקציה מוגדרת היטב כי <math>f-(f-h)\in \mathbb{Z}^{\mathbb{R}}</math> וקל לוודא שזוהי ההופכית
חח"ע: נניח <math>F(g)=F(h)</math> לכן <math>\forall x\in\mathbb{R} f(x)-g(x)=f(x)-h(x)</math> ולכן h=g.
על: תהי h פונקציה כלשהי מהממשיים לשלמים, ברור ש(f-h) במחלקת השקילות של f והיא תהיה המקור.
אם כך, העוצמה של מחלקת השקילות זהה לעוצמה של אוסף הפונקציות מהממשיים לשלמים והוא <math>{\aleph_0}^\aleph</math>. לפי התכונות שלמדנו לעיל מתקיים <math>2^\aleph\leq{\aleph_0}^\aleph\leq 2^\aleph</math> ולכן לפי קנטור מתקיים <math>{\aleph_0}^\aleph=2^\aleph</math>
3.
נזכור בסימון <math>\lfloor x\rfloor</math> שהוא המספר השלם הגדול ביותר הקטן או שווה לx.
נגדיר F פונקציה השולחת את <math>f\in\mathbb{R}^\mathbb{R}</math> לפונקציה <math>F(f):=f-\lfloor f\rfloor\in [0,1)^\mathbb{R}</math>. נראה ש-F מוגדרת היטב (על קבוצת המנה)וההפעלה שלה על קבוצת המנה תהיה חח"ע ועל.
מוגדרות: יהיו שתי פונקציות באותה מחלקת שקילות g,f. אזי, <math>F(g)-F(f)=g-\lfloor g\rfloor -f + \lfloor f\rfloor</math>. מכיוון שזהו הפרש של שני מספרים אי שליליים קטנים מאחד, זה שווה למספר שבערכו המוחלט קטן מאחד. מכיוון שההפרש בין f ל-g שלם, המספר הזה הוא שלם. המספר השלם האי שלילי היחיד שקטן מאחד הינו אפס
כלומר <math>F(f)=F(g)</math>. לכן הפונקציה F מוגדרת היטב שכן היא שולחת נציגים שונים של מחלקת שקילות לאותו מקום.
חח"ע: נניח <math>F(f)=F(g)</math> אז <math>f-g=\lfloor f\rfloor - \lfloor g\rfloor</math>
כיוון ש <math>\lfloor f\rfloor - \lfloor g\rfloor\in \mathbb{Z}^\mathbb{R} </math> אזי הם נציגים של אותה מחלקת שקילות כלומר <math>[f]=[g]</math>
על: ניקח פונקציה כלשהי r מהממשיים לקטע <math>[0,1)</math>. קל לראות ש <math>F[r]=r</math> שכן
<math>\lfloor r \rfloor = 0</math>. לכן r ישמש מקור ולכן F הינה על.
סה"כ קיבלנו שעוצמת קבוצת המנה שווה ל<math>\aleph^\aleph</math> וזה שווה ל<math>2^\aleph</math> לפי התכונות לעיל.
===תרגיל ממבחן תשע מועד ב (ד"ר שי סרוסי וד"ר אפי כהן)===
א. תהי A קבוצה אינסופית מעוצמה a.
:1. נגדיר עבור :
<math>X=\{(X_1,...,X_n):1<n\in\mathbb{N}\and\Big[\bigcup_i X_i=A\Big] \and \Big[\forall i\neq j: X_i\cap X_j = \emptyset\Big] \and \big[ \forall i X_i \neq \emptyset\big]\}</math>.
כלומר אוסף החלקות הסופיות הלא טרי' הסדורות של A
'''הוכח''' <math>|X|=2^a</math>
:2. מצא את <math>|\mathbb{N}\times X|,|\mathbb{N}\cup X|</math> וגם את <math>|X|^{|\mathbb{N}|},|\mathbb{N}|^{|X|}</math>
ב.תהי <math>\{A_i\}_{i\in I}</math> משפחה של קבוצות הזרות זו לזו. נסמן את עוצמת כל אחת מהן ב<math>a_i</math> בהתאמה. נגדיר <math>\sum_{i\in I} a_i = |\bigcup_{i\in I}A_i|</math>.
חשב את <math>\sum_{n\in\mathbb{N}}\aleph</math>
'''פתרון.'''
א.
:1.
נביט באוסף הפונקציות <math>Y=\{f:A\rightarrow\mathbb{N}\}</math>. נגדיר <math>g:X\to Y</math>
על ידי לכל <math>x=(X_1,...,X_n)\in X</math>
נשלח אותו ל <math>g(x)=f_x</math> המוגדר
<math>\forall a\in A :\; f_x(a)=k</math> כאשר <math>a\in X_k</math> כלומר שולחת איבר לאינדקס של הקבוצה שהוא נמצא בה בחלוקה.
נוכיח שהפונקציה מוגדרת וחח"ע.
מוגדרת: כיוון ש x הוא חלוקה של A אזי האיבר a יופיע ויופיע בדיוק באחת מהקבוצות.
חח"ע: נניח <math>(X_1,...,X_n)=x\neq x'=(X'_1,...,X'_m)</math>. אזי קיים <math>X_i\not=X'_i</math>, לכן קיים יהיה <math>a\in X_i/X'_i</math> (או להיפך) ואז <math>i=f_x(a)\not= f_{x'}(a)</math>
כלומר <math>g(x)\not=g(x') </math>
דרך 2- נגדיר פונקציה <math>g:X\to P(A)^{\mathbb{N}}</math> ע"י <math>g((X_1,...,X_n))(i) = \begin{cases}X_i & \text{if } 1\leq i \leq n \\ \emptyset & \text{if } n<i \end{cases} </math>
קל לראות כי הפונקציה חח"ע ולכן <math> |X| \leq (2^{a})^{\aleph_0} = 2^{a\cdot \aleph_0} =2^a</math>
דרך 3- נציג את X כאיחוד זר <math>X=\cup_{1<n\in \mathbb {N}}Y_n</math> כאשר <math>Y_n</math> זה חלוקות סדורות של A עם n קבוצות. כעת לכל n קיימת פונקציה <math>g:Y_n \to P(A)^n</math>
המוגדרת <math>g((X_1,...,X_n))=X_1 \times \cdots \times X_n</math> קל לראות שהיא חח"ע ולכן <math>|Y_n|=|A|^n =|A|</math> ולכן <math>|X|\leq \sum_{1<n\in \mathbb {N}}|A|=|A|\cdot \aleph_0 =|A|</math>
כעת, קל למצוא פונקציה חח"ע מקבוצת החזקה של A ל-X - נשלח כל תת קבוצה לזוג שמכיל אותה ואת המשלים שלה.
לכן <math>2^{|A|} \leq |X| \leq |Y| = \aleph_0^{|A|}</math>, ולפי התכונות לעיל שני הקצוות שווים. לכן עוצמת X הינה <math>2^a</math>.
:2.
קל לבנות פונקציה על מאוסף הפונקציות מA לB אל A. נשלח כל פונקציה באוסף למקור של איבר b מסוים. מכיוון שכל הפונקציות מA לB נמצאות באוסף, בפרט כל הפונקציות ששולחות כל איבר מA ל-b יהיו שם.<math>|\mathbb{N}\cup X|=\aleph_0+2^a=2^a</math>
נניח בשלילה שקיימת התאמה חח"ע ועל בין A לבין אוסף הפונקציות הנ"ל. נסמן ב<math>f_a:A|\rightarrow B</math> את הפונקציה המתאימה לאיבר <math>mathbb{N}\times X|=\aleph_0\cdot 2^a=2^a\in A</math>.
ידוע לנו שבקבוצה B יש לפחות שני איברים, לכן בהנתן אחד מהם אפשר לבחור את השני. נגדיר פונקציה באופן הבא <math>|X|^{|\forall a\in A : gmathbb{N}|}=(2^a)^{\neq g_a(aleph_0}=2^{a\cdot \aleph_0}=2^a)</math>. לפי ההגדרות פונקציה זו הינה פונקציה מA לB אך אינה מתאימה לאף איבר בA בסתירה.
<math>|\mathbb{N}|^{|X|}=(\aleph_0)^{2^a}=2^{2^a}</math>
'''תרגיל.''' הוכח שעוצמת קבוצת החזקה של A תמיד גדולה מעוצמתה של A
'''הוכחה.''' קל להראות שקיימת העתקה חח"ע ועל בין אוסף הפונקציה <math>f:A\rightarrow \{0,1\}</math> (כל קבוצה חלקית אומרת בעצם על כל איבר של A אם הוא שייך (1) או לא שייך (0). למשל הפונקציה המתאימה לקבוצה הריקה היא פונקצית האפס, והפונקציה המתאימה לקבוצה כולה היא הפונקציה 1)ב.
פונקציה זו עומדת בתנאי התרגיל לעיל ולכן עוצמתה גדולה בעצם אנו רוצים לחשב איחוד בן מנייה של קבוצות מעוצמת A אבל זהה לעוצמה <math>\aleph</math>. לכל עותק של קבוצת החזקה<math>\aleph</math> נתאים <math>A_n</math> ופונקציה חח"ע ועל <math>f_n:\mathbb{R}\rightarrow A_n</math>. כעת נגדיר פונקציה <math>g:\mathbb{N}\times\mathbb{R}\rightarrow\bigcup_{n\in\mathbb{N}}A_n</math> ע"י <math>g(k, כפי שרצינוx)=f_k(x)</math>.מכיוון שהקבוצות זרות ו<math>f_k</math> חח"ע ברור שg חח"ע. מכיוון ש<math>f_k</math> על גם g על ולכן סה"כ עוצמת הסכום הינה <math>\aleph_0\cdot\aleph=\aleph</math>