שיטות הוכחה בסיסיות

שיטות הוכחה

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

לכן נציג מספר שיטות להתחלת פתרון תרגילים מתמטיים.

ראשית מומלץ לקרוא את החלק הרלוונטי בקורס לחשיבה מתמטית

הוכחה בשלילה

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

שנית, בשיטות הוכחה ישירות, בהן עלינו להסיק טענה מסוימת, עלינו לזכור טענה זו ולכוון אליה כמטרה. בהוכחה בשלילה עלינו רק לזכור שמטרתנו להגיע לסתירה.

מבנה שאלה והוכחה בשלילה

מבנה שאלה:

• נתונים.
• טענה שצריך להוכיח.

מבנה ההוכחה:

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

דוגמא 1

• תהיינה A,B קבוצות המקיימות [math]\displaystyle{ A\backslash B=B\backslash A }[/math].
• הוכיחו כי [math]\displaystyle{ A=B }[/math]

הוכחה בשלילה:

• נתון: [math]\displaystyle{ A\backslash B=B\backslash A }[/math]
• צ"ל: [math]\displaystyle{ A=B }[/math]

נניח בשלילה כי [math]\displaystyle{ A\neq B }[/math].

לכן קיים [math]\displaystyle{ a\in A }[/math] כך ש [math]\displaystyle{ a\notin B }[/math] (או ההפך)

לכן לפי ההגדרה [math]\displaystyle{ a\in A\backslash B }[/math] אבל [math]\displaystyle{ a\notin B\backslash A }[/math] (או ההפך)

לכן [math]\displaystyle{ A\backslash B\neq B\backslash A }[/math]

בסתירה.

דוגמא 2

• תהיינה A,B קבוצות כך ש [math]\displaystyle{ (A\backslash B)\cup B = (A\cup B)\backslash B }[/math].
• הוכיחו כי [math]\displaystyle{ B = \phi }[/math]

הוכחה בשלילה:

נניח בשלילה כי [math]\displaystyle{ B\neq \phi }[/math].

לכן קיים איבר [math]\displaystyle{ b\in B }[/math].

לכן [math]\displaystyle{ b\in B \or b\in(A\backslash B) }[/math].

שימו לב השתמשנו כאן בכלל ההיסק הבא: מהנחת טענה א', ניתן להסיק שטענה א' או טענה ב' נכונות.

לכן [math]\displaystyle{ b\in(A\backslash B)\cup B }[/math].

מצד שני כיוון ש[math]\displaystyle{ b\in B }[/math], ניתן להסיק כי [math]\displaystyle{ b\in B \or b\not\in(A\cup B) }[/math].

אבל זה שקול לפי דה מורגן לטענה [math]\displaystyle{ \neg \left(b\not\in B \and b\in(A\cup B)\right) }[/math].

כלומר [math]\displaystyle{ \neg \left(b\in(A\cup B)\backslash B\right) }[/math].

לכן [math]\displaystyle{ b\not\in(A\cup B)\backslash B }[/math].

בסתירה לכך ש [math]\displaystyle{ (A\backslash B)\cup B = (A\cup B)\backslash B }[/math].

דוגמא 3

• יהי מספר ממשי [math]\displaystyle{ x\geq 0 }[/math] המקיים את הטענה- לכל מספר חיובי [math]\displaystyle{ \epsilon\gt 0 }[/math] מתקיים [math]\displaystyle{ x\lt \epsilon }[/math].
• הוכיחו כי x=0

הוכחה בשלילה:

נניח בשלילה כי [math]\displaystyle{ x\neq 0 }[/math].

כיוון ש [math]\displaystyle{ x\geq 0 }[/math] נובע כי [math]\displaystyle{ x\gt 0 }[/math].

לכן [math]\displaystyle{ 0\lt \frac{x}{2}\lt x }[/math].

כלומר קיים מספר חיובי [math]\displaystyle{ \epsilon=\frac{x}{2} }[/math] עבורו [math]\displaystyle{ x\not\lt \epsilon }[/math], בסתירה לנתון.

