תורת הקבוצות/סודרים

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

למספרים הטבעיים יש שני שימושים נחמדים: הראשון הוא במונחים של עוצמה, כלומר "באלף בית העברי יש עשרים ושתים אותיות", שאותו הכללנו לאינסוף במסגרת העוצמות. השני הוא במונחים של סדר, כלומר "ג' היא האות השלישית באלף בית העברי". את שימוש זה נכליל לאינסוף כאן, כשנגדיר את הסודרים.

הגדרה[עריכה]

נגדיר קודם כל מושג עזר:

הגדרה: קבוצה טרנזיטיבית

קבוצה טרנזיטיבית היא קבוצה שכל איבר שלה הוא תת קבוצה שלה, כלומר היא קבוצה טרנזיטיבית אם ורק אם . השם טרנזיטיבית נגזר מכך שיחס השייכות מתנהג בצורה טרנזיטיבית על הקבוצה, כלומר .

כעת נגדיר את הסודרים:

הגדרה: סודר

סודר הוא קבוצה טרנזיטיבית הסדורה היטב ביחס השייכות. כלומר:

  • .
  • לכל תת קבוצה לא ריקה, יש איבר ראשון בקבוצה הסדורה .


משפט 5.0:

אם סדורה מלא ב, אז היא סדורה היטב ב.


הוכחה: נניח ש סדורה מלא. תהי לא ריקה. מאקסיומת היסוד נובע שקיים כך שלכל מתקיים . מכיוון ש סדורה מלא, מתקיים , לכן לכל מתקיים , כלומר איבר ראשון ב. לכן סדורה היטב.

מש"ל.PNG


משפט 5.1:

כל איבר של סודר הוא סודר בעצמו.


הוכחה: נניח ש סודר, וכן . מהטרנזיטיביות של נקבל . תת קבוצה של קבוצה סדורה היטב היא קבוצה סדורה היטב, לכן צריך להוכיח רק ש טרנזיטיבית. מכיוון שהיחס על הוא טרנזיטיבי, נקבל .

מש"ל.PNG

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


משפט 5.2:

אם סודר, אז סודר.


הוכחה: יהי . אז או . במקרה הראשון נקבל . במקרה השני נקבל . בכל מקרה קבוצה טרנזיטיבית. נראה ש סדורה היטב. לצורך כך יש להראות גם כי היא סדורה מלא:

  1. אנטי רפלקסיביות: נפעיל את אקסיומת היסוד על , ונקבל .
  2. טרנזיטיביות: (כי y הוא סודר).
  3. השוואה: נניח ש. אז או שאחד מהם הוא , נניח y, ואז , או ש, ואז , ולכן מתקיימת תכונת ההשוואה כי סודר.


מש"ל.PNG

נגדיר , כלומר , ובאופן כללי .

קיבלנו אוסף נחמד של סודרים, והוא . אלו הם כל הסודרים הסופיים, אך ברצוננו להגדיר גם סודרים אינסופיים. לשם כך נגדיר את אומגה, הסודר האינסופי הראשון: . כלומר אומגה הוא קבוצת המספרים הטבעיים. כעת נוכיח כי אומגה הוא סודר. לשם כך נוכיח טענה חזקה יותר:


משפט 5.3:

אם קבוצה של סודרים, אז הוא סודר.

לפני שנוכיח את המשפט, נקדים מספר למות:



למה 5.4

אם סודרים, אז .


הוכחה: , לכן אינה ריקה. מכיוון ש סודר, הוא סדור היטב ב, ויהי האיבר הראשון ב. מתקיים (מכיוון ש הוא ראשון, ו) כלומר . לכל מתקיים (אחרת מהטרנזיטיביות של נובע ) וכן (אחרת ), ומכך שהיחס על הוא מלא, נקבל , כלומר ובפרט . לכן .

מש"ל.PNG



למה 5.5

לכל סודרים, מתקיים .


הוכחה: נסמן . נראה כי הוא סודר:

  • טרנזיטיביות הקבוצה: .

את תכונת האנטי רפלקסיביות כבר ראינו שאין צורך להוכיח, לכן נוכיח את שאר התכונות:

  • טרנזיטיביות הסדר: .
  • השוואה: .

נניח כי . אז מתקיים , לכן , כלומר , בסתירה לאקסיומת היסוד. לכן נניח כי . אם לא מתקיים , אז , ולכן .

מש"ל.PNG

כעת ניגש להוכיח את משפט 5.3:

הוכחה: נראה את תכונות הסודר:

  • טרנזיטיביות הקבוצה: .
  • טרנזיטיביות הסדר: נניח כי . אז קיימים כך ש. מלמה 4.5 נוכל להניח , לכן , ונקבל .
  • השוואה: באותה דרך נוכל להניח כי . לכן .


