מכינה למחלקת מתמטיקה/מערכי שיעור/14

שיטות הוכחה

הוכחה בשלילה

הוכחה בשלילה מבוססת על הטאוטולוגיה [math]\displaystyle{ (\sim p \rightarrow F)\rightarrow p }[/math]. בהוכחה בשלילה אנו מניחים את השלילה של מה שצריך להוכיח ומגיעים לסתירה.

שימו לב שאנו לא שוללים את הנתון אלא את הצ"ל.

דוגמא:

תרגיל תהיינה 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]

בסתירה.

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

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

הכלה דו כיוונית

בשיטה זו אנו מוכיחים שיוויון בין קבוצות. על מנת להוכיח כי [math]\displaystyle{ A=B }[/math] מספיק להוכיח כי [math]\displaystyle{ A\subseteq B }[/math] וגם [math]\displaystyle{ B\subseteq A }[/math]

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

הוכחה באמצעות הכלה דו כיוונית:

מהנתון ניתן להסיק כי [math]\displaystyle{ A\cup B \subseteq A \cap B }[/math]

לכן בפרט [math]\displaystyle{ A\cup B \subseteq A }[/math] וגם [math]\displaystyle{ A\cup B \subseteq B }[/math]

לכן [math]\displaystyle{ A\subseteq B }[/math] וגם [math]\displaystyle{ B\subseteq A }[/math]

וביחד לפי הכלה דו-כיוונית [math]\displaystyle{ A=B }[/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].

דוגמא

תהי קבוצה 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]

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

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

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

דוגמא תהינה קבוצות 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].