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

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

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

הוכחה

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

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

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

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

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

• $\phi (a_{0})$
• $\forall x\prec a,\phi (x)\Rightarrow \phi (a)$

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

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

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

דוגמה

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

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

הגדרה: יחס בנוי היטב נאמר כי יחס בינארי ${\mathcal {R}}$ על קבוצה $A$ הוא בנוי היטב, אם ורק אם לכל תת קבוצה לא ריקה $S\subseteq A$ קיים איבר $x_{0}\in S$ כך שלכל $x\in S$ מתקיים $\lnot x{\mathcal {R}}x_{0}$.

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

הוכחה: נניח בשלילה שהקבוצה $S=\{x|\lnot \phi (x)\}$ לא ריקה. אז קיים $x_{0}\in S$ כך שלכל $x\in S$ מתקיים $\lnot x{\mathcal {R}}x_{0}$. לכן לכל $x{\mathcal {R}}x_{0}$ מתקיים $x\not \in S$, כלומר $\phi (x)$, לכן $\phi (x_{0})$ בסתירה לכך ש$x_{0}\in S$.

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

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

הפרק הקודם: תורת הקבוצות האקסיומטית

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

הפרק הבא: סודרים