סדר טוב

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

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

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

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

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

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

סדר טוב הוא סדר שבו כל תת־קבוצה לא ריקה מתחילה עם איבר ראשון. (איבר ראשון הוא האיבר הקטן ביותר בקבוצה.)

דוגמה פשוטה: המספרים הטבעיים מסודרים היטב. בכל קבוצה של טבעיים יש מספר הכי קטן. אבל בכל השלמים אין מספר ראשון. לכן הם לא מסודרים היטב.

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

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

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