סדר טוב

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

בקבוצה סדורה היטב, לכל איבר (פרט לאיבר המקסימלי, אם יש כזה) יש איבר עוקב מיידי‏[1] וכל חתך‏[2] הוא או הקבוצה כולה או קטע התחלי.‏[3]

טיפוס הסדר של קבוצה סדורה בסדר טוב נקרא מספר סודר.

מחלקת הקבוצות הסדורות היטב[עריכת קוד מקור | עריכה]

ארבע תכונות חשובות נוספות מתקיימות על מחלקת הסדרים. תכונות אלה מראות כי מחלקת הסדרים המלאים מסודרת בסדר מלא, ביחס לפעולה  Q \le P אם ורק אם  Q \cong P או  Q \cong P_x .

  1. אי-סימטריות: משפט קנטור ברנשטיין חל גם על סדרים טובים, כלומר אם  (P , \le)  (Q , \le) סדרים טובים וניתן לשכן את P ב-Q וניתן לשכן את Q ב-P אז הסדרים איזומורפיים.
  2. השוואתיות: כל שני סדרים טובים ניתנים להשוואה, כלומר אם  (P , \le)  (Q , \le) סדרים טובים, אז או ש \ Q \cong P או ש \ Q \cong P_x (כאשר P_x קטע התחלי של P ) או ש  Q_y \cong P (כאשר \ Q_y קטע התחלי של Q).
  3. רפלקסיביות: תכונה זו מתקיימת באופן טריוויאלי באמצעות פונקציית הזהות.
  4. טרנזטיביות : לפי אופן הרכבת פונקציות איזומורפיות אם  (M , \le)  (P , \le)  (Q , \le) סדרים טובים ו \ f : Q \rightarrow P \ g : P \rightarrow M איזומורפיזמים, אז גם \ g \circ f : Q \rightarrow M איזומורפיזם ולכן אם Q \le P וגם P \le M אז Q \le M.

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

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

טענה:  (Q , \le) מסודרת היטב אם ורק אם אין בה סדרה אינסופית יורדת.

הוכחת כיוון ראשון : נניח ש- Q לא מסודרת היטב ונבנה סדרה אינסופית יורדת. Q לא מסודרת היטב פירושו שקיימת תת-קבוצה P לא ריקה שאין בה איבר ראשון, נבחר איבר \ p_0 האיבר 
 p_0 הוא לא הראשון ולכן קיים 
 p_1 כך ש \ p_0 > p_1, אבל גם \ p_1 הוא לא האיבר הקטן ביותר בקבוצה ולכן קיים \ p_2 כך ש \ p_0 > p_1 > p_2 ונמשיך בבניה הזו לכל p_n , n \in N וזו סדרה אינסופית יורדת.

הוכחת כיוון שני: ננית שקיימת סדרה אינסופית יורדת ונראה ש-Q לא מסודרת היטב. נגדיר קבוצה P שמכילה את כל אברי הסדרה היורדת ורק אותם, ולכן P היא מהצורה  P = \left\{p_0 > p_1 > p_2 > p_3 ...\right\} ובתת קבוצה זו אין איבר ראשון, ולכן Q מכילה קבוצה שאין לה איבר ראשון ולכן Q לא מסודרת היטב.

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

  1. ^ איבר \ y נקרא עוקב מיידי של \ x אם \ y > x ואין איבר z \in Q כך ש \ y > z > x
  2. ^ תת-קבוצה M היא חתך של Q אם לכל c \in M , אם \ d < c אז  d \in M
  3. ^ קטע התחלי (רישא): הוא קבוצה מהצורה  S_x = \left\{y \in Q : y < x \right\}