עקרון הסדר הטוב

הגדרה

קבוצה סדורה קווית $(A,<)$ היא סדורה היטב (well-ordered) אם לכל $\varnothing \ne S\subseteq A$ יש מינימום: קיים $m\in S$ עם $m\le s$ לכל $s\in S$.

הדוגמה הקנונית: $(\mathbb{N},<)$ סדורה היטב. $(\mathbb{Z},<)$ אינה סדורה היטב (אין מינימום ל-$\mathbb{Z}$).

1. מבנה קבוצה סדורה היטב

1.1 עוקב מיידי

לכל $a\in A$ שאינו מקסימום, קיים עוקב מיידי $a^{+}$: הוא המינימום של $\{x\in A:x>a\}$.

סימון: $a^{+}$ (לפעמים $a+1$), ומינימום $A$ הוא $0$.

1.2 איבר גבולי

האיבר $a\in A$ נקרא איבר גבולי אם אין לו קודם מיידי ואינו המינימום. (דוגמה: $\omega$ בסדרים הסודרים הכלליים.)

1.3 שלמות

אם $(A,<)$ סדורה היטב ו-$S\subseteq A$ חסומה מלעיל, אז ל-$S$ יש חסם עליון מזערי $(\sup S)$.

הוכחה: $\sup S:=\min \{a\in A:\forall b\in S,a\ge b\}$. הקבוצה לא ריקה (כי $S$ חסומה), ולכן יש לה מינימום. $■$

2. עקרון האינדוקציה הטרנסינסופית

גרסה ראשונה

אם $(A,<)$ סדורה היטב ו-$S\subseteq A$ מקיימת: לכל $a\in A$, אם $\{b\in A:b<a\}\subseteq S$ אז $a\in S$, אז $S=A$.

הוכחה: אם $S\ne A$ אז $A\setminus S\ne \varnothing$, ויש לו מינימום $a_0$. לכל $b<a_0$: $b\notin A\setminus S$, לכן $b\in S$. לפי ההנחה: $a_0\in S$ — סתירה. $■$

גרסה שנייה (שלושה תנאים)

הקבוצה $S\subseteq A$ מקיימת $S=A$ אם:

1. $\min (A)\in S$,
2. אם $a\in S$ אז $a^{+}\in S$,
3. אם $a$ גבולי ו-$\{b:b<a\}\subseteq S$ אז $a\in S$.

3. יחידות אוטומורפיזם

טענת עזר: אם $f:A\to A$ שומרת סדר (חח”ע), אז $f(x)\ge x$ לכל $x$.

הוכחה: בשלילה, אם $f(x_0)<x_0$ עבור $x_0$ מזערי: $f(x_0)=y<x_0$, אבל אז $f(y)\ge y=f(x_0)$, ומכיוון ש-$f$ שומרת סדר ו-$y<x_0$: $f(y)<f(x_0)$ — סתירה.

משפט: אם $f:A\to A$ חח”ע, שומרת סדר, ועל רישא (prefix) של $A$, אז $f=\mathrm{Id}$.

הוכחה: אם $x_0\ne f(x_0)$, מהטענה $f(x_0)>x_0$. קח $x_0$ מזערי כזה. לכל $x<x_0$: $f(x)=x<x_0$, ולכל $x>x_0$: $f(x)>f(x_0)$. לכן $x_0$ לא ב-$\mathrm{Im}(f)$ — סתירה לכך ש-$f$ על רישא כלשהי המכילה $x_0$. $■$

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

4. המשפט המרכזי: השוואת סדרים טובים

משפט: אם $(A,<)$ ו-$(B,<)$ סדורות היטב, אז בדיוק אחד מהבאים מתקיים:

1. $(A,<)\cong (B,<)$ (איזומורפיות).
2. $(A,<)$ איזומורפית לרישא ממש של $(B,<)$.
3. $(B,<)$ איזומורפית לרישא ממש של $(A,<)$.

(רישא של $(A,<)$ היא $A(a):=\{x\in A:x<a\}$ לאיזשהו $a$.)

רעיון ההוכחה: נגדיר $f:=\{(x,y)\in A\times B:A(x)\cong B(y)\}$. מיחידות האיזומורפיזם, $f$ פונקציה חלקית ממ-$A$ ל-$B$ השומרת סדר ומוגדרת על רישא (אפשר רישא ממש, אפשר $A$ כולה). בנסיבות אלה, $f$ היא ביקציה בין רישא של $A$ לרישא של $B$, ממנה נגזרים שלושת המקרים. אי-אפשר שגם $A$ וגם $B$ איזומורפיות לרישא ממש של השנייה, כי זה היה נותן $B\cong$ רישא ממש של $B$, בסתירה לאוטומורפיזם היחיד. $■$

5. תכונות נוספות

אין סדרה אינסופית יורדת

הסדר $(A,<)$ סדורה היטב אם ורק אם אין ב-$A$ סדרה $a_0>a_1>a_2>\cdots$ אינסופית יורדת.

(ההוכחה של “רק אם” משתמשת באקסיומת הבחירה.)

סדר מילוני

אם $(A,{<}_A)$ ו-$(B,{<}_B)$ סדורות היטב, אז המכפלה $A\times B$ עם הסדר המילוני היא סדורה היטב.

ראה גם

• קבוצה סדורה קווית
• איזומורפיזם
• המספרים הממשיים