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

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

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

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

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

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

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

שקילות לאקסיומת האינדוקציה[עריכת קוד מקור | עריכה]

אקסיומת האינדוקציה קובעת שלכל $\ 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\not \in \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$ . אם קיים $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}$ מתקיים $an<b$ . אזי הקבוצה $T=\{b-an|n\in \mathbb {N} \}$ כוללת רק טבעיים. לפי עקרון הסדר הטוב קיים $m$ כך ש- $b-ma$ מינימלי ב- $T$ . אולם לפי הגדרת $T$ גם $b-(m+1)a$ איבר של $T$ , ומתקיים $b-(m+1)a=(b-ma)-a<b-ma$ בסתירה למינימליות של $b-ma$ .