מש"ל.PNG

סדר[עריכה]

הגדרה: הסדר על הסודרים

נגדיר את הסדר על הסודרים באופן הבא: .

שילוב העובדה שסודר הוא קבוצה טרנזיטיבית עם למה 5.4 יתן את המשפט הבא:


משפט 5.6:

.

מכאן ואילך נחליף בחופשיות בין הסימונים .


משפט 5.7: תכונות הסדר על הסודרים

הסדר על הסודרים הוא סדר טוב, כלומר:

  • אנטי רפלקסיביות: .
  • טרנזיטיביות: .
  • השוואה: .
  • תכונת הסדר הטוב: לכל קבוצה לא ריקה של סודרים יש איבר ראשון.


הוכחה:

  • אנטי רפלקסיביות: נובע מאקסיומת היסוד כי .
  • טרנזיטיביות: .
  • השוואה: למה 5.5 אומרת בדיוק את טענה זו.
  • תכונת הסדר הטוב: התכונה נובעת מאקסיומת היסוד, אך נראה גם דרך למצוא את האיבר הראשון: תהי קבוצה לא ריקה של סודרים. נגדיר . נראה כי הוא האיבר הראשון ב: יהי האיבר הראשון ב, שקיומו מובטח מאקסיומת היסוד. אז מתקיים לכל , כלומר . מצד שני, , כי , לכן .


מש"ל.PNG

הוכחת משפט 5.7 הדגימה כמה נוח המעבר החופשי בין : בכל סעיף השתמשנו ביחס הנוח ביותר להוכחתו. מכיוון שהסדר על הסודרים הוא טוב, לכל סודר יש עוקב מידי. נראה דרך למצוא את עוקב זה:


משפט 5.8:

העוקב המיידי של סודר הוא . כלומר לא קיים .


הוכחה: נניח בשלילה כי . אז , לכן לא יתכן , ומכך ש נקבל , כלומר , בסתירה לכך ש.

מש"ל.PNG

הגדרה: סודר עוקב; סודר גבולי

יהי סודר. נאמר כי הוא סודר עוקב, אם הוא איבר עוקב (על פי הגדרת איבר עוקב בסדר טוב). נאמר כי הוא סודר גבולי, אם הוא איבר גבולי (על פי הגדרת איבר גבולי בסדר טוב).


משפט 5.9:

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

  • הוא גבולי.
  • .
  • .


הוכחה:

  • יהי גבולי. לכל מתקיים , לכן . יהי . אז , ומכיוון ש גבולי, נקבל , כלומר . לכן . לכן .
  • יהי . נניח שקיים כך ש. לכן . מצד שני, . לכן , כלומר לכל מתקיים , כלומר , ובמילים אחרות . לכן , בסתירה לכך ש.
  • נניח כי אינו גבולי. אז קיים כך ש. כלומר , אבל .


מש"ל.PNG


משפט 5.10:

אם היא קבוצה של סודרים, אז .


הוכחה: לכל מתקיים . אם הוא חסם מלעיל של הקבוצה , אז לכל מתקיים , כלומר .

מש"ל.PNG

אריתמטיקה[עריכה]

חיבור[עריכה]

הגדרה: חיבור סודרים

יהו סודרים. נגדיר את הסכום באינדוקציה טרנספיניטית:

  • כאשר גבולי.


משפט 5.11: תכונות החיבור

  1. הוא איבר נייטרלי: .
  2. אם סודר גבולי, אז סודר גבולי, לכל .
  3. איזוטוניות שמאלית ביחס לסדר חזק: .
  4. איזוטוניות ימנית ביחס לסדר חלש: .
  5. .
  6. אסוציאטיביות: .


הוכחה:

  1. התכונה ברורה מההגדרה. את התכונה נוכיח באינדוקציה טרנספיניטית:
    1. מההגדרה.
    2. נניח . נקבל .
    3. יהי גבולי, ונניח . נקבל .
  2. נניח בשלילה כי . אז . מההגדרה נובע שקיים כך ש. לכן (קל להשתכנע כי פונקצית העוקב שומרת סדר). מכיוון ש, נקבל , בסתירה לאקסיומת היסוד.
  3. באינדוקציה טרנספיניטית על המשתנה :
    1. הטענה לעולם לא נכונה, לכן הטענה נכונה באופן ריק.
    2. נניח כי . נקבל .
    3. יהי גבולי, ונניח כי . נקבל .
  4. באינדוקציה טרנספיניטית על המשתנה :
    1. .
    2. נניח כי . לכל סודרים מתקיים . במקרה הראשון מתקיים , ובמקרה השני , כי הוא העוקב המיידי של , ולכן . בסה"כ בשני המקרים . לכן נקבל: .
    3. יהי גבולי, ונניח . נקבל .
  5. מתקיים , לכן . בנוסף .
  6. באינדוקציה טרנספיניטית:
    1. .
    2. .
    3. (כי גבולי), כלומר . עלינו להצדיק את המעבר : לכל מתקיים (איזוטוניות שמאלית), לכן קיים כך ש. לכן . בנוסף, לכל קיים כך ש , ולכן (איזוטוניות שמאלית, כאשר החלפנו את סימן ה בסימן החלש יותר ). לכן , ובסך הכל .


