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

הטענות הבאות שקולות לקבוצה $A$ :

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

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

הוכחה

1 גורר 2

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

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

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

$\psi (a)=\{\begin{array}{cc}a& a\in A\setminus D\\ \phi ({\phi }^{-1}(a)+1)& a\in D\end{array}$

נראה כי $\psi$ חח"ע: יהיו $a_1,a_2\in A$ המקיימים $a_1\ne a_2$, ונפריד למקרים:

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

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

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

לכן $\psi$ פונקציית השקילות הדרושה. $◼$

2 גורר 1

קיימת $B\subset A$ (חלקית ממש) המקיימת $A\sim B$ , לכן קיימת פונקציית שקילות (חח"ע ועל) $\phi :A\to B$ .

כמו כן, נשים לב כי $A\setminus B\ne \varphi$ , לכן יהי $a\in A\setminus B$ .

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

$\psi (0)=a,\psi (n+1)=\phi (\psi (n))$

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

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

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