מכינה למחלקת מתמטיקה/מערכי שיעור/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{ 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 נקבל את מה שרצינו.

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