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

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

  1. קיימת המקיימת .
  2. קיימת (חלקית ממש) המקיימת .

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

הוכחה

1 גורר 2

עריכה

קיימת   המקיימת   , לכן קיימת פונקציית שקילות (חח"ע ועל)   .

נגדיר   , ונראה שהיא אכן שקולה ל-   .

נגדיר   באופן הבא:

 

נראה כי   חח"ע: יהיו   המקיימים  , ונפריד למקרים:

  •   , כאן  .
  •   , מתקיים   , לכן גם   (וזאת כיון ש-   פונקציית שקילות).
  •   , כאן   בעוד   .

נראה כי   על: יהי   , ונפריד למקרים:

  •   , אזי   .
  •   , אזי   .

לכן   פונקציית השקילות הדרושה.  

2 גורר 1

עריכה

קיימת   (חלקית ממש) המקיימת   , לכן קיימת פונקציית שקילות (חח"ע ועל)   .

כמו כן, נשים לב כי   , לכן יהי   .

נגדיר פונקציה   באופן הבא:

 

נניח בשלילה שהיא אינה חח"ע, אזי קיים זוג מינימלי   עבורו   .

אך אם נפעיל על שני האגפים את   נקבל   , בסתירה למינימליות   .

כעת נגדיר   , ואז   הנה פונקציה חח"ע ועל כנדרש.