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

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

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

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

הוכחה

1 גורר 2

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

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

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

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

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

• $a_{1},a_{2}\in A\setminus D$ , כאן $\psi (a_{1})=a_{1}\neq a_{2}=\psi (a_{2})$.
• $a_{1},a_{2}\in D$ , מתקיים $\varphi ^{-1}(a_{1})\neq \varphi ^{-1}(a_{2})$ , לכן גם $\varphi (\varphi ^{-1}(a_{1})+1)\neq \varphi (\varphi ^{-1}(a_{2})+1)$ (וזאת כיון ש- $\varphi$ פונקציית שקילות).
• $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 \varphi (0)=(A\setminus D)\cup (D\setminus \varphi (0))$ , ונפריד למקרים:

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

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

2 גורר 1

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

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

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

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

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

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

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