שינויים
<math>a_{n+1}=a_n^2+1/4<(1/2)^2+1/4 =1/2</math>
==הכללות==
וסיימנו
עוד תרגילים [[מכינה למתמטיקה קיץ תשעב/תרגילים/4]]
חישבו איפה השגיאה (רמז: במעבר מ <math>n=1</math> ל <math>n=2</math>)
==סדר טוב - העשרה מתקדמת ביותר, לא להעביר לשנה א ==
הגדרה: יהי <math>R</math> יחס סדר חלקי על קבוצה <math>A</math>.
<math>R</math> יקרא '''סדר טוב''' אם לכל <math>\emptyset \neq B\subseteq A</math> קיים איבר מינימום/הכי קטן/ראשון ב <math>B</math>.
מינוח: נאמר כי <math>A</math> '''סדורה היטב'''.
דוגמא: הקס"ח <math>(\{1,2,3\},\le)</math> היא סדורה היטב - תתי הקבוצות הלא ריקות שלה הן <math>\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}</math> והאיבר הראשון בכל תת קבוצה הוא בהתאמה <math>1,2,3,1,2,1,1</math>.
===עקרון הסדר הטוב===
נסתכל על <math>(\mathbb{N},\le)</math> - קבוצת הטבעיים עם יחס הסדר "קטן שווה" הסטנדרטי.
אינטואיטיבית, אכן מתקיים כי לכל קבוצה לא ריקה של טבעיים קיים איבר ראשון - "אם 1 שם, הוא הקטן ביותר; אם 2 שם, הוא הקטן ביותר; ''ממשיכים כך'' עד שמגיעים לאיבר כלשהו (כי הקבוצה לא ריקה), והוא הקטן ביותר".
פורמלית, טענה זו, הנקראת '''עקרון הסדר הטוב''', והיא '''שקולה''' לטענת (/אקסיומת) האינדוקציה.
דוגמא נוספת: ניתן להגדיר אל <math>\mathbb{Q}_+</math> יחס סדר חלקי לפי התמונה הבא (כאשר מזהים כל שבר עם זוג סדור ומבטלים את החזרות המיותרות)
[[קובץ:NutualSquareEqNutural.jpeg]]
התבוננו והשתכנעו שזה גם סדר טוב.
הערה: זה בניגוד לסדר "קטן שווה" הרגיל על השברים שאינו סדר טוב כי לקבוצה
<math>\{x\in \mathbb{Q}_+ | \sqrt{2}<x \}</math> אין איבר מינימום.
===משפט הסדר הטוב===
משפט הסדר הטוב קובע שלכל קבוצה <math>A</math> קיים סדר טוב.
תרגיל:
תהא <math>A</math> קבוצה בת מנייה. הוכח כי ניתן לסדר אותה היטב (בהינתן עקרון הסדר הטוב).
פתרון:
לפי הנתון קיימת פונקציה חח"ע ועל <math>f:A\to \mathbb{N} </math>.
נגדיר את היחס הבא על <math>A</math> כך: <math>x\leq y \iff f(x)\leq f(y) </math>. זהו יחס סדר (השתכנעו!).
בנוסף, <math>A</math> סדורה היטב על ידו: תהא <math>B\subseteq A</math> תת קבוצה לא ריקה. אזי <math>f(B)\subseteq\mathbb{N}</math> תת קבוצה לא ריקה ולכן קיים בה איבר מינימום נסמנו <math>n</math>. בדקו כי
<math>f^{-1}(n)\in B</math> איבר מינימום.
==== הכללה עקרון האינדוקציה בעזרת קבוצות סדורות היטב ====
תהא <math>A</math> קבוצה סדורה היטב (נסמן את היחס שלה ב<math>\leq</math>) אזי:
* '''אם''' <math>\forall n ([\forall m<n P(m)] \to P(n))</math>
*אז <math>P</math> מתקיימת לכל <math>a\in A</math>
למה זה עובד?
נניח בשלילה כי הטענה <math>P</math> לא מתקיימת לכל <math>a\in A</math>
אזי נגדיר <math>D:=\{a\in A | P(a)=FALSE \}</math> - קבוצת כל האיברים ב <math>A</math> שעבורם הטענה אינה נכונה. מהנחת השלילה <math>D\neq \emptyset</math>.
כיוון ש <math>A</math> סדורה היטב אזי קיים ב <math>D</math> מינימום, נסמנו <math>d</math>. לפי הגדרת מינימום והגדרת <math>D</math> נובע כי לכל <math>m<d</math> הטענה נכונה (אם היה <math>m<d</math> שהטענה לא נכונה לגביו אזי הוא היה בקבוצה <math>D</math> ואז זה היה סתירה לכך ש <math>d</math> מינימום של קבוצה זאת).
אבל אם זה כך אז לפי הטענה שמוכיחים זה גורר כי <math>d</math> כן מתקיים. סתירה. ולכן הטענה נכונה לכל <math>a\in A</math>
הערה: אפשר לעשות אינדוקציה הנקראת אינדוקציה טרנספניטית על קבוצות כלשהן (לאו דווקא בנות מניה)
