תוכן עניינים

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

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

בשביל להוכיח שטענה מסוימת $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}_+$ יחס סדר חלקי לפי התמונה הבא (כאשר מזהים כל שבר עם זוג סדור ומבטלים את החזרות המיותרות)

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

הערה: זה בניגוד לסדר "קטן שווה" הרגיל על השברים שאינו סדר טוב כי לקבוצה $\{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}$