סדר טוב

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

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

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

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

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

ארבע תכונות חשובות נוספות מתקיימות על מחלקת הסדרים. תכונות אלה מראות כי מחלקת הסדרים המלאים מסודרת בסדר מלא, ביחס לפעולה ${\displaystyle Q\leq P}$  אם ורק אם ${\displaystyle Q\cong P}$  או ${\displaystyle Q\cong P_{x}}$ .

1. אי-סימטריות: משפט קנטור ברנשטיין חל גם על סדרים טובים, כלומר אם ${\displaystyle (P,\leq )}$  ${\displaystyle (Q,\leq )}$  סדרים טובים וניתן לשכן את ${\displaystyle P}$  ב-${\displaystyle Q}$  וניתן לשכן את ${\displaystyle Q}$  ב-${\displaystyle P}$  אז הסדרים איזומורפיים.
2. השוואתיות: כל שני סדרים טובים ניתנים להשוואה, כלומר אם ${\displaystyle (P,\leq )}$  ${\displaystyle (Q,\leq )}$  סדרים טובים, אז או ש-${\displaystyle Q\cong P}$  או ש-${\displaystyle Q\cong P_{x}}$  (כאשר ${\displaystyle P_{x}}$  קטע התחלי של ${\displaystyle P}$  ) או ש-${\displaystyle Q_{y}\cong P}$  (כאשר ${\displaystyle Q_{y}}$  קטע התחלי של ${\displaystyle Q}$ ).
3. רפלקסיביות: תכונה זו מתקיימת באופן טריוויאלי באמצעות פונקציית הזהות.
4. טרנזטיביות : לפי אופן הרכבת פונקציות איזומורפיות אם ${\displaystyle (M,\leq )}$  ${\displaystyle (P,\leq )}$  ${\displaystyle (Q,\leq )}$  סדרים טובים ו-${\displaystyle f:Q\rightarrow P}$  ${\displaystyle g:P\rightarrow M}$  איזומורפיזמים, אז גם ${\displaystyle g\circ f:Q\rightarrow M}$  איזומורפיזם ולכן אם ${\displaystyle Q\leq P}$  וגם ${\displaystyle P\leq M}$  אז ${\displaystyle Q\leq M}$ .

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

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

הוכחת כיוון ראשון : נניח ש-${\displaystyle Q}$  לא מסודרת היטב ונבנה סדרה אינסופית יורדת. ${\displaystyle Q}$  לא מסודרת היטב פירושו שקיימת תת-קבוצה ${\displaystyle P}$  לא ריקה שאין בה איבר ראשון, נבחר איבר ${\displaystyle p_{0}}$ , האיבר ${\displaystyle p_{0}}$  הוא לא הראשון ולכן קיים ${\displaystyle p_{1}}$  כך ש ${\displaystyle p_{0}>p_{1}}$ , אבל גם ${\displaystyle p_{1}}$  הוא לא האיבר הקטן ביותר בקבוצה ולכן קיים ${\displaystyle p_{2}}$  כך ש ${\displaystyle p_{0}>p_{1}>p_{2}}$  ונמשיך בבניה הזו לכל ${\displaystyle p_{n},n\in N}$  וזו סדרה אינסופית יורדת.

הוכחת כיוון שני: נניח שקיימת סדרה אינסופית יורדת ונראה ש-${\displaystyle Q}$  לא מסודרת היטב. נגדיר קבוצה ${\displaystyle P}$  שמכילה את כל אברי הסדרה היורדת ורק אותם, ולכן ${\displaystyle P}$  היא מהצורה ${\displaystyle P=\left\{p_{0}>p_{1}>p_{2}>p_{3}...\right\}}$  ובתת קבוצה זו אין איבר ראשון, ולכן ${\displaystyle Q}$  מכילה קבוצה שאין לה איבר ראשון ולכן ${\displaystyle Q}$  לא מסודרת היטב.