מש"ל.PNG

כדוגמה, נחשב את : מכיוון ש גבולי, נקבל . דוגמה זו מראה שאין קומוטטיביות, כי .

נשים לב שלכל סודר מתקיים . תכונה זו מאפשרת להחליף בכל מקום את ב, וכך להפוך את הכתיבה לנוחה יותר. למשל הגדרת החיבור מחדש תהיה .

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

כפל[עריכה]

הגדרה: כפל סודרים

יהו סודרים. נגדיר את המכפלה (בקיצור: ) באידוקציה טרנספיניטית:

  • כאשר גבולי.

שימו לב שבהגדרת הכפל החלפנו את ב.


משפט 5.12: תכונות הכפל

  1. הוא איבר נייטרלי: .
  2. הוא איבר מאפס: .
  3. אם גבולי אז גבולי, לכל .
  4. איזוטוניות שמאלית ביחס לסדר חזק: .
  5. איזוטוניות ימנית ביחס לסדר חלש: .
  6. דיסטריבוטיביות ימנית: .
  7. .
  8. אסוציאטיביות: .


הוכחה:

  1. . נוכיח באינדוקציה טרנספיניטית כי :
    1. מההגדרה.
    2. נניח כי . נקבל .
    3. יהי גבולי, ונניח כי . נקבל .
  2. מההגדרה. נוכיח באינדוקציה טרנספיניטית כי :
    1. מההגדרה.
    2. נניח כי . נקבל .
    3. יהי גבולי, ונניח כי . נקבל .
  3. יהי . אז קיים כך ש . לכן . (הסתמכנו על כך ש , לכן , וכן על חוקי האיזוטוניות.)
  4. באינדוקציה טרנספיניטית על המשתנה :
    1. הטענה תמיד לא נכונה, לכן הטענה מתקיימת באופן ריק.
    2. נניח כי . נקבל .
    3. יהי גבולי, ונניח כי . נקבל .
  5. באינדוקציה טרנספיניטית על המשתנה :
    1. .
    2. נניח כי . נקבל .
    3. יהי גבולי, ונניח כי . נקבל .
  6. עבור הטענה ברורה. נניח , ונוכיח באינדוקציה על המשתנה :
    1. .
    2. נניח כי . נקבל .
    3. יהי גבולי, ונניח כי . נקבל: גבולי, לכן . אם נוכיח כי , נקבל . אם נוכיח כי , נקבל (מכיוון ש גבולי, כי הנחנו ) . כעת נראה כי : לכל קיים כך ש, כלומר (כי ), לכן . לכל מתקיים , לכן קיים כך ש, לכן . בסך הכל . כעת נראה כי : לכל מתקיים (כי ), לכן קיים כך ש, לכן . לכל קיים כך ש. לכן , לכן . בסך הכל .
  7. , לכן וכן .
  8. אם או שווים ל, הטענה ברורה. לכן נניח ונוכיח באינדוקציה על :
    1. נניח כי , ונקבל .
    2. יהי גבולי, ונניח כי . נקבל: גבולי (כי ), לכן . אם נוכיח כי , נקבל . כעת נוכיח כי : לכל מתקיים (כי הנחנו ), לכן קיים כך ש, לכן . לכל קיים כך ש, כלומר (כי הנחנו ), לכן . בסך הכל .


מש"ל.PNG

פעולת הכפל מאפשרת לנו לתת שמות נוספים (או שמות קצרים יותר) לסודרים כגון .

חזקה[עריכה]

הגדרה: חזקה של סודרים

יהו סודרים. נגדיר את החזקה באינדוקציה טרנספיניטית:

  • כאשר גבולי.


משפט 5.13: תכונות החזקה

  1. נייטרלי מימין: .
  2. .
  3. אם גבולי, אז גבולי לכל .
  4. איזוטוניות שמאלית ביחס לסדר חזק: .
  5. איזוטוניות ימנית ביחס לסדר חלש: .
  6. .
  7. .


הוכחה:

  1. באינדוקציה טרנפיניטית:
    1. על פי ההגדרה.
    2. נניח כי . אז .
    3. יהי גבולי, ונניח כי . אז .


מש"ל.PNG