'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
=עוצמות=
'''הגדרה.''' יהיו A,B שתי קבוצות. אזי:
*אם קיימת פונקציה <math>f:A\to B </math> חח"ע מA לB אזי העוצמה ועל אז אומרים של A ולB '''יש אותה עוצמה''' (סימון <math>|A|=|B גדולה |</math>)*אם קיימת <math>f:A\to B </math> חח"ע אז אומרים כי העוצמה של A קטנה או שווה לזו של AB. (סימון <math>|A|\leq|B|</math>)*אם <math>|A|\leq|B|</math> וגם <math>|A|\not=|B|</math> אזי אומרים כי העוצמה של A קטנה ממש מהעצמה של B (סימון <math>|A|<|B|</math>) הערה: בעזרת אקסיומת הבחירה מוכיחים כי אם קיימת פונקציה <math>f:A\to B </math> על אזי <math>|B|\leq|A|</math>(בעזרת התרגיל מתירגול קודם כי ניתן לצמצם את התחום של f כך שתהא חח"ע ועל מA לB אזי אומרים שלA ולB '''יש אותה עוצמה''')
'''דוגמא.''' יהיו 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>A\subseteq B</math> אזי <math>|A|\leq |B|</math>. קל לבנות פונקציה מA לB ששולחת כל איבר בA לעצמו, זו פונקציה חח"ע.=== '''טענה.''' אם A קבוצה וR יחס שקילויות על הקבוצה אזי עוצמת קבוצת המנה קטנה או שווה לעוצמה של A. נוכיח טענה זו בהמשך הקורס באמצעות אקסיומת הבחירה. '''טענה.''' מתקיים ש <math>|\mathbb{N}|=|\mathbb{N}\times \mathbb{N}|</math>.
'''הוכחה.'''
קל לראות שפונקציה זו מוגדרת היטב. לכל מספר טבעי פשוט עוקבים אחרי התהליך הזה ורואים לאיזה זוג הוא נשלח. כמו כן, לכל זוג ניתן לעבור על התהליך עד שיגיע המספר שישלח אליו.
[[קובץ:NutualSquareEqNutural.jpeg]]
כמו כן קל לראות שפונקציה זו חח"ע וגם על.
=== <math>\aleph_0 \cdot \aleph_0=\aleph_0</math> ==='''טענה.הגדרה''' מתקיים ש * העוצמה של הטבעיים מסומנת <math>|\mathbb{Z}aleph_0</math>* קבוצה A המקיימת <math>|=A|\mathbb{Z}leq \times \mathbb{Z}|aleph_0 </math>. תרגיל בית.נקראת '''בת מנייה''' (מקור השם כי ניתן למנות/ למספר את האיברים בה ע"י התאמה חח"ע ועל מהטבעיים במקרה האין סופי או במקרה הסופי פשוט למספר עד n )
נביט באוסף הזוגות הסדורים בהם האיבר הימני שונה מאפס. קבוצה זו מוכלת באוסף כל הזוגות ולכן עוצמתה קטנה מעוצמת השלמים. נחלק אוסף זה ביחס השקילות טענה <math>(a,b)~(x,y) \iff ayB=bx</math> ונקבל קבוצה מעוצמה אף קטנה יותר. קבוצת המנה שקיבלנו היא כמובן <math>\mathbb{Q}</math> ולכן קיבלנו ש <math>2n-1 |n\in \mathbb{QN}|\leq |\mathbb{Z}|</math>.קבוצת האי זוגיים היא בת מנייה
בכיוון ההפוך, השלמים מוכלים ברציונאליים ולכן עוצמתם קטנה יותר ומכאן שעוצמת הרציונאליים שווה לעוצמת השלמים.הוכחה : נגדיר פונצקיה <math>f:\mathbb{N}\to B </math> ע"י <math>n\mapsto 2n-1</math>
טענה <math>C=\mathbb{N}\cup\{0\}</math> קבוצת הטבעיים עם <math>0</math> בת מנייה
(השתמשנו במשפט קנטור-ברנשטייןהוכחה : אם A וB קבוצות שעוצמתן קטנות זו מזו אזי עוצמתן שווה.)נגדיר פונצקיה <math>f:\mathbb{N}\to C </math> ע"י <math>n\mapsto n-1</math>
עוצמתן של הקבוצות הנ"ל נקראת טענה <math>\aleph_0 \cdot \aleph_0=\aleph_0</math>. קבוצות מעוצמה זו נקראות '''בנות מנייה'''.
שימו לב שכל קבוצה בת מנייה, ניתן למצוא פונקציה חחהוכחה: נגדיר <math>f:B\times C\to \mathbb{N}</math> ע"ע ועל מהטבעיים אליה - כלומרי <math>(x, ניתן לסדר אותה בסדרה (ומכאן מגיע השםk).\mapsto x\cdot 2^k</math>
==השוואות עוצמות=='''תרגיל.''' נביט באוסף כל הסדרות הבינאריות (01110010101011011...). נתאר אוסף זה באופן מדוייקטענה: <math>B=\{f:\mathbb{N}\rightarrow \{0,1\}\}</math>. השווה בין העוצמה של B לבין אלף אפס.חח"ע
'''פתרון.'''קיימת פונקציה על מהסדרות אל המספרים הטבעיים: נשלח כל סדרה שהחל ממקום מסויים היא קבועה אפס אל המספר שהיא מייצגת בבסיס בינארי. כל סדרה אחרת נשלח לאחד. הוכחה נניח <math>f(שימו לב שאת הסדרה הקבועה אפס נשלח גם לאחד לפי הגדרה...x_1,k_1).=f(x_2,k_2)</math> אזי <math>x_1 \cdot 2^{k_1} =x_2 \cdot 2^{k_2}</math>
לכן עוצמת B גדולה או שווה לאלף אפס. נוכיח כי היא גדולה ממש.בה"כ <math>k_1\leq k_2</math> ונחלק את שני האגפים ב <math>2^{k_1}</math>
נניח בשלילה שקיימת פונקציה g חח"ע ועל מהטבעיים אל Bנקבל כי<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>g(1)=0101010110110101001000100101...</math>טענה: f על
הוכחה: יהא n טבעי. יהיה <math>k\in C</math> כך ש <math>g(2)=1101010001010010100010101010...^k</math>מחלק את n ואילו <math>2^{k+1}</math> אינו מחלק את n. כלומר החזקה הגדולה ביותר של 2 בפירוק של n למכפלת ראשונים זרים.
מהגדרת k נובע כי <math>g\frac{n}{2^k}</math> אי זוגי (3)=0101010101011101010001010111...כי אחרת הוא זוגי ואז 2 מחלק את המספר ואז <math>2^{k+1}</math>מחלק את n. סתירה).
לפי הגדרת f רואים כי <math>(\frac{n}{2^k},k)</math> מקור ל n. וסיימנו.
נבנה סדרה בינארית שקיימת בB אך לא ייתכן שהיא מתקבלת על ידי הפונקציה g (כלומר היא אינה בסדרה, בסתירה).==== תרגיל ====הוכיחו כי לכל <math>0<n</math> טבעי מתקיים כי <math>\mathbb{N}^n=\mathbb{N}\times\mathbb{N}\times \cdots \times \mathbb{N} </math> מעוצמה <math>\aleph_0</math>
נגדיר את הפונקציה f שנותנת את הסדרה פתרון: באינדוקציה. בסיס: ברור. צעד: <math>|\forall mathbb{N}^{n\in+1}=|\mathbb{N}:f(^n)\times \mathbb{N}|= |\neg g(n)_nmathbb{N}\times \mathbb{N}|=|\mathbb{N}|</math>. כלומר לקחנו סדרה שהאיבר הראשון שלה שונה מהאיבר הראשון של הסדרה הראשונה, האיבר השני שונה מהאיבר השני של הסדרה השנייה וכן הלאה.
בדוגמא לעיל הסדרה תתחיל בשלושת האיברים ==משפט קנטור- שרדר-ברנשטיין==אם <math>101|B|\leq|A|</math> וגם <math>|A|\leq|B|</math> אז <math>|B|=|A|</math> ולכן בוודאי לא תהיה אף אחת משלוש הסדרות הראשונות.
באופן כללי, לא ייתכן שסדרה זו נמצאת במקום k כלשהו בסדרת הסדרות, כי האיבר ה-k שלה שונה מהאיבר ה-k של הסדרה ה-k===תרגיל===<math>|\mathbb{Q}|=\aleph_0</math>.
====פתרון====
'''טענה.''' מתקיים ש <math>|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Z}\times \mathbb{Z}|</math>.
'''מסקנה.''' נובע מהתרגיל הקודם דיי בקלות הוכחה: כיוון ש'''עוצמת הממשיים גדולה מזו של הטבעיים'''. (אם נסתכל על הסדרות הבינאריות כספרות אחרי הנקודה של מספרים ממשיים נראה שקבוצה זו מוכלת בממשיים).<math>|\mathbb{N}|=|\mathbb{Z}|</math> אזי לפי תרגיל ממקודם <math>|\mathbb{N}|=|\mathbb{N}\times \mathbb{N}|=|\mathbb{Z}\times \mathbb{Z}|</math>
עוצמת הממשיים נקראת כעת, נזכר ש <math>\alephmathbb{Q}</math>.הם קבוצת מנה של <math>\mathbb{Z} \times \mathbb{N}</math>ולכן
'''טענה.''' יהיו C,W קבוצות ויהיו <math>X,Y|\subseteq W</math>, <math>A,Bmathbb{N}|\subseteq C</math> תתי קבוצות כך ש <math>Aleq |\cap B=Xmathbb{Q}|\cap Y=leq |\phi</math> וגם <math>Amathbb{Z} \cup B = C</math> וגם <math>Xtimes \cup Y = W</math>. אזי אם קיימות פונקציות חח"ע ועל <math>g:Bmathbb{N}|\rightarrow Y</math>,<math>f:Aleq |\mathbb{Z}\rightarrow X</math> מתקיים ש <math>|Xtimes \mathbb{Z}|=|Y\mathbb{N}|</math>
לפי קנטור ברנשטיין נקבל ש <math>|\mathbb{Q}|= |\mathbb{N}|=\aleph_0</math>.
'''===תרגיל.''' הוכח שעוצמת קטע סופי בממשיים זהה לעוצמת כל הממשיים===
'''הוכחה.''' קל מאד להראות שכל הקטעים הסופיים מאותה עוצמה, לכן מספיק להוכיח עבור קטע ספציפי. ניקח חשבו את הפונקציה עוצמת <math>f(x)A=\fracmathbb{1Q}{x}</math> בקטע <math>(\cap [0,1]</math> התמונה שלה הינה <math>[1,\infty)</math>. למעשה סיימנו פה את החלק העיקרי בתרגיל, שכן הפכנו קטע סופי לקטע אינסופי, כל שנותר לעשות הוא להשלים את מה שבנינו לפונקציה מקטע סופי לכל הממשיים.
====פתרון====
מצד אחד <math>A\subseteq \mathbb{Q}</math> ולכן <math>|A|\leq \aleph_0</math>.
ניקח פונקציה g השולחת את הקטע מצד שני, נגדיר <math>(B=\{\frac{1}{2n},1]</math> לקטע <math>(0,1]</math>, על ידי <math>g(x)=2x-1</math> ומשם נעביר לקטע האינסופי על ידי f. את הקטע <math>[0,:n\in \fracmathbb{1N}{2\}]\subseteq A</math> היא שולחת לקטע <math>[0,1]קל לראות ש- </math> על ידי 2x. סה"כ הגענו לחצי הישר <math>[0,|A|\geq |B|=\infty)aleph_0</math>.
באופן דומה נשלח את <math>(-1,0)</math> לקטע <math>(-\infty,0)</math> וסה"כ קיבלנו פונקציה חח"ע ועל מקטע סופי לכל ציר הממשייםלפי ק.ש.ב. סיימנו.
===תרגיל===
נסמן <math>A=\{1,2,3,4\}</math>.
'''תרגילא.''' ראינו ש חשבו את עוצמת <math>|\{f\in \mathbb{N}|=|^A:f\mathbbtext{Nis 1-1}\times\mathbb{N}|</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>. הוכיחו שהיא חח"ע.
'''תרגיל ממבחןג. הוכיחו <math>|S|=|P(\mathbb{N})|</math>.'''
א. יהיו ===תרגיל===תהיינה <math>A,B ,C,D</math> קבוצות כך ש - <math>|A/B|=|C|,|B/A|=|D|</math>. הוכח ש הוכיחו: <math>|A^B|=|BC^D|</math>.
ב. מצא קבוצות A וB כך ש ====פתרון====קיימות פונקציות הפיכות <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>. ניתן לראות שהיא חח"ע ועל.
== עוצמת הממשיים==
'''פתרון.תרגיל'''
א. לפי הנתון קיימת פונקציה חח"ע ועל f בין Aהוכח כי עוצמת כל הקבוצות הבאות שווה - כל קטעים מהצורה <math>[a,b],(a,b),[a,b),(a,b]</B לבין Bmath> כאשר <math>a<b</A. נגדיר פונקציה g מmath> ואפשר כי <math>a=-A לB.\infty , b=\infty</math>
אם הוכחה:קל לראות כי כל הקטעים הסופיים מהצורה <math>([a\in A) \and (a\notin B) </math> אזי נגדיר <math>g(a)=f(a)</math>. אם <math>(a\in A) \and (a\in B) </math>, נגדיר <math>g(a)=ab]</math>. נותר להוכיח כי g הינה חחבעלי אותה עוצמה ע"ע ועל.י הפונקציה
על[[קובץ: לכל איבר בB או שהוא בA או שלא. אם לא, אזי מכיוון ש<math>f</math> על, יהיה לו מקור מתוך האיברים בA שאינם בB. אם הוא כן בA הוא ישלח לעצמוEqveOfTowIntervals.jpeg]]
חח"ע'''הערה''': נניח בשלילה ששני איברים נשלחים לאותו מקוםאפשר לעבור מכאן לק. באופן ברור זה דורש שאחד מהם יהיה בB ואחד לאש. אם כן, האיבר שנמצא בB נשלח לעצמו ולכן גם השני נשלח לשם בסתירה לכך שהוא ב. ולא צריך להשלח לאיבר שאינו בAאת כל הפונקציות.
באותו אופן כל הקטעים הסופיים מהצורה <math>(a,b)</math> או <math>(a,b]</math> או <math>[a,b)</math> בעלי אותה עוצמה (כל הקטעים מאותו "סוג")
ב. ניקח את הטבעייםנמשיך- ט: הקטע <math>[0, ואת הטבעיים לאחר שזרקנו מהם את אחד. ברור שנשארנו עם קבוצות שוות 1]</math> בעל עוצמהשווה ל <math>[0, אבל ההפרשים בינהם הם 1)</math>\{. ה: נגדיר <math>f:[0,1)\}rightarrow [0,\phi1]</math> ואלו קבוצות מעוצמה שונה.על ידי:
*אם <math>\nexists n\in\mathbb{N}:x=\frac{1}{n}</math> אזי נגדיר <math>f(x)=x</math>
*אחרת נגדיר <math>f(\frac{1}{n})=\frac{1}{n-1}</math>
'''תרגיל.'''למעשה, כל מספר כמעט נשלח לעצמו פרט לסדרה הבת מנייה
נגדיר "שמיניה" בתור זוג עיגולים בגדלים כלשהם המשיקים זה לזה בנקודה כלשהי<math>\frac{1}{2},\frac{1}{3},\frac{1}{4},. יהי אוסף אינסופי כלשהו של שמיניות במישור הזרות זו מזו (כלומר אין שתים עם נקודת חיתוך משותפת) ..</math>
א. הוכח שעוצמת קבוצה זו הינה אלף אפסהנשלחת לסדרה
ב<math>\frac{1}{1},\frac{1}{2},\frac{1}{3},...</math>. הוכח שקיימת קבוצה של אינסוף עיגולים במרחב ללא חיתוך מעוצמת אלף
זה פונקציה חח"ע ועל.
'''פתרוןהערה: אותה פונקציה מוכיחה כי הקטע <math>(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>tan:(\frac{-\pi}{2}, והכמות שלהם זהה לחצי ציר הממשיים והוא כמובן מעוצמת אלף\frac{\pi}{2})\to \mathbb{R}</math> הפיכה בתחום הזה ולכן חח"ע ועל.
לסיום נעיר כי כל קרן (קטע עם צד אחד אין סופי) ג"כ בעלת אותה עוצמה כי היא מכילה איזה שהוא קטע ומוכלת בממשיים ולכן עפ"י קנטור ברנשטיין בעלת אותה עוצמה.
'''הגדרה''': העוצמה של הממשיים מסומנת <math>\aleph</math>.
=== תרגיל ===
הוכיחו כי <math>(0,1)\cup (3,4)</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}\to \{0,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>|C|=|W|</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 חח"ע ועל.
'''תרגיל ממבחן.'''
א.(ב 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>.
==תמיד קיימת עוצמה גדולה יותר==
'''תרגיל.''' יהיו A,B קבוצות כך ש, עוצמת B גדולה מאחד. הוכח כי העוצמה של אוסף הפונקציות מA לB גדולה מעוצמת A.
'''פתרון.'''
קל לבנות פונקציה על מאוסף הפונקציות מA לB אל Aא. נשלח כל פונקציה באוסף למקור של איבר b מסוים. מכיוון שכל הפונקציות מA לB נמצאות באוסףמתקיים <math>A=(A\cap B)\cup A/B, בפרט כל הפונקציות ששולחות כל איבר מA ל-b יהיו שם\;\; B=(A\cap B)\cup B/A</math> לפי נתון <math>|A/B|=|B/A|</math>.כיוון ש <math>|A\cap B|=|A\cap B|</math> לפי תרגיל קודם סימנו.
נניח בשלילה שקיימת התאמה חח"ע ועל בין A לבין אוסף הפונקציות הנ"לב. נסמן בניקח את הטבעיים, ואת הטבעיים לאחר שזרקנו מהם את אחד. ברור שנשארנו עם קבוצות שוות עוצמה, אבל ההפרשים בינהם הם <math>f_a:A\rightarrow B</math> את הפונקציה המתאימה לאיבר <math>a{1\},\in Aphi</math>ואלו קבוצות מעוצמה שונה.
ידוע לנו שבקבוצה B יש לפחות שני איברים, לכן בהנתן אחד מהם אפשר לבחור את השני. נגדיר פונקציה באופן הבא <math>\forall a\in A : g== '''תרגילי העשרה''' (aלא מומלץ להעביר בתירגול)\neq g_a(a)</math>. לפי ההגדרות פונקציה זו הינה פונקציה מA לB אך אינה מתאימה לאף איבר בA בסתירה=='''תרגיל.'''
נגדיר "שמיניה" בתור זוג מעגלים בגדלים כלשהם המשיקים זה לזה בנקודה כלשהי. יהי אוסף אינסופי כלשהו של שמיניות במישור הזרות זו מזו (כלומר אין שתים עם נקודת חיתוך משותפת)
'''תרגילא.''' הוכח שעוצמת קבוצת החזקה של A תמיד גדולה מעוצמתה של Aקבוצה זו הינה אלף אפס
ב. הוכח שקיימת קבוצה של אינסוף מעגלים במרחב ללא חיתוך מעוצמת אלף '''הוכחהפתרון.''' קל להראות שקיימת העתקה א. בהנתן שמיניה מסוימת באוסף, נבחר נקודה רציונאלית אחת ממעגל אחד, ואחת מהמעגל השני. זה נותן לנו פונקציה מהאוסף אל הזוגות הסדורים של מספרים רציונאליים. כעת, נוכיח כי פונקציה זו הינה חח"ע ועל בין אוסף הפונקציה <math>f:A\rightarrow \{0. נניח בשלילה כי לשתי שמיניות שונות יש נקודות משותפים בשני המעגלים. אם כן,1\}</math> (כל קבוצה חלקית אומרת בעצם על כל איבר המעגל של A אם הוא שייך האחת נמצא במעגל של האחרת ולכן גם נקודת ההשקה נמצאת בתוך המעגל האחד. מכיוון שהמעגל השני מכיל נקודה משותפת עם המעגל השני של השמיניה השנייה, חייב להיות חיתוך בינהם בסתירה (1) או לא שייך (0ציור פה יקל ממש על ההבנה שלכם...). למשל הפונקציה המתאימה לקבוצה הריקה היא פונקצית האפס לכן עוצמת האוסף קטנה מעוצמת הזוגות הסדורים של הרציונאליים, והפונקציה המתאימה לקבוצה כולה ולמדנו שזוגות סדורים של קבוצה בת מנייה היא הפונקציה 1)קבוצה בת מנייה. לכן עוצמת האוסף קטנה מבת מנייה אבל מכיוון שהיא אינסופית היא גדולה מבת מנייה ולכן בת מנייה כדרוש.
פונקציה זו עומדת בתנאי התרגיל לעיל ולכן עוצמתה גדולה מעוצמת A אבל זהה לעוצמה של קבוצת החזקהב. ניקח את אוסף המעגלים עם מרכז בראשית ורדיוס ממשי חיובי. אין בינהם חיתוך, כפי שרצינווהכמות שלהם זהה לחצי ציר הממשיים והוא כמובן מעוצמת אלף.