הוכחות מתמטיות/תורת הקבוצות/משפט קנטור

משפט

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

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

הוכחה

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

כעת נוכל להניח $X\ne \varnothing$ .

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

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

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

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

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

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

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

$◼$