מספר סודר

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
לחצו כדי להקטין חזרה
0 1 2 3 4 5 אומגה (מספר סודר)Omega-exp-omega-labeled.svg

לדף הקובץ
תמונה אינטראקטיבית (לחצו להסבר)‏

תצוגה גרפית של כל הסודרים מ-0 עד \omega^\omega

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

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

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

ω + 1, ω + 2, …, ω·2, ω·2 + 1, …, ω2, …, ω3, …, ωω, …, ωωω, …, ε0, ….

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

הגדרה[עריכת קוד מקור | עריכה]

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

  1. \alpha קבוצה טרנזיטיבית.
  2. \alpha סדורה היטב ביחס השייכות. (כלומר, אם נגדיר <_\alpha כך ש-x<_\alpha y \iff x\in y עבור x,y \in\alpha אזי <_\alpha יחס סדר טוב)

התכונה הראשונה שמופיעה מטה מאפשרת לנו להגדיר סדר בין סודרים: עבור \alpha,\beta סודרים \alpha<\beta \iff \alpha\in\beta. סדר זה הינו סדר טוב.

נגדיר גם את פעולת העוקב: S(\alpha)=\alpha\cup \{\alpha\}.

סודר \alpha יקרא סודר עוקב אם קיים סודר אחר \beta כך שמתקיים \alpha=S(\beta), וסודר גבולי אחרת. (לעתים לא מתייחסים ל-0 כאל סודר גבולי מטעמי נוחות)
סודר מונה (לעתים נקרא סודר פותח) הוא סודר שאינו שווה עוצמה לאף סודר קטן יותר.

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

הסודרים הסופיים[עריכת קוד מקור | עריכה]

סודר נקרא סודר סופי אם הוא 0=\{\}=\empty או שהוא עוקב של סודר סופי.

בניית המספרים הטבעיים של ג'ון פון נוימן מתלכדת עם המספרים הסודרים הסופיים:

  • 0=\{\}=\empty
  • 1=S(0)=\{0\}=\{\empty\}
  • 2=S(1)=\{0,1\}=\{\empty,\{\empty\}\}
  • 3=S(2)=\{0,1,2\}=\{\empty,\{\empty\}, \{\empty,\{\empty\}\}\}
  • ...
  • n=S(n-1)=\{0,1,2,...,n-1\}

הסודרים הסופיים הינם סודרים עוקבים וסודרים מונים.

סודרים נוספים[עריכת קוד מקור | עריכה]

המחשה של מבנה המספרים הסודרים: אינסוף סדרות של מספרים אינסופיים.

לפי אקסיומת הקבוצה האינסופית קיימת קבוצת כל הסודרים הסופיים.
קבוצה זו, \omega=\bigcup_n n=\{0,1,2,...\}, הינה הסודר האינסופי הקטן ביותר.

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

  • \omega+1=S(\omega)=\omega\cup \{\omega\}=\{0,1,2,...,\omega\}
  • \omega\cdot 2=0\cup 1\cup 2\cup ...\cup \omega\cup \omega+1\cup \omega+2\cup ...=\{0,1,2,...,\omega,\omega+1,\omega+2,...\}

תכונות[עריכת קוד מקור | עריכה]

  • כל איבר של סודר הינו סודר בעצמו.
  • אם \alpha סודר אז גם \alpha\cup \{\alpha\} סודר.
  • אם A הוא קבוצה של סודרים אז \bigcup_{\alpha\in A} \alpha הינו סודר.
  • אם A הוא קבוצה (או מחלקה) של סודרים אז \bigcap_{\alpha\in A} \alpha הינו סודר. סודר זה הוא המינימום ב-A.
  • עבור שני סודרים \alpha,\beta מתקיים בדיוק אחד מהבאים: \alpha=\beta, \alpha<\beta או \beta<\alpha.
  • קבוצת הסודרים הסופיים מהווים מודל לתורה של אקסיומות פאנו.

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

לכל קבוצה וסדר טוב שלה (A,\leq) קיים ויחיד סודר \alpha כך ש-A\cong \alpha, כאשר הסימון \cong מציין שקיים איזומורפיזם ביניהן (פונקציה חד-חד-ערכית ועל ששומרת את הסדר בין האיברים).
\alpha נקרא טיפוס הסדר של (A,\leq) ומסומן \mathrm{ort}(A,\leq).
נציין כי פעמים רבות ניתן להגדיר מספר סדרים טובים על אותה קבוצה והם יכולים להשרות טיפוס סדר שונה.