שימו לב המסקנה שהגענו אליה היא בדיוק שלילת הנתון.

הוכחת פסוק עם כמתים- לכל או קיים

על מנת להוכיח טענת לכל, אנו לוקחים איבר כללי ללא תנאים ומראים כי הטענה נכונה לגביו. הוכחות כאלו מתחילות במילה 'יהי'.

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

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

דוגמא

תהי קבוצה B. הוכיחו כי קיימת קבוצה A כך ש [math]\displaystyle{ A\cap B = B }[/math]

הוכחת הכמת קיים:

על מנת להוכיח קיום, מספיק למצוא דוגמא אחת. למשל, אם ניקח A=B נקבל את מה שרצינו.

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

דוגמא

הוכיחו שלכל מספר ממשי חיובי x יש מספר ממשי חיובי קטן ממנו. בשפה לוגית יש להוכיח כי:

[math]\displaystyle{ \forall x\gt 0\exists y\gt 0: y\lt x }[/math]

דוגמא

הוכיחו כי לכל ממשי חיובי x קיים מספר טבעי n כך ש [math]\displaystyle{ \frac{1}{n} \lt x }[/math]

הוכחת הכמת לכל:

יהי מספר טבעי חיובי כלשהו x.

צריך למצוא מספר n כך ש [math]\displaystyle{ \frac{1}{n} \lt x }[/math]

לכן, מספיק למצוא מספר n כך ש [math]\displaystyle{ \frac{1}{x} \lt n }[/math]

כיוון שאין חסם למספרים הטבעיים, ניתן לבחור מספר n כלשהו הגדול מ[math]\displaystyle{ \frac{1}{x} }[/math].

דוגמא הצרינו את הגדרת גבול הסדרה:

לכל מרחק אפיסלון, קיים מקום בסדרה שהחל ממנו והלאה כל איברי הסדרה קרובים לגבול עד כדי אפסילון.

• הוכיחו כי גבול הסדרה [math]\displaystyle{ a_n=\frac{1}{n} }[/math] הוא אפס.

• הוכיחו כי אין גבול לסדרה [math]\displaystyle{ a_n=(-1)^n }[/math]

הוכחת הכלה ושיוויון בין קבוצות

ראשית, שימו לב שהקבוצות בתרגילים כאלו יכולות להופיע באופן עקיף ולא ישיר. למשל, במשוואה [math]\displaystyle{ A\cup (B\backslash C) = P(D) }[/math] מופיעות שתי קבוצות המיוצגות על ידי ארבע הקבוצות A,B,C,D.

הוכחת הכלה

הכלה בין קבוצות היא מקרה פרטי של טענת לכל, כיוון שההגדרה של [math]\displaystyle{ A\subseteq B }[/math] הינה [math]\displaystyle{ \forall a\in A:a\in B }[/math]

מבנה ההוכחה

• יהי* איבר בקבוצה המוכלת.
• צ"ל כי האיבר שייך לקבוצה המכילה.

*שימו לב, אם למשל מדובר בקבוצה של קבוצות נאמר "תהי קבוצה שייכת לקבוצה המוכלת" ונסמן אותה באות המתאימה לקבוצה (לדוגמא תהי [math]\displaystyle{ A\in P(B) }[/math]).

אם מדובר בקבוצה של זוגות סדורים, נאמר "יהי זוג השייך לקבוצה המוכלת" ונסמן אותו בסימון המתאים לזוג (לדוגמא יהי זוג [math]\displaystyle{ (a,b)\in A\times B }[/math]).

אמנם השמות והסימונים לא משנים את המהות, אך הם מהותיים להבנה אנושית ולהצלחה בפתרון תרגילים.

דוגמא

הוכיחו כי [math]\displaystyle{ A\subseteq A \cup B }[/math].

הוכחה:

יהי [math]\displaystyle{ a\in A }[/math].

אזי [math]\displaystyle{ a\in A \or a\in B }[/math].

ולכן לפי ההגדרה [math]\displaystyle{ a\in A \cup B }[/math]

