תורת הקבוצות/אינדוקציה טרנספיניטית: הבדלים בין גרסאות בדף

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה
שורה 3: שורה 3:
==הוכחה==
==הוכחה==
נוכיח את עקרון האינדוקציה הטרנספיניטית: נניח בשלילה שקיימים איברים שעבורם הטענה לא מתקיימת. נסמן את קבוצת כל האיברים האלו ב<math>S</math>. על פי ההנחה, S אינה ריקה, וברור ש<math>S\subseteq A</math>, לכן יהי <math>x_0</math> האיבר הראשון בS. מכך נובע שלכל <math>x\prec x_0</math>, הטענה נכונה לגבי x (אחרת <math>x_0</math> אינו הראשון), ומהנחת האינדוקציה נובע ש <math>\phi(x_0)</math>, בסתירה לכך ש<math>x_0\in S=\{x|\lnot\phi(x)\}</math>. סתירה.
נוכיח את עקרון האינדוקציה הטרנספיניטית: נניח בשלילה שקיימים איברים שעבורם הטענה לא מתקיימת. נסמן את קבוצת כל האיברים האלו ב<math>S</math>. על פי ההנחה, S אינה ריקה, וברור ש<math>S\subseteq A</math>, לכן יהי <math>x_0</math> האיבר הראשון בS. מכך נובע שלכל <math>x\prec x_0</math>, הטענה נכונה לגבי x (אחרת <math>x_0</math> אינו הראשון), ומהנחת האינדוקציה נובע ש <math>\phi(x_0)</math>, בסתירה לכך ש<math>x_0\in S=\{x|\lnot\phi(x)\}</math>. סתירה.
==טכניקות הוכחה==
למעשה, אין צורך להוכיח כי <math>\phi(a_0)</math>, כי הטענה <math>\forall x\prec a_0,\phi(x)</math> מתקיימת באופן ריק, לכן <math>\phi(a_0)</math>. למרות זאת נהוג להוכיח <math>\phi(a_0)</math>, כי בדרך כלל ההוכחה שמתקיים <math>\forall x\prec a,\phi(x)\Rightarrow\phi(a)</math> נשענת על כך שאכן קיים <math>x\prec a</math>, ולכן היא תיכשל במקרה <math>a=a_0</math>.

נהוגות שתי טכניקות להוכחה באינדוקציה טרנספיניטית:
# הוכחה כללית, כלומר:
* <math>\phi(a_0)</math>
* <math>\forall x\prec a,\phi(x)\Rightarrow\phi(a)</math>
# הוכחה בהתאם למקרים, כלומר:
* <math>\phi(a_0)</math>
* מקרה א' - <math>a</math> [[תורת הקבוצות/יחסי סדר#יחס סדר טוב|איבר עוקב]], לכן יהי <math>S(x)=a</math>. מכיוון ש<math>x\prec S(x)=a</math>, הטענה <math>\forall y\prec a,\phi(y)</math> גוררת את הטענה <math>\phi(x)</math>, לכן לובשת ההוכחה צורה של <math>\phi(x)\Rightarrow\phi(S(x))</math>.
* מקרה ב' - <math>a</math> [[תורת הקבוצות/יחסי סדר#יחס סדר טוב|איבר גבולי]], לכן 'אין ברירה', וההוכחה נשארת בתבנית של <math>\forall x\prec a,\phi(x)\Rightarrow\phi(a)</math>.
הטכניקה השנייה נפוצה ונוחה יותר, ובה נשתמש בדרך כלל בפרק [[סודרים]].

==דוגמה==
==דוגמה==
* אינדוקציה מתמטית היא בעצם סוג מסוים של אינדוקציה טרנספיניטית: הקבוצה <math>\N</math> סדורה היטב (יוכח במהלך הפרק על ה[[תורת הקבוצות/סודרים|סודרים]], שם גם נגדיר את הקבוצה), לכן ניתן לפעול לגביה באינדוקציה טרנספיניטית. בהינתן <math>n\not=0</math> (הנחנו שכבר הוכחנו את הטענה לגבי 0), ניתן לרשום <math>n=(n-1)+1:=k+1</math> כאשר <math>k<n</math>. ההנחה <math>\forall m<n,\phi(m)</math> כוללת בתוכה את הטענה <math>\phi(k)</math>, לכן הגרירה <math>\phi(k)\Rightarrow\phi(k+1)\Rightarrow\phi(n)</math> גוררת את הגרירה <math>(\forall m<n,\phi(m))\Rightarrow\phi(n)</math>, לכן הטענה <math>\phi(0)\land\forall n\in\N(\phi(n)\Rightarrow\phi(n+1))</math> גוררת את <math>\phi(0)\land\forall n\in\N(\phi(n)\Rightarrow\phi(n+1))</math>, כלומר את <math>\forall n\in\N,\phi(n)</math>.
* אינדוקציה מתמטית היא בעצם סוג מסוים של אינדוקציה טרנספיניטית: הקבוצה <math>\N</math> סדורה היטב (יוכח במהלך הפרק על ה[[תורת הקבוצות/סודרים|סודרים]], שם גם נגדיר את הקבוצה), לכן ניתן לפעול לגביה באינדוקציה טרנספיניטית. בהינתן <math>n\not=0</math> (הנחנו שכבר הוכחנו את הטענה לגבי 0), ניתן לרשום <math>n=(n-1)+1:=k+1</math> כאשר <math>k<n</math>. ההנחה <math>\forall m<n,\phi(m)</math> כוללת בתוכה את הטענה <math>\phi(k)</math>, לכן הגרירה <math>\phi(k)\Rightarrow\phi(k+1)\Rightarrow\phi(n)</math> גוררת את הגרירה <math>(\forall m<n,\phi(m))\Rightarrow\phi(n)</math>, לכן הטענה <math>\phi(0)\land\forall n\in\N(\phi(n)\Rightarrow\phi(n+1))</math> גוררת את <math>\phi(0)\land\forall n\in\N(\phi(n)\Rightarrow\phi(n+1))</math>, כלומר את <math>\forall n\in\N,\phi(n)</math>.

גרסה מ־14:43, 29 ביוני 2021

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

הוכחה

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

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

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

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

  1. הוכחה כללית, כלומר:
  1. הוכחה בהתאם למקרים, כלומר:
  • מקרה א' - איבר עוקב, לכן יהי . מכיוון ש, הטענה גוררת את הטענה , לכן לובשת ההוכחה צורה של .
  • מקרה ב' - איבר גבולי, לכן 'אין ברירה', וההוכחה נשארת בתבנית של .

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

דוגמה

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

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

הגדרה: יחס בנוי היטב

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

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

הוכחה: נניח בשלילה שהקבוצה לא ריקה. אז קיים כך שלכל מתקיים . לכן לכל מתקיים , כלומר , לכן בסתירה לכך ש.

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