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

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

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

עקרון הסדר הטוב כטענה לוגית

עקרון הסדר הטוב קובע כי לכל תת-קבוצה $T\subseteq \mathbb {N}$ לא-ריקה, קיים מספר $a\in T$ עבורו $a\leq b$ לכל $b\in T$ .

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

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

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

שקילות לאקסיומת האינדוקציה

אקסיומת האינדוקציה קובעת כי לכל $T\subseteq \mathbb {N}$ שעבורה $1\in T$ , ולכל $n$ – אם $n\in T$ גורר $n+1\in T$ , אז $T=\mathbb {N}$ . נוכיח שהאקסיומה שקולה לעקרון הסדר הטוב.

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

• תהי $T$ קבוצת טבעיים עבורה $1\in T$ , ולכל $n\in T$ מתקיים $n+1\in T$ .

נבחן את הקבוצה $\mathbb {N} \setminus T$ הכוללת את כל הטבעיים שאינם ב-$T$ . נניח בשלילה כי קבוצה זו אינה ריקה. לפי עקרון הסדר הטוב ב-$\mathbb {N} \setminus T$ יש מספר מינימלי $m$ .

$1\in T$ , ולכן $m\neq 1$ . מהמינימליות של $m$ נובע $m-1\notin (\mathbb {N} \setminus T)$ , כלומר $m-1\in T$ . לכן לפי ההנחה על $T$ מתקבלת הסתירה $(m-1)+1=m\in T$ .

מכאן $\mathbb {N} \setminus T$ ריקה, ולכן $T=\mathbb {N}$ .

כעת נוכיח את עקרון הסדר הטוב מתוך אקסיומת האינדוקציה:

• נגדיר את $P(n)$ בתור הטענה שלכל קבוצת טבעיים הכוללת מספר $k\leq n$ יש מינימום.

ברור כי מתקיים $P(1)$ , מפני ש-1 הוא המינימום בכל קבוצת טבעיים בה הוא חבר. נניח שמתקיים $P(n)$ ונוכיח כי מתקיים $P(n+1)$ .

תהי $S$ קבוצה הכוללת מספר $k\leq n+1$ .

אם לא קיים ב-$S$ מספר $r\leq n$ , אז $k=n+1$ מספר מינימלי ב-$S$ .

אם קיים ב-$S$ מספר $r\leq n$ , אז לפי הנחת האינדוקציה קיים מספר מינימלי ב-$S$ .

קיבלנו כי מתקיים $P(n+1)$ . מכאן לפי אקסיומת האינדוקציה $P(n)$ מתקיים לכל $n$ .

תהי $T$ קבוצה לא-ריקה של טבעיים. נבחר $n\in T$ . מכיוון שמתקיים $P(n)$ ו-$n\leq n$ , הרי שקיים ב-$T$ מספר מינימלי.

תכונת ארכימדס

תכונת ארכימדס של המספרים הטבעיים נובעת ישירות מעקרון הסדר הטוב. התכונה קובעת כי לכל $a,b$ טבעיים, קיים $n$ טבעי עבורו $na>b$ .

נניח בשלילה כי קיימים $a,b\in \mathbb {N}$ כך שלכל $n\in \mathbb {N}$ מתקיים $na<b$ . אזי הקבוצה $T=\{b-an:n\in \mathbb {N} \}$ כוללת רק טבעיים.

לפי עקרון הסדר הטוב קיים $m$ עבורו $b-ma\in T$ מינימלי. אולם לפי הגדרת $T$ גם $b-(m+1)a\in T$ , ומתקיים $b-(m+1)a=(b-ma)-a<b-ma$ . סתירה.

ראו גם

• נסיגה אינסופית