תורת הקבוצות/סודרים: הבדלים בין גרסאות בדף

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
תוכן שנמחק תוכן שנוסף
שורה 110: שורה 110:


נשים לב שלכל סודר מתקיים <math>\alpha+1=\alpha+S(0)=S(\alpha+0)=S(\alpha)</math>. תכונה זו מאפשרת להחליף בכל מקום את <math>S(\alpha)</math> ב<math>\alpha+1</math>, וכך להפוך את הכתיבה לנוחה יותר. למשל הגדרת החיבור מחדש תהיה <math>\alpha+(\beta+1)=(\alpha+\beta)+1</math>.
נשים לב שלכל סודר מתקיים <math>\alpha+1=\alpha+S(0)=S(\alpha+0)=S(\alpha)</math>. תכונה זו מאפשרת להחליף בכל מקום את <math>S(\alpha)</math> ב<math>\alpha+1</math>, וכך להפוך את הכתיבה לנוחה יותר. למשל הגדרת החיבור מחדש תהיה <math>\alpha+(\beta+1)=(\alpha+\beta)+1</math>.

החיבור מאפשר לנו לתת שמות למספר סודרים שלא יכולנו להתייחס אליהם במפורש לפני כן, כגון <math>\omega+1,\omega+2,...,\omega+n,...,\omega+\omega,...,\omega+\omega+\omega,...</math>.

===כפל===
===כפל===
{{הגדרה|שם=כפל סודרים|תוכן=יהו <math>\alpha,\beta</math> סודרים. נגדיר את המכפלה <math>\alpha\cdot\beta</math> (בקיצור: <math>\alpha\beta</math>) ב[[תורת הקבוצות/אינדוקציה טרנספיניטית|אידוקציה טרנספיניטית]]:
{{הגדרה|שם=כפל סודרים|תוכן=יהו <math>\alpha,\beta</math> סודרים. נגדיר את המכפלה <math>\alpha\cdot\beta</math> (בקיצור: <math>\alpha\beta</math>) ב[[תורת הקבוצות/אינדוקציה טרנספיניטית|אידוקציה טרנספיניטית]]:

גרסה מ־20:20, 28 ביוני 2021

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

הגדרה

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

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

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

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

הגדרה: סודר

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

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


משפט 5.0:

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

לפני שניגש להוכחת המשפט, נביא אקסיומה חשובה ושימושית ממערכת האקסיומות של ZFC - מערכת אקסיומות של תורת הקבוצות האקסיומטית:

אקסיומת היסוד

לכל קבוצה x אם x לא ריקה אז יש איבר כך שלכל מתקיים .

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

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


משפט 5.1:

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


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

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


משפט 5.2:

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


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

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


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

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


משפט 5.3:

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

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



למה 5.4

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


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



למה 5.5

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


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

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

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

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

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

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

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

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


סדר

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

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

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


משפט 5.6:

.

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


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

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

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


הוכחה:

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


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


משפט 5.8:

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


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

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

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


משפט 5.9:

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

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


הוכחה:

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



משפט 5.10:

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


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

אריתמטיקה

חיבור

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

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

  • כאשר גבולי.


משפט 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. (כי גבולי), כלומר . עלינו להצדיק את המעבר : לכל מתקיים (איזוטוניות שמאלית), לכן קיים כך ש. לכן . בנוסף, לכל קיים כך ש , ולכן (איזוטוניות שמאלית, כאשר החלפנו את סימן ה בסימן החלש יותר ). לכן , ובסך הכל .


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

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

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

כפל

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

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

  • כאשר גבולי.

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


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

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


הוכחה:

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