תורת הקבוצות/אינדוקציה טרנספיניטית

תבנית:תורת הקבוצות אינדוקציה טרנספיניטית היא שיטה מוצלחת להוכחת תכונות ולהגדרת פעולות בקבוצות סדורות היטב, המכלילה את עקרון האינדוקציה המתמטית על קבוצת המספרים הטבעיים. מהלך שיטת ההוכחה הוא כך: נניח ש $(A, ≺)$ סדורה היטב, ותהי $ϕ (x)$ טענה לוגית התלויה במשתנים, כאשר משמעות הביטוי $ϕ (x)$ היא ש $ϕ$ טענה נכונה כאשר מציבים את x במקומות הנכונים. כדוגמה, הטענה $ϕ (x) \equiv (\exists y, x + y = 0)$ נכונה לכל $x \in ℝ$ . לעומת זאת, הטענה $ϕ (x) \equiv (x^{2} = x)$ נכונה רק עבור $x = 0, 1$ . נחזור לעקרון האינדוקציה: בהינתן טענה כזו על קבוצה סדורה היטב, יהי $a_{0}$ האיבר הראשון בקבוצה. מתקיימת הטענה הבאה: $(ϕ (a_{0}) \land \forall x \in A (\forall y ≺ x, ϕ (y) \Rightarrow ϕ (x))) \Rightarrow \forall x \in A, ϕ (x)$ . במילים אחרות: אם הוכחנו את הטענה עבור האיבר הראשון, והוכחנו שאם הטענה מתקיימת לכל האיברים שקטנים מאיבר כלשהו אז היא מתקיימת גם לאיבר הזה, אז הטענה מתקיימת לכל האיברים.

עבור הגדרה, רוצים להגדיר אופרטור $f$ על קבוצה סדורה היטב $(A, ≺)$ . אם מגדירים את $f (a_{0})$ , ולכל $a$ מגדירים את $f (a)$ עם התייחסות ל $f (x)$ לכל $x ≺ a$ . אז האופרטור מוגדר לכל איברי הקבוצה.

הוכחה

נוכיח את עקרון האינדוקציה הטרנספיניטית: נניח בשלילה שקיימים איברים שעבורם הטענה לא מתקיימת. נסמן את קבוצת כל האיברים האלו ב $S$ . על פי ההנחה, S אינה ריקה, וברור ש $S \subseteq A$ , לכן יהי $x_{0}$ האיבר הראשון בS. מכך נובע שלכל $x ≺ x_{0}$ , הטענה נכונה לגבי x (אחרת $x_{0}$ אינו הראשון), ומהנחת האינדוקציה נובע ש $ϕ (x_{0})$ , בסתירה לכך ש $x_{0} \in S = {x | \neg ϕ (x)}$ . סתירה.

עבור הגדרה, נגדיר את הטענה $ϕ (x)$ על פי " $f (a)$ מוגדר". ברצוננו להוכיח כי $f (a)$ מוגדר לכל a, כלומר $\forall x \in A, ϕ (x)$ . נשים לב שמהדרך שבה הוגדר האופרטור נובע כי $ϕ (a_{0}) \land \forall a \in A (\forall x ≺ a, ϕ (x) \Rightarrow ϕ (a))$ , לכן מעקרון האינדוקציה עבור הוכחות נובע כי $\forall x \in A, ϕ (x)$ .

טכניקות הוכחה

למעשה, אין צורך להוכיח כי $ϕ (a_{0})$ , כי הטענה $\forall x ≺ a_{0}, ϕ (x)$ מתקיימת באופן ריק, לכן $ϕ (a_{0})$ . למרות זאת נהוג להוכיח $ϕ (a_{0})$ , כי בדרך כלל ההוכחה שמתקיים $\forall x ≺ a, ϕ (x) \Rightarrow ϕ (a)$ נשענת על כך שאכן קיים $x ≺ a$ , ולכן היא תיכשל במקרה $a = a_{0}$ .

נהוגות שתי טכניקות להוכחה באינדוקציה טרנספיניטית: 1. הוכחה כללית, כלומר:

