הוכחות מתמטיות/תורת הקבוצות/האלכסון של קנטור ועוצמת הממשיים

$\aleph _{0}=|\mathbb {N} |<|(0,1)|=|\mathbb {R} |=\aleph ={\mathfrak {c}}=2^{\aleph _{0}}$

הוכחה

ראשית, ניווכח כי אכן $|(0,1)|=|\mathbb {R} |$:
נגדיר $f\colon (0,1)\to \mathbb {R}$ כ-$f(x)=x$, מובן כי היא חח"ע.
נגדיר $g\colon \mathbb {R} \to (0,1)$ כ-$g(x)=\arctan(x)/\pi +1/2$, אשר גם היא חח"ע.
לפי משפט קנטור-שרדר-ברנשטיין נקבל $|(0,1)|=|\mathbb {R} |$.

שנית, מאחר ו-$\mathbb {N} \subset \mathbb {R}$ נקבל אוטומטית $|\mathbb {N} |\leq |\mathbb {R} |$

נראה כי יש התאמה בין $(0,1)$ לבין $2^{\mathbb {N} }=\{0,1\}^{\mathbb {N} }$.
נסתכל על המספרים בין 0 ל-1 בבסיס בבינארי. לכל מספר כזה קיים ייצוג (או שניים) המהווה סדרה של 0 ו-1.
המקרה היחיד שיש שני ייצוגים לאותו המספר, הוא מספר המסתיים ברצף אינסופי של 1. במקרה שכזה נבחר באופן שרירותי את הייצוג השני.
כעת יש לנו התאמה בין שתי הקבוצות הנ"ל.

נניח בשלילה כי יש פונקציית שקילות $\varphi$ בין $\mathbb {N}$ לבין $(0,1)$.
נגדיר סדרות כך ש-$r_{j}^{i}$ זו הספרה ה-$j$ אחרי הנקודה בייצוג בבסיס בינארי של $\varphi (i)$.
נבנה מספר חדש על ידי הסדרה שמייצגת אותו, $r_{j}=1-r_{j}^{j}$ היא הספרה ה-$j$ אחרי הנקודה בייצוג בבסיס בינארי של המספר.
לא ייתכן כי המספר החדש נמצא במנייה כי הוא שונה מכל מספר לפחות בספרה אחת לפחות.
מכאן $|\mathbb {N} |\neq (0,1)$.

אם נשלב את כל שקיבלנו, נמצא כי $\aleph _{0}=|\mathbb {N} |<|(0,1)|=|\mathbb {R} |=\aleph ={\mathfrak {c}}=2^{\aleph _{0}}$.