הצגת המקור של הדף "עקרון הסדר הטוב"

{{פירוש נוסף|נוכחי=קיומו של [[סדר טוב]] על המספרים הטבעיים|אחר=קיומו של סדר טוב על כל קבוצה שהיא|ראו=[[משפט הסדר הטוב]]}}
ב[[מתמטיקה]], '''עקרון הסדר הטוב''' קובע שה[[סדר חלקי|סדר]] המקובל על ה[[מספר טבעי|מספרים הטבעיים]] הוא [[סדר טוב]]. משמע שבכל [[קבוצה (מתמטיקה)|קבוצה]] לא [[הקבוצה הריקה|ריקה]] של מספרים טבעיים יש [[חסם (מתמטיקה)|מספר מינימלי]] (מספר ראשון). העיקרון שקול ל[[אקסיומת האינדוקציה]], ולעיתים בוחרים להתייחס אליו כאל [[אקסיומה]] במקום אקסיומת האינדוקציה.

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

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

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

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

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

ראשית נוכיח את אקסיומת האינדוקציה על סמך עקרון הסדר הטוב. תהי <math>T</math> קבוצה של טבעיים כך ש-<math>1 \in T</math>, ולכל <math>n \in T</math> מתקיים <math>n+1 \in T</math>. נבחן את הקבוצה <math>\mathbb{N}\setminus T</math> הכוללת את כל הטבעיים שאינם ב-<math>T</math>. [[הוכחה בדרך השלילה|נניח בשלילה]] כי קבוצה זו אינה ריקה. לפי עקרון הסדר הטוב ב-<math>\mathbb{N}\setminus T</math> יש מספר מינימלי <math>m</math>. <math>1 \in T</math>, ולכן <math>m \ne 1</math>. מהמינימליות של <math>m</math> נובע <math>m-1 \not\in \mathbb{N}\setminus T</math>, כלומר <math>m-1 \in T</math>. לכן לפי ההנחה על <math>T</math> מתקבלת הסתירה <math> (m-1)+1 = m \in T</math>. מכאן ש-<math>\mathbb{N}\setminus T</math> ריקה, ו-<math>T=\mathbb{N}</math>.

כעת נוכיח את עקרון הסדר הטוב מתוך אקסיומת האינדוקציה. נגדיר את <math>P(n)</math> בתור הטענה שלכל קבוצה של טבעיים הכוללת מספר <math>k \le n</math> יש מינימום. ברור כי מתקיים <math>P(1)</math>, מכיוון ש-1 הוא המינימום בכל קבוצה של טבעיים שבה הוא חבר. נניח שמתקיים <math>P(n)</math> ונוכיח כי מתקיים <math>P(n+1)</math>.

תהי <math>S</math> קבוצה הכוללת מספר <math>k \le n+1</math>. אם אין ב-<math>S</math> מספר <math>r \le n</math>, אז <math>k = n+1</math> מספר מינימלי ב-<math>S</math>. אם קיים <math>r \le n</math>, אז לפי הנחת האינדוקציה יש ב-<math>S</math> מספר מינימלי. קיבלנו כי מתקיים <math>P(n+1)</math>. מכאן לפי אקסיומת האינדוקציה <math>P(n)</math> מתקיים לכל <math>n</math>.

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

==תכונת ארכימדס==
[[תכונת ארכימדס]] של המספרים הטבעיים נובעת ישירות מעקרון הסדר הטוב. התכונה קובעת כי לכל <math>a, b</math> טבעיים, קיים <math>n</math> טבעי כך ש-<math>na>b</math>. 

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

==ראו גם==
*[[נסיגה אינסופית]]

==קישורים חיצוניים==
* {{MathWorld}}

[[קטגוריה:משפטים בתורת הקבוצות]]
[[קטגוריה:משפטים בתורת המספרים]]
[[קטגוריה:אקסיומות]]
[[קטגוריה:קבוצות סדורות]]
[[קטגוריה:הוכחות]]