שינויים
'''דוגמא.''' יהיו 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>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>\aleph_0 \cdot \aleph_0=\aleph_0</math> ==='''משפט (קנטור- שרדר-ברנשטיין)הגדרה''' אם * העוצמה של הטבעיים מסומנת <math>|B|\leq|A|aleph_0</math> וגם * קבוצה A המקיימת <math>|A|\leq|B|\aleph_0 </math> אז <math>|B|=|A|<נקראת '''בת מנייה''' (מקור השם כי ניתן למנות/math>למספר את האיברים בה ע"י התאמה חח"ע ועל מהטבעיים במקרה האין סופי או במקרה הסופי פשוט למספר עד n )
הוכחה: נגדיר פונצקיה <math>f:\mathbb{ZN}\to \mathbb{N}\times \{0,1\}B </math> ע"י <math>f(z)=(|z|,sgn(z))</math>.פונקציה זו חח"ע ולכן<math>|n\mathbb{N}|\leq |\mathbb{Z}|\leq|\mathbb{Z}\times \mathbb{Z}|\leq|(\mathbb{N}\times \{0,mapsto 2n-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{N}|aleph_0 \leq |cdot \mathbb{Q}|\leq |\mathbb{Z} \times \mathbb{N}|\leq |\mathbb{Z}\times \mathbb{Z}|aleph_0=|\mathbb{N}| aleph_0</math>
טענה: f חח"ע
הוכחה:קל לראות כי כל הקטעים הסופיים מהצורה יהא n טבעי. יהיה <math>[a,b]k\in C</math>כך ש <math>2^k</math> מחלק את n ואילו <math>2^{k+1}</math> אינו מחלק את n. כלומר החזקה הגדולה ביותר של 2 בפירוק של n למכפלת ראשונים זרים. בעלי אותה עוצמה ע"י הפונקציה
הוכחה: כיוון ש <math>|\fracmathbb{1N}|=|\mathbb{2Z},|</math> אזי לפי תרגיל ממקודם <math>|\fracmathbb{1N}|=|\mathbb{3N},\fractimes \mathbb{1N}|=|\mathbb{Z}\times \mathbb{4Z},...|</math>
<math>|\fracmathbb{1N}|\leq |\mathbb{1Q},|\fracleq |\mathbb{1Z}\times \mathbb{2N},|\fracleq |\mathbb{1Z}\times \mathbb{Z}|=|\mathbb{3N},...| </math>.
==השוואות עוצמות==פתרון===='''תרגיל.''' נביט באוסף כל הסדרות הבינאריות (01110010101011011...). נתאר אוסף זה באופן מדוייק: מצד אחד <math>B=A\{f:subseteq \mathbb{NQ}</math> ולכן <math>|A|\rightarrow leq \{0,1\}\}aleph_0</math>. השווה בין העוצמה של B לבין אלף אפס.
א. חשבו את עוצמת <math>g(\{f\in \mathbb{N}^A:f\text{ is 1)=0101010110110101001000100101...-1}\}</math>.
ב. חשבו את עוצמת <math>g(2)=1101010001010010100010101010...\{f\in \mathbb{N}^A:f\text{ is not 1-1}\}</math>.
===תרגיל===נסמן ב-<math>g(3)S</math> את קבוצת יחסי השקילות על הטבעיים <math>S=0101010101011101010001010111...\{R\subseteq \mathbb{N}\times \mathbb{N}:R\text{ is an equivalence relation}\}</math>.
א. הראו ש- <math>|S|\leq |P(\mathbb{N})|</math>.
== עוצמת הממשיים==
'''מסקנה.תרגיל''' נובע מהתרגיל הקודם דיי בקלות ש'''עוצמת הממשיים גדולה מזו של הטבעיים'''. (אם נסתכל על הסדרות הבינאריות כספרות אחרי הנקודה של מספרים ממשיים נראה שקבוצה זו מוכלת בממשיים).
הוכח כי עוצמת הממשיים נקראת כל הקבוצות הבאות שווה - כל קטעים מהצורה <math>[a,b],(a,b),[a,b),(a,b]</math> כאשר <math>a<b</math> ואפשר כי <math>a=-\infty , b=\alephinfty</math>.
[[קובץ:EqveOfTowIntervals.jpeg]]
'''תרגיל.הערה''' הוכח שעוצמת הקטע <math>[0,1]</math> זהה לעוצמת הקטע <math>[0,1)</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>(קל להוכיח שהפונקציה שתארנו לעיל הינה חח"ע ועל.-1,0]</math> בעל עוצמה שווה ל <math>[0,1)</math>.
ה: ע"י הפונקציה <math>f(x)=-x</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>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 על.
לפי נתון קיימות 2 פונקציות חח"ע ועל <math>f_1:A\to X,\;\;f_2:B\to Y</math>
'''פתרון.'''
ב. ניקח את הטבעיים, ואת הטבעיים לאחר שזרקנו מהם את אחד. ברור שנשארנו עם קבוצות שוות עוצמה, אבל ההפרשים בינהם הם <math>\{1\},\phi</math> ואלו קבוצות מעוצמה שונה.
== '''תרגילי העשרה''' (לא מומלץ להעביר בתירגול) ==
'''תרגיל.'''
נגדיר "שמיניה" בתור זוג עיגולים מעגלים בגדלים כלשהם המשיקים זה לזה בנקודה כלשהי. יהי אוסף אינסופי כלשהו של שמיניות במישור הזרות זו מזו (כלומר אין שתים עם נקודת חיתוך משותפת)
א. הוכח שעוצמת קבוצה זו הינה אלף אפס
ב. הוכח שקיימת קבוצה של אינסוף עיגולים מעגלים במרחב ללא חיתוך מעוצמת אלף
'''פתרון.'''
א. בהנתן שמיניה מסוימת באוסף, נבחר נקודה רציונאלית אחת מעיגול ממעגל אחד, ואחת מהעיגול מהמעגל השני. זה נותן לנו פונקציה מהאוסף אל הזוגות הסדורים של מספרים רציונאליים.
כעת, נוכיח כי פונקציה זו הינה חח"ע. נניח בשלילה כי לשתי שמיניות שונות יש נקודות משותפים בשני העיגוליםהמעגלים. אם כן, העיגול המעגל של האחת נמצא בעיגול במעגל של האחרת ולכן גם נקודת ההשקה נמצאת בתוך העיגול המעגל האחד. מכיוון שהעיגול שהמעגל השני מכיל נקודה משותפת עם העיגול המעגל השני של השמיניה השנייה, חייב להיות חיתוך בינהם בסתירה (ציור פה יקל ממש על ההבנה שלכם...).
לכן עוצמת האוסף קטנה מעוצמת הזוגות הסדורים של הרציונאליים, ולמדנו שזוגות סדורים של קבוצה בת מנייה היא קבוצה בת מנייה. לכן עוצמת האוסף קטנה מבת מנייה אבל מכיוון שהיא אינסופית היא גדולה מבת מנייה ולכן בת מנייה כדרוש.
ב. ניקח את אוסף העיגולים המעגלים עם מרכז בראשית ורדיוס ממשי חיובי. אין בינהם חיתוך, והכמות שלהם זהה לחצי ציר הממשיים והוא כמובן מעוצמת אלף.