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

הטענות הבאות שקולות לקבוצה <math>A</math> :
#קיימת <math>D\subseteq A</math> המקיימת <math>D\sim\omega</math> .
#קיימת <math>B\subset A</math> (חלקית ממש) המקיימת <math>A\sim B</math> .

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

;הוכחה
====1 גורר 2====
קיימת <math>D\subseteq A</math> המקיימת <math>D\sim\omega</math> , לכן קיימת פונקציית שקילות (חח"ע ועל) <math>\varphi\colon\omega\to D</math> .

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

נגדיר <math>\psi\colon A\to B</math> באופן הבא:

:<math>\psi(a)=\begin{cases}a&a\in A\setminus D\\\varphi(\varphi^{-1}(a)+1)&a\in D\end{cases}</math>

נראה כי <math>\psi</math> חח"ע: יהיו <math>a_1,a_2\in A</math> המקיימים <math>a_1\ne a_2</math>, ונפריד למקרים:
*<math>a_1,a_2\in A\setminus D</math> , כאן <math>\psi(a_1)=a_1\ne a_2=\psi(a_2)</math>.
*<math>a_1,a_2\in D</math> , מתקיים <math>\varphi^{-1}(a_1)\ne\varphi^{-1}(a_2)</math> , לכן גם <math>\varphi(\varphi^{-1}(a_1)+1)\ne\varphi(\varphi^{-1}(a_2)+1)</math> (וזאת כיון ש- <math>\varphi</math> פונקציית שקילות).
*<math>a_1\in D,a_2\in A\setminus D</math> , כאן <math>\psi(a_1)\in D</math> בעוד <math>\psi(a_2)\in A\setminus D</math> .

נראה כי <math>\psi</math> על: יהי <math>y\in B=A\setminus\varphi(0)=(A\setminus D)\cup(D\setminus\varphi(0))</math> , ונפריד למקרים:
*<math>y\in A\setminus D</math> , אזי <math>\psi(y)=y</math> .
*<math>y\in D\setminus\varphi(0)</math> , אזי <math>\psi(\varphi(\varphi^{-1}(y)-1))=y</math> .

לכן <math>\psi</math> פונקציית השקילות הדרושה. <math>\blacksquare</math>

==== 2 גורר 1 ====
קיימת <math>B\subset A</math> (חלקית ממש) המקיימת <math>A\sim B</math> , לכן קיימת פונקציית שקילות (חח"ע ועל) <math>\varphi\colon A\to B</math> .

כמו כן, נשים לב כי <math>A\setminus B\ne\phi</math> , לכן יהי <math>a\in A\setminus B</math> .

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

:<math>\psi(0)=a\ ,\ \psi(n+1)=\varphi(\psi(n))</math>

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

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

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

[[קטגוריה:הוכחות מתמטיות (ספר)]]