$ϕ (a_{0})$
$\forall x ≺ a, ϕ (x) \Rightarrow ϕ (a)$

2. הוכחה בהתאם למקרים, כלומר:

$ϕ (a_{0})$
מקרה א' - $a$ איבר עוקב, לכן יהי $S (x) = a$ . מכיוון ש $x ≺ S (x) = a$ , הטענה $\forall y ≺ a, ϕ (y)$ גוררת את הטענה $ϕ (x)$ , לכן לובשת ההוכחה צורה של $ϕ (x) \Rightarrow ϕ (S (x))$ .
מקרה ב' - $a$ איבר גבולי, לכן 'אין ברירה', וההוכחה נשארת בתבנית של $\forall x ≺ a, ϕ (x) \Rightarrow ϕ (a)$ .

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

דוגמה

אינדוקציה מתמטית היא בעצם סוג מסוים של אינדוקציה טרנספיניטית: הקבוצה $ℕ$ סדורה היטב (יוכח במהלך הפרק על הסודרים, שם גם נגדיר את הקבוצה), לכן ניתן לפעול לגביה באינדוקציה טרנספיניטית. בהינתן $n = 0$ (הנחנו שכבר הוכחנו את הטענה לגבי 0), ניתן לרשום $n = (n - 1) + 1 : = k + 1$ כאשר $k < n$ . ההנחה $\forall m < n, ϕ (m)$ כוללת בתוכה את הטענה $ϕ (k)$ , לכן הגרירה $ϕ (k) \Rightarrow ϕ (k + 1) \Rightarrow ϕ (n)$ גוררת את הגרירה $(\forall m < n, ϕ (m)) \Rightarrow ϕ (n)$ , לכן הטענה $ϕ (0) \land \forall n \in ℕ (ϕ (n) \Rightarrow ϕ (n + 1))$ גוררת את $ϕ (0) \land \forall n \in ℕ (ϕ (n) \Rightarrow ϕ (n + 1))$ , כלומר את $\forall n \in ℕ, ϕ (n)$ .

אינדוקציה בנויה היטב

תבנית:מבנה תבנית ניתן להכליל את עקרון האינדוקציה הטרנספיניטית לכל יחס בנוי היטב: יהי $(A, ℛ)$ יחס בנוי היטב, ותהי $ϕ$ טענה. נסמן ב $a_{0}$ את האיבר ב $A$ כך שלכל $x \in A$ מתקיים $\neg x ℛ a_{0}$ . אז מתקיים $ϕ (a_{0}) \land \forall a \in A ((\forall x ℛ a, ϕ (x)) \Rightarrow ϕ (a)) \Rightarrow \forall x \in A, ϕ (x)$ : כלומר מפסיק להוכיח את הטענה לגבי האיבר ה"מינימלי" (כלומר האיבר שאף איבר לא עומד ביחס איתו) של הקבוצה, ולהוכיח שאם הטענה נכונה לכל האיברים העומדים ביחס עם איבר כלשהו של הקבוצה אז הטענה נכונה גם לגבי האיבר, כדי להוכיח שהטענה נכונה לכל איברי הקבוצה. תבנית:הוכחה

אינדוקציה על פני כל הקבוצות

על פי אקסיומת היסוד, לכל קבוצה $S$ לא ריקה קיים $x_{0} \in S$ כך שלכל $x \in S$ מתקיים $x \in̸ x_{0}$ . כלומר יחס השייכות על כל הקבוצות הוא יחס בנוי היטב. מכאן שניתן לפעול באינדוקציה בנויה היטב על כל הקבוצות. תבנית:תורת הקבוצות

תורת הקבוצות/אינדוקציה טרנספיניטית

תוכן עניינים

הוכחה

טכניקות הוכחה

דוגמה

אינדוקציה בנויה היטב

אינדוקציה על פני כל הקבוצות

תפריט ניווט

תורת הקבוצות/אינדוקציה טרנספיניטית

הוכחה

טכניקות הוכחה

דוגמה

אינדוקציה בנויה היטב

אינדוקציה על פני כל הקבוצות

תפריט ניווט

חיפוש