כעת לכל n <math>f_n\not=f</math> כי <math>f_n(n)\not=f(n)</math> עפ"י הגדרת f. סתירה לכל ש g על.
==השוואות עוצמות==
'''תרגיל.''' נביט באוסף כל הסדרות הבינאריות (01110010101011011...). נתאר אוסף זה באופן מדוייק: <math>B=\{f:\mathbb{N}\rightarrow \{0,1\}\}</math>. השווה בין העוצמה של B לבין אלף אפס.
'''פתרון.'''
קיימת פונקציה על מהסדרות אל המספרים הטבעיים: נשלח כל סדרה שהחל ממקום מסויים היא קבועה אפס אל המספר שהיא מייצגת בבסיס בינארי. כל סדרה אחרת נשלח לאחד. (שימו לב שאת הסדרה הקבועה אפס נשלח גם לאחד לפי הגדרה...).
לכן עוצמת B גדולה או שווה לאלף אפס. נוכיח כי היא גדולה ממש.
נניח בשלילה שקיימת פונקציה g חח"ע ועל מהטבעיים אל B. לכן ניתן "לסדר" את כל הסדרות אחת אחרי השנייה:
<math>g(1)=0101010110110101001000100101...</math>
<math>g(2)=1101010001010010100010101010...</math>
<math>g(3)=0101010101011101010001010111...</math>
נבנה סדרה בינארית שקיימת בB אך לא ייתכן שהיא מתקבלת על ידי הפונקציה g (כלומר היא אינה בסדרה, בסתירה).
נגדיר את הפונקציה f שנותנת את הסדרה <math>\forall n\in\mathbb{N}:f(n)= \neg g(n)_n</math>. כלומר לקחנו סדרה שהאיבר הראשון שלה שונה מהאיבר הראשון של הסדרה הראשונה, האיבר השני שונה מהאיבר השני של הסדרה השנייה וכן הלאה.
בדוגמא לעיל הסדרה תתחיל בשלושת האיברים <math>101</math> ולכן בוודאי לא תהיה אף אחת משלוש הסדרות הראשונות.
באופן כללי, לא ייתכן שסדרה זו נמצאת במקום k כלשהו בסדרת הסדרות, כי האיבר ה-k שלה שונה מהאיבר ה-k של הסדרה ה-k.
'''מסקנה.''' נובע מהתרגיל הקודם דיי בקלות ש'''עוצמת הממשיים גדולה מזו של הטבעיים'''. (אם נסתכל על הסדרות הבינאריות כספרות אחרי הנקודה של מספרים ממשיים נראה שקבוצה זו מוכלת בממשיים).
עוצמת הממשיים נקראת <math>\aleph</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>