הטענות הבאות שקולות לקבוצה ${\displaystyle A}$ :

1. קיימת ${\displaystyle D\subseteq A}$ המקיימת ${\displaystyle D\sim \omega }$ .
2. קיימת ${\displaystyle B\subset A}$ (חלקית ממש) המקיימת ${\displaystyle A\sim B}$ .

כלומר, ישנן שתי הגדרות שקולות להיות ${\displaystyle A}$ קבוצה אינסופית.

הוכחה

קיימת ${\displaystyle D\subseteq A}$ המקיימת ${\displaystyle D\sim \omega }$ , לכן קיימת פונקציית שקילות (חח"ע ועל) ${\displaystyle \varphi \colon \omega \to D}$ .

נגדיר ${\displaystyle B=A\setminus \varphi (0)=(A\setminus D)\cup (D\setminus \varphi (0))}$ , ונראה שהיא אכן שקולה ל- ${\displaystyle A}$ .

נגדיר ${\displaystyle \psi \colon A\to B}$ באופן הבא:

${\displaystyle \psi (a)={\begin{cases}a&a\in A\setminus D\\\varphi (\varphi ^{-1}(a)+1)&a\in D\end{cases}}}$

נראה כי ${\displaystyle \psi }$ חח"ע: יהיו ${\displaystyle a_{1},a_{2}\in A}$ המקיימים ${\displaystyle a_{1}\neq a_{2}}$, ונפריד למקרים:

• ${\displaystyle a_{1},a_{2}\in A\setminus D}$ , כאן ${\displaystyle \psi (a_{1})=a_{1}\neq a_{2}=\psi (a_{2})}$.
• ${\displaystyle a_{1},a_{2}\in D}$ , מתקיים ${\displaystyle \varphi ^{-1}(a_{1})\neq \varphi ^{-1}(a_{2})}$ , לכן גם ${\displaystyle \varphi (\varphi ^{-1}(a_{1})+1)\neq \varphi (\varphi ^{-1}(a_{2})+1)}$ (וזאת כיון ש- ${\displaystyle \varphi }$ פונקציית שקילות).
• ${\displaystyle a_{1}\in D,a_{2}\in A\setminus D}$ , כאן ${\displaystyle \psi (a_{1})\in D}$ בעוד ${\displaystyle \psi (a_{2})\in A\setminus D}$ .

נראה כי ${\displaystyle \psi }$ על: יהי ${\displaystyle y\in B=A\setminus \varphi (0)=(A\setminus D)\cup (D\setminus \varphi (0))}$ , ונפריד למקרים:

• ${\displaystyle y\in A\setminus D}$ , אזי ${\displaystyle \psi (y)=y}$ .
• ${\displaystyle y\in D\setminus \varphi (0)}$ , אזי ${\displaystyle \psi (\varphi (\varphi ^{-1}(y)-1))=y}$ .

לכן ${\displaystyle \psi }$ פונקציית השקילות הדרושה. ${\displaystyle \blacksquare }$

קיימת ${\displaystyle B\subset A}$ (חלקית ממש) המקיימת ${\displaystyle A\sim B}$ , לכן קיימת פונקציית שקילות (חח"ע ועל) ${\displaystyle \varphi \colon A\to B}$ .

כמו כן, נשים לב כי ${\displaystyle A\setminus B\neq \phi }$ , לכן יהי ${\displaystyle a\in A\setminus B}$ .

נגדיר פונקציה ${\displaystyle \psi \colon \omega \to A}$ באופן הבא:

${\displaystyle \psi (0)=a\ ,\ \psi (n+1)=\varphi (\psi (n))}$

נניח בשלילה שהיא אינה חח"ע, אזי קיים זוג מינימלי ${\displaystyle m<n}$ עבורו ${\displaystyle \varphi (\psi (m-1))=\psi (m)=\psi (n)=\varphi (\psi (n-1))}$ .

אך אם נפעיל על שני האגפים את ${\displaystyle \varphi ^{-1}}$ נקבל ${\displaystyle \psi (m-1)=\psi (n-1)}$ , בסתירה למינימליות ${\displaystyle m,n}$ .

כעת נגדיר ${\displaystyle D=\psi [\omega ]}$ , ואז ${\displaystyle \psi :\omega \to D}$ הנה פונקציה חח"ע ועל כנדרש. ${\displaystyle \blacksquare }$