מהתכונה הנ"ל ניתן להסיק תכונה מעניינת נוספת: תהי קבוצה שניתנת לסידור טוב A (כלומר שניתן להגדיר עליה סדר טוב אחד או יותר). נסתכל על קבוצת הסודרים שאיזומורפיים לה O=\{\mathrm{ort}(A,\leq)|\leq \text{well order of }A\}=\{\alpha|\alpha \text{ ordinal}, A\cong \alpha\}. הקבוצה O הינה קבוצה של סודרים. כפי שאמרנו, חיתוך של קבוצת סודרים הינה סודרים, ולכן \bigcap O=\min O סודר.
כעת נוכל להגדיר את העוצמה של הקבוצה A כסודר המינימלי שאיזומורפי לה, קרי: \mathrm{card}(A)=|A|=\min O=\bigcap O.
ניתן להראות שסודר מסוג זה הינו תמיד סודר מונה.

הקשר בין סודרים לעוצמות[עריכת קוד מקור | עריכה]

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

נוכל להגדיר את המספרים המונים בתור הסודרים המונים.
באופן זה נזהה כל מונה כסודר המונה שעוצמתו היא המונה הנ"ל, למשל את \aleph_0 נזהה עם \omega.

תחת הגדרה זו ישנה טריכוטומיה בין עוצמות של קבוצות, כלומר, עבור שתי קבוצות A,B מתקיים בדיוק אחד מהבאים: |A|=|B|, |A|<|B| או |B|<|A|. (איננו יודעים עובדה זו ללא אקסיומת הבחירה)

פעולות בין סודרים[עריכת קוד מקור | עריכה]

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

לרוע המזל, פעולות על סודרים לעתים לא מתלכדות עם פעולות על מונים. למשל, ציינו כי אנחנו מזהים את \omega עם \aleph_0, אולם לפי ההגדרה מטה 2^\omega=\omega בעוד שלפי משפט קנטור 2^{\aleph_0}>\aleph_0.

חיבור[עריכת קוד מקור | עריכה]

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

הגדרה 1[עריכת קוד מקור | עריכה]

הגדרה זו היא הגדרה אינדוקטיבית.

  • \alpha+0=\alpha עבור חיבור 0
  • \alpha+(\beta+1)=(\alpha+\beta)+1=S(\alpha+\beta) עבור חיבור סודר עוקב \beta+1
  • \alpha+\beta=\bigcup_{\gamma<\beta} \alpha+\gamma עבור חיבור סודר גבולי \beta

הגדרה 2[עריכת קוד מקור | עריכה]

נגדיר את \alpha+\beta באופן הבא: נסתכל על \alpha\times \{0\}\cup\beta\times \{1\} יחד עם יחס הסדר בו איברי \alpha שומרים על סדרם הפנימי, איברי \beta שומרים על סדרם הפנימי ואיברי \alpha קטנים מאיברי \beta, ניתן להראות כי יחס סדר זה הוא יחס סדר טוב. כעת ניתן להגדיר את החיבור כטיפוס הסדר (ראה הגדרה מעלה) של האיחוד הנ"ל תחת יחס הסדר המדובר: \alpha+\beta=\mathrm{ort}(\alpha\times \{0\}\cup\beta\times \{1\},\leq).

ניתן להראות כי שתי ההגדרות שהוצגו שקולות זו לזו.

כפל[עריכת קוד מקור | עריכה]

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

הגדרה 1[עריכת קוד מקור | עריכה]

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

  • \alpha\cdot 0=0 עבור כפל ב-0
  • \alpha\cdot (\beta+1)=(\alpha\cdot \beta)+\beta עבור כפל בסודר עוקב \beta+1
  • \alpha\cdot \beta=\bigcup_{\gamma<\beta} \alpha\cdot \gamma עבור כפל בסודר גבולי \beta

הגדרה 2[עריכת קוד מקור | עריכה]

באופן דומה להגדרת החיבור השנייה, נגדיר \alpha\cdot \beta=\mathrm{ort}(\alpha\times\beta, \leq) כאשר יחס הסדר הוא יחס הסדר הלקסיקוגרפי.

חזקה[עריכת קוד מקור | עריכה]

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

  • \alpha^0=1 עבור העלאה בחזקת 0
  • \alpha^{\beta+1}=(\alpha^\beta)\cdot \alpha עבור העלאה בחזקת סודר עוקב \beta+1
  • \alpha^\beta=\bigcup_{\gamma<\beta} \alpha^\gamma עבור העלאה בחזקת סודר גבולי \beta

קישורים חיצוניים[עריכת קוד מקור | עריכה]

נושאים בתורת הקבוצות

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