הבדלים בין גרסאות בדף "88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 1.5"

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(עיקרון הסדר הטוב)
(תרגילים יותר מעניינים)
שורה 226: שורה 226:
  
 
וסיימנו.
 
וסיימנו.
 +
 +
==אזהרה==
 +
אינדוקציה היא כלי חזק אך יש לשים לב כי משתמשים בו נכונה.
 +
 +
דוגמא מפורסמת להוכחת שגויה באינדוקציה היא הדוגמא הבא:
 +
 +
טענה: כל קבוצה של סוסים לא ריקה מכילה סוסים מצבע יחיד.
 +
 +
"הוכחה": נוכיח בעזרת אינדוקציה על מספר האיברים בקבוצת הסוסים.
 +
 +
עבור <math>n=1</math> אכן מתקיים כי קבוצה עם סוס אחד מכילה רק סוסים מצבע יחיד
 +
 +
כעת נניח כל קבוצה עם <math>n</math> סוסים מכילה סוסים רק מצבע יחיד ונוכיח את הטענה לקבוצת סוסים מגודל <math>n+1</math>
 +
 +
תהא <math>H={h_1,h_2,\dots h_n,h_{n+1}}</math> קבוצה עם <math>n+1</math> סוסים אזי לפי הנחת האינדוקציה
 +
<math>H_1 ={h_1,h_2,\dots h_n}</math> ו <math>H_2={h_2,\dots h_n,h_{n+1}}</math> הן קבוצות שמכילות סוסים מצבע יחיד (כי אלו קבוצות סוסים מגודל <math>n</math>)
 +
אזי לפי התרשים <math>H={h_1,h_2,\dots h_n,h_{n+1}}</math> רואים כי כל הסוסים ב <math>H</math> ג"כ בעלי צבע יחיד (כי יש חפיפה בין <math>Hֹ_1</math> ובין <math>H_2</math>)

גרסה מ־15:41, 21 ביולי 2014

חזרה למערכי התרגול

רעיון בסיסי - אינדוקציה על הטבעיים

בשביל להוכיח שטענה מסוימת P(n) נכונה עבור כל מספר טבעי (למשל (1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3) מספיק להוכיח את הבאים:

  • (בסיס האינדוקציה) הטענה מתקיימת עבור n=1 כלומר P(1) מתקיים
  • (צעד האינדוקציה)אם הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר P(n)\Rightarrow P(n+1).

למה זה מספיק? בוא נחשוב.. הוכחנו באופן ישיר כי הטענה נכונה עבור n=1 כלומר P(1) מתקיים. לכן לפי הטענה השניה, אם הטענה נכונה עבור n=1 (שזה אכן כך) אז הטענה נכונה גם עבור n=2כלומר P(2). אה! אז עכשיו זה נכון עבור n=2 אז לפי אותה טענה זה נכון גם עבור n=3! ומה עכשיו? אם זה נכון עבור n=3 זה נכון עבור n=4 . וכן על זה הדרך. אפשר להשתכנע שבסופו של דבר P(n) נכון לכל n

דוגמא: נוכיח באינדוקציה כי הטענה (1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3 נכונה לכל n\in \mathbb{N} טבעי

הוכחה:

עבור n=1 אכן מתקיים כי 1^2=1^3

כעת נראה שאם הטענה נכונה עבור n כלשהוא, כלומר אם מתקיים (1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3 אזי הטענה נכונה עבור n+1, כלומר (1+2+\cdots +n+(n+1))^2 =1^3 +2^3 + \cdots +n^3 + (n+1)^3. כלומר נוכיח ש: P(n) \to P(n+1)

נוכיח:

(1+2+\cdots +n+(n+)1)^2=(1+2+\cdots +n)^2+2\cdot(1+2+\cdots +n)(n+1)+(n+1)^2

לפי הנחת האינדוקציה אפשר להמשיך הלאה

=1^3 +2^3 + \cdots +n^3 +2\cdot (1+2+\cdots +n)(n+1)+(n+1)^2 =1^3 +2^3 + \cdots +n^3 +2 \cdot \frac{n(n+1)}{2}(n+1)+(n+1)^2 =1^3 +2^3 + \cdots +n^3 +n(n+1)^2+(n+1)^2 =1^3 +2^3 + \cdots +n^3 +(1+n)(n+1)^2=1^3 +2^3 + \cdots +n^3+(n+1)^3

וסיימנו


דוגמא נוספת:

הוכח כי לכל מספר טבעי n מתקיים כי 2+4+6+\cdots +2n=n(n+1)

פתרון:

עבור n=1 אכן מתקיים 2=1\cdot(1+1)

כעת נניח שהטענה נכונה עבור n ונוכיח את הטענה עבור n+1

2+4+\cdots 2n+2(n+1)=\sum_{k=1}^{n+1}2\cdot k=\sum_{k=1}^{n}2\cdot k + 2(n+1) =

לפי הנחת האינדוקציה ניתן להמשיך

=n(n+1)+2(n+1)=(n+1)(n+2)

שזה הטענה עבור n+1 וסיימנו.

עיקרון הסדר הטוב

הגדרה:

תהא A קבוצה עם יחס סדר חלקי R על A.

R יקרא סדר טוב אם לכל \emptyset \neq B\subseteq A קיים איבר מינימום/הכי קטן/ראשון ב B.

מינוח: נאמר כי A סדורה היטב.

דוגמא (אינטואיטיבית):

נסתכל על \mathbb{N} קבוצת הטבעיים עם יחס הסדר "קטן שווה" הסטנדרטי.

אזי אכן מתקיים כי לכל קבוצה לא ריקה של טבעיים קיים איבר מינימום בקבוצה.


דוגמא נוספת:

ניתן להגדיר אל \mathbb{Q}_+ יחס סדר חלקי לפי התמונה הבא (כאשר מזהים כל שבר עם זוג סדור ומבטלים את החזרות המיותרות)

NutualSquareEqNutural.jpeg

התבוננו והשתכנעו שזה גם סדר טוב.

הערה: זה בניגוד לסדר "קטן שווה" הרגיל על השברים שאינו סדר טוב כי לקבוצה \{x\in \mathbb{Q}_+ | \sqrt{2}<x \} אין איבר מינימום.


עיקרון הסדר הטוב

עיקרון הסדר הטוב הוא פשוט הטענה שלכל קבוצה A קיים סדר טוב


תרגיל:

תהא A קבוצה בת מנייה. הוכח כי ניתן לסדר אותה היטב.

פתרון:

לפי הנתון קיימת פונקציה חח"ע וכל f:A\to \mathbb{N} . נגדיר את היחס הבא על A כך: x\leq y \iff f(x)\leq f(y) . זהו יחס סדר (השתכנעו!). בנוסף, A סדורה היטב על ידו. הוכחה: תהא B\subseteq A תת קבוצה לא ריקה. אזי f(B)\subseteq\mathbb{N} תת קבוצה לא ריקה ולכן קיים בה איבר מינימום נסמנו n. בדקו כי f^{-1}(n)\in B איבר מינימום.

הכללות

הכללה פשוטה 1

הכללה ישירה מתבצעת כך (החלפה רק של הטענה הראשונה): אם נוכיח עבור טענה P(n) ש:

  • הטענה מתקיימת עבור n=k מסוים כלומר P(k) מתקיים
  • אם הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר P(n)\Rightarrow P(n+1).

אז באופן דומה הטענה נכונה P(n) נכונה עבור n\geq k

כלומר - במקום להוכיח עבור n=1 ואז הטענה מתקיים החל מ-1 ניתן להוכיח עבור n=k ואז הטענה מתקיים החל מ-k


דוגמא:

הוכח כי לכל x>0 מתקיים (1+x)^n > 1+nx לכל n\geq 2

פתרון:

עבור n=2 נקבל (1+x)^2 = 1+2x+x^2>1+2x כי x>0

כעת נניח כי הטענה נכונה עבור n כלשהוא, כלומר מתקיים (1+x)^n > 1+nx

נוכיח עבור n+1 מהנחת האינדוקציה נקבל כי  (1+x)^{n+1}=(1+x)^n\cdot (1+x)>(1+nx) +1+x > 1+x+nx =1+ (n+1)x

וסיימנו

הכללה פשוטה 2

אם נוכיח עבור טענה P(n) ש:

  • הטענה מתקיימת עבור n=1 מסוים כלומר P(1) מתקיים
  • אם הטענה נכונה עבור כל המספרים עד מספר טבעי מסוים n (כלומר מתקיים P(m) עבור m\leq n) אזי היא נכונה גם עבור המספר הבא אחריו (כלומר P(n+1) מתקיים).

אז באופן דומה הטענה נכונה P(n) נכונה עבור n\geq k

כלומר - אפשר להחליף את ההנחה שמתקיים עבור n ולהוכיח עבור n+1 בהנחה שמתקיים עבור כל מי שקטן שווה n ולהוכיח עבור n+1


דוגמא: כל מספר טבעי 1<n ניתן להציגו כמכפלה של מספרים ראשוניים

הוכחה:

עבור n=2 זה נכון כי 2 ראשוני ואז הוא הפירוק של עצמו.

כעת נניח שהטענה נכונה לכל 1<k\leq n ונוכיח עבור n+1

אם n+1 ראשוני - סיימנו כי אז הוא הפירוק של עצמו.

אחרת n+1 מתפרק למכפלה n+1=ab כאשר 1<a,b<n+1 לפי הנחת האינדוקציה a,b מתפרקים למכפלה של מספרים ראשוניים a=\Pi_{k=1}^l p_k,b=\Pi_{i=1}^r q_i כאשר p_k,q)i ראשוניים

ואז n=ab=\Pi_{k=1}^l p_k\cdot \Pi_{i=1}^r q_i

וסיימנו

הכללה מעמיקה

תהא A קבוצה סדורה היטב (נסמן את היחס שלה ב\leq) בת מניה אז ניתן להוכיח שטענה P מתקיימת לכל a\in A ע"י הוכחת הטענה הבא:

  • אם הטענה P נכונה עבור m<n אז הטענה נכונה עבור n.


למה זה עובד?

נניח בשלילה כי הטענה P לא מתקיימת לכל a\in A אזי נגדיר D:=\{a\in A | P(a)=FALSE \} - קבוצת כל האיברים ב A שעבורם הטענה אינה נכונה. מהנחת השלילה D\neq \emptyset.

כיוון ש A סדורה היטב אזי קיים ב D מינימום, נסמנו d. לפי הגדרת מינימום והגדרת D נובע כי לכל m<d הטענה נכונה (אם היה m<d שהטענה לא נכונה לגביו אזי הוא היה בקבוצה D ואז זה היה סתירה לכך ש d מינימום של קבוצה זאת).

אבל אם זה כך אז לפי הטענה שמוכיחים זה גורר כי d כן מתקיים. סתירה. ולכן הטענה נכונה לכל a\in A


הערה: אפשר לעשות אינדוקציה הנקראת אינדוקציה טרנספניטית על קבוצות כלשהן (לאו דווקא בנות מניה)

הערה: קיום סדר טוב על הטבעיים שקול לקיומה של אינדוקציה על הטבעיים.

תרגילים יותר מעניינים

תרגיל:

יהיו A_1,A_2,\dots A_n קבוצות אזי A_1 \triangle A_2 \triangle \dots  \triangle A_n =\{x| x \; \; \text{in odd number of sets} \}

הוכחה:

עבור n=2 זה נכון כי הפרש סימטרי של 2 קבוצות זה כל ה x - ים שנמצאים או בראשונה בלבד או בשניה בלבד.

נניח כי הטענה נכונה עבור n קבוצות. נוכיח עבור n+1 קבוצות:

A_1 \triangle A_2 \triangle \dots  \triangle A_n \triangle A_{n+1} = B\cup C כאשר B=\{x \; | \; x\in (A_1 \triangle A_2 \triangle \dots  \triangle A_n )\backslash A_{n+1} \} = \{x \; | \; x\in (A_1 \triangle A_2 \triangle \dots  \triangle A_n ) \land x\not\in A_{n+1} \}
, \; C= \{ x \; | \; x \in A_{n+1} \backslash (A_1 \triangle A_2 \triangle \dots  \triangle A_n ) \} = \{x \; | \; x \in A_{n+1} \land x\not\in (A_1 \triangle A_2 \triangle \dots  \triangle A_n )\}

לפי הנחת האינדוקציה מתקיים A_1 \triangle A_2 \triangle \dots  \triangle A_n =\{x| x \; \; \text{in odd number of sets from}\; A_1,A_2\dots A_n \} ולכן ניתן להמשיך כך

B\cup C = \{x \; | \; x\in (A_1 \triangle A_2 \triangle \dots  \triangle A_n ) \; \land \; x\not\in A_{n+1}\} \cup \{x \; | \; x \in A_{n+1} \; \land \; x\not\in (A_1 \triangle A_2 \triangle \dots  \triangle A_n )\} =

\{x \; | \; x\in  \; \text{in odd number of sets from}\; A_1,A_2\dots A_n \; \land \; x\not\in A_{n+1} \} \cup \{x \; | \; x \in A_{n+1} \; \land \; x\not\in \text{in odd number of sets from}\; A_1,A_2\dots A_n \}  =

\{x \; | x\not\in A_{n+1} \; \land \; x\in  \; \text{in odd number of sets from}\; A_1,A_2\dots A_n \} \cup \{x \; | \; x \in A_{n+1} \; \land \; x \in \text{in even number of sets from}\; A_1,A_2\dots A_n \}=

\{x \; | \; x\in  \; \text{in odd number of sets from}\; A_1,A_2\dots A_n, A_{n+1} \}


לכן, הטענה נכונה גם עבור n+1 וסיימנו


תרגיל:

יהיו A_1,A_2\dots A_{m+1} \in \mathbb{F}^{n\times n} מטריצות ריבועיות אזי האיבר הכללי של המכפלה של כולם ניתן ע"י הנוסחא (A_1A_2\cdots A_{m+1})_{i,j}=\underset{1\leq i_1,i_2,\dots i_m \leq n}{\sum}(A_1)_{i,i_1}(A_2)_{i_1,i_2}\dots (A_{m+1})_{i_m,j}

הוכחה (באינדוקציה על מספר המטריצות):

עבור m=1 זה ההגדרה של כפל בין 2 מטריצות

כעת, נניח שהטענה נכונה עבור m כל שהוא. נוכיח נכונות עבור m+1

(A_1A_2\cdots A_{m+1}A_{m+2})_{i,j}=\sum_{i_{m+1}=1}^n (A_1A_2\cdots A_{m+1})_{i,i_{m+1}}(A_{m+2})_{i_{m+1},j}

לפי הנחת האינדוקציה נמשיך:

=\sum_{i_{m+1}=1}^n \underset{1\leq i_1,i_2,\dots i_m \leq n}{\sum}(A_1)_{i,i_1}(A_2)_{i_1,i_2}\dots (A_{m+1})_{i_m,i_{m+1}}(A_{m+2})_{i_{m+1},j} =

 = \underset{1\leq i_1,i_2,\dots i_m, i_{m+1} \leq n}{\sum}(A_1)_{i,i_1}(A_2)_{i_1,i_2}\dots (A_{m+1})_{i_m,i_{m+1}}(A_{m+2})_{i_{m+1},j}

וסיימנו.

אזהרה

אינדוקציה היא כלי חזק אך יש לשים לב כי משתמשים בו נכונה.

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

טענה: כל קבוצה של סוסים לא ריקה מכילה סוסים מצבע יחיד.

"הוכחה": נוכיח בעזרת אינדוקציה על מספר האיברים בקבוצת הסוסים.

עבור n=1 אכן מתקיים כי קבוצה עם סוס אחד מכילה רק סוסים מצבע יחיד

כעת נניח כל קבוצה עם n סוסים מכילה סוסים רק מצבע יחיד ונוכיח את הטענה לקבוצת סוסים מגודל n+1

תהא H={h_1,h_2,\dots h_n,h_{n+1}} קבוצה עם n+1 סוסים אזי לפי הנחת האינדוקציה H_1 ={h_1,h_2,\dots h_n} ו H_2={h_2,\dots h_n,h_{n+1}} הן קבוצות שמכילות סוסים מצבע יחיד (כי אלו קבוצות סוסים מגודל n) אזי לפי התרשים H={h_1,h_2,\dots h_n,h_{n+1}} רואים כי כל הסוסים ב H ג"כ בעלי צבע יחיד (כי יש חפיפה בין עיבוד הנוסחה נכשל (שגיאת לקסינג): Hֹ_1

ובין H_2)