ולכן [math]\displaystyle{ A\subseteq A \cup B }[/math].

הוכחת שיוויון בין קבוצות

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

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

שיטה II: הכלה דו כיוונית. להוכיח שהקבוצה הימנית מוכלת בשמאלית וגם הקבוצה השמאלית מוכלת בימנית.

הוכחת שקילות לוגית - אם ורק אם

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

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

דוגמא תהינה קבוצות A,B,C. הוכיחו כי [math]\displaystyle{ A\backslash (B\cup C) = A }[/math] אם"ם [math]\displaystyle{ A\cap B = \phi }[/math] וגם [math]\displaystyle{ A\cap C = \phi }[/math]

הוכחת אם"ם.

[math]\displaystyle{ \Rightarrow }[/math] בכיוון ראשון נניח ונתון כי [math]\displaystyle{ A\cap B = \phi }[/math] וגם [math]\displaystyle{ A\cap C = \phi }[/math].

לכן [math]\displaystyle{ A\cap (B\cup C) = (A\cap B)\cup(A\cap C) = \phi \cup \phi = \phi }[/math].

לכן, לכל [math]\displaystyle{ a\in A }[/math] מתקיים [math]\displaystyle{ a\notin B\cup C }[/math] ולכן [math]\displaystyle{ a\in A\backslash (B\cup C) }[/math]

במשפט לעיל הוכחנו כי [math]\displaystyle{ A\subseteq A\backslash (B\cup C) }[/math]

קל להראות את ההכלה בכיוון ההפוך [math]\displaystyle{ A\backslash (B\cup C) \subseteq A }[/math] וביחד קיבלנו את מה שצריך להוכיח:

[math]\displaystyle{ A\backslash (B\cup C) = A }[/math] (לפי הכלה דו כיוונית)

[math]\displaystyle{ \Leftarrow }[/math] בכיוון השני

נתון: [math]\displaystyle{ A\backslash (B\cup C) = A }[/math]

צ"ל: [math]\displaystyle{ A\cap B = \phi }[/math] וגם [math]\displaystyle{ A\cap C = \phi }[/math]

נניח בשלילה את השלילה של מה שצריך להוכיח.

כלומר, נניח כי [math]\displaystyle{ A\cap B \neq \phi }[/math] או [math]\displaystyle{ A\cap C \neq \phi }[/math]

לכן קיים [math]\displaystyle{ x\in A\cap B }[/math] או קיים [math]\displaystyle{ x\in A\cap C }[/math].

בשני המקרים נובע כי [math]\displaystyle{ x\in A }[/math] וגם [math]\displaystyle{ x\in B\cup C }[/math]

ולכן [math]\displaystyle{ x\notin A\backslash (B\cup C) }[/math] וגם [math]\displaystyle{ x\in A }[/math]

בסתירה לכך ש [math]\displaystyle{ A\backslash (B\cup C)=A }[/math].

חלוקה למקרים

דוגמא הוכיחו כי לכל n טבעי ולכל x אי שלילי מתקיים [math]\displaystyle{ \frac{x}{1+n^4x^2}\leq \frac{1}{n^2} }[/math]

הוכחה:

יהי n טבעי ויהי [math]\displaystyle{ x\geq 0 }[/math].

אם [math]\displaystyle{ x\leq \frac{1}{n^2} }[/math] מתקיים

[math]\displaystyle{ \frac{x}{1+n^4x^2}\leq \frac{x}{1} = x \leq \frac{1}{n^2} }[/math]

אם [math]\displaystyle{ x\gt \frac{1}{n^2} }[/math] אזי

[math]\displaystyle{ \frac{x}{1+n^4x^2}\leq \frac{x}{n^4x^2} = \frac{1}{n^4x} \leq \frac{1}{n^4 \frac{1}{n^2}}=\frac{1}{n^2} }[/math]

לכן סה"כ לכל x אי שלילי ולכל n טבעי מתקיים [math]\displaystyle{ \frac{x}{1+n^4x^2}\leq \frac{1}{n^2} }[/math] כפי שרצינו.