משפט

לכל קבוצה ${\displaystyle X}$ מתקיים ${\displaystyle |X|<|2^{X}|=|P(X)|}$ .

מסקנה של משפט זה: קיימות אינסוף עוצמות שונות.

הוכחה

עבור ${\displaystyle X=\varnothing }$ מתקיים ${\displaystyle |X|=0<1=|\{\varnothing \}|=|P(X)|}$ כנדרש.

כעת נוכל להניח ${\displaystyle X\neq \varnothing }$ .

מתקיים ${\displaystyle |X|\leq |P(X)|}$ כי הפונקציה ${\displaystyle \psi :X\to P(X)}$ המוגדרת ${\displaystyle \varphi (a)=\{a\}}$ הנה חח"ע.

נניח בשלילה כי ${\displaystyle |X|=|P(X)|}$ , אזי לפי ההגדרה קיימת ${\displaystyle \psi :X\to P(X)}$ פונקציית שקילות, כלומר חח"ע ועל.

נגדיר ${\displaystyle A={\Big \{}x\in X:x\notin \psi (x){\Big \}}\in P(X)}$ .

מאחר ו־${\displaystyle \psi }$ פונקציית שקילות קיים ${\displaystyle a\in X}$ המקיים ${\displaystyle \psi (a)=A}$ .

אם ${\displaystyle a\in \psi (a)=A}$ נקבל לפי ההגדרה ${\displaystyle a\notin A}$ . סתירה.

אחרת, אם ${\displaystyle a\notin \psi (a)=A}$ נקבל לפי ההגדרה ${\displaystyle a\in A}$ . סתירה.

מכאן נסיק כי ${\displaystyle |X|\neq |P(X)|}$ , כלומר ${\displaystyle |X|<|P(X)|}$ .

${\displaystyle \blacksquare }$