בקצרה: שיטות ההוכחה הבסיסיות במתמטיקה כוללות: הוכחה בשלילה, הוכחת פסוקים עם כמתים ('לכל'/'קיים'), הוכחת הכלה ושוויון בין קבוצות, הוכחת שקילות לוגית ('אם ורק אם'), וחלוקה למקרים.

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

▶ סרטון: מבוא לחשיבה מתמטית: קשרים לוגיים, כמתים ושלילה

בסרטון: ▶ גרירה ו"אם ורק אם" 1:21 · ▶ הכמתים "לכל" ו"קיים" 4:57 · ▶ שלילת פסוקים וכמתים 6:16
הרצאה מלאה על שיטות הוכחה (קורס ההכנה במתמטיקה): ▶ מ־1:19:28

איך בוחרים שיטה?

השאלה הראשונה מול תרגיל הוכחה היא מה צורת הטענה. לפי הצורה בוחרים איך להתחיל:

הטענה נראית כך	מתחילים כך	בדף
"לכל [math]\displaystyle{ x }[/math] מתקיים..."	יהי [math]\displaystyle{ x }[/math] כלשהו, ומוכיחים את הטענה עבורו	כמתים
"קיים [math]\displaystyle{ x }[/math] כך ש..."	מציגים [math]\displaystyle{ x }[/math] מתאים ובודקים שהוא מקיים את הדרוש	כמתים
"הוכח או הפרך" לטענת "לכל" שאינה נכונה	דוגמה נגדית אחת	תרגילים
[math]\displaystyle{ A\subseteq B }[/math]	יהי [math]\displaystyle{ a\in A }[/math], וצ"ל [math]\displaystyle{ a\in B }[/math]	הכלה
[math]\displaystyle{ A=B }[/math] (קבוצות)	הכלה דו־כיוונית: [math]\displaystyle{ A\subseteq B }[/math] וגם [math]\displaystyle{ B\subseteq A }[/math]	שוויון קבוצות
"[math]\displaystyle{ P }[/math] אם ורק אם [math]\displaystyle{ Q }[/math]"	שני כיוונים: [math]\displaystyle{ P\Rightarrow Q }[/math], ואחר כך [math]\displaystyle{ Q\Rightarrow P }[/math]	אם ורק אם
"אין...", "לא קיים...", "[math]\displaystyle{ x=0 }[/math]" כשנתון רק אי־שוויון	נב"ש (נניח בשלילה) ומגיעים לסתירה	הוכחה בשלילה
הטענה מתנהגת אחרת בתחומים שונים (סימן, זוגיות, [math]\displaystyle{ x }[/math] קטן או גדול)	חלוקה למקרים שמכסים את כל האפשרויות	מקרים
"לכל [math]\displaystyle{ n }[/math] טבעי..." (נוסחה, אי־שוויון)	אינדוקציה	אינדוקציה מתמטית

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

שיטות הוכחה

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

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

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

הוכחה בשלילה

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

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

החלק הקשה בהוכחה בשלילה הוא לנסח נכון את השלילה של הטענה: ▶ שלילת פסוקים וכמתים 6:16 · ▶ שלילת טענה עם כמתים, בהרצאה 2:24:57

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

מבנה שאלה:

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

מבנה ההוכחה:

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

דוגמא 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].

במילים פשוטות: האיבר [math]\displaystyle{ b }[/math] שייך לאגף שמאל, כי כל איברי [math]\displaystyle{ B }[/math] נמצאים באיחוד עם [math]\displaystyle{ B }[/math]. הוא לא שייך לאגף ימין, כי מאגף ימין הוצאו כל איברי [math]\displaystyle{ B }[/math]. לכן שני האגפים אינם שווים.

דוגמא 3

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

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

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

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

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

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

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

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

▶ סרטון: הוכחת טענות לכל וטענות קיים

בהרצאה המלאה: ▶ "לכל" והמילה "יהי" 1:19:43 · ▶ "קיים" 1:22:26 · ▶ הפרכה ודוגמה נגדית 1:29:34 · ▶ התרגיל "לכל x חיובי קיים y חיובי קטן ממנו" 1:34:35

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

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

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

דוגמא

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

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

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

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

דוגמא

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

[math]\displaystyle{ \forall x>0\exists y>0: y<x }[/math]

הטענה מתחילה ב"לכל", ולכן מתחילים ביהי: יהי [math]\displaystyle{ x>0 }[/math].
עכשיו צריך להוכיח טענת קיים, ולכן מציגים [math]\displaystyle{ y }[/math] מתאים: נבחר [math]\displaystyle{ y=\frac x2 }[/math].
בדיקה: [math]\displaystyle{ y=\frac x2>0 }[/math], וגם [math]\displaystyle{ y=\frac x2<x }[/math], כי [math]\displaystyle{ x>0 }[/math]. לכן [math]\displaystyle{ y }[/math] מקיים את הדרוש.
שימו לב למי מותר לבחור: את [math]\displaystyle{ x }[/math] לא בוחרים, כי הוא "כלשהו". את [math]\displaystyle{ y }[/math] בוחרים, ומותר לו להיות תלוי ב־[math]\displaystyle{ x }[/math].

דוגמא

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

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

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

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

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

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

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

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

[math]\displaystyle{ \lim_{n\to\infty}a_n=L }[/math]

אם ורק אם

[math]\displaystyle{ \forall\varepsilon>0\ \exists N\in\mathbb N\ \forall n>N: }[/math]

[math]\displaystyle{ |a_n-L|<\varepsilon }[/math]

"מרחק אפסילון" הוא [math]\displaystyle{ \varepsilon>0 }[/math], "מקום בסדרה" הוא [math]\displaystyle{ N }[/math], ו"קרובים לגבול" פירושו [math]\displaystyle{ |a_n-L|<\varepsilon }[/math]. לפירוט ראו הגדרת הגבול של סדרה.

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

ההגדרה מתחילה ב"לכל [math]\displaystyle{ \varepsilon }[/math]", ולכן: יהי [math]\displaystyle{ \varepsilon>0 }[/math].
צריך להציג [math]\displaystyle{ N }[/math] (קיים). לפי הדוגמה הקודמת, עם [math]\displaystyle{ x=\varepsilon }[/math], קיים [math]\displaystyle{ N }[/math] טבעי כך ש [math]\displaystyle{ \frac1N<\varepsilon }[/math].
שוב "לכל": יהי [math]\displaystyle{ n>N }[/math]. אזי

[math]\displaystyle{ \left|\frac1n-0\right|=\frac1n }[/math]

[math]\displaystyle{ \frac1n<\frac1N<\varepsilon }[/math]

הוכחנו את ההגדרה, ולכן [math]\displaystyle{ \frac1n\to0 }[/math].

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

"אין גבול" היא טענת "לא קיים", ולכן נוכיח אותה בשלילה.
נב"ש כי [math]\displaystyle{ a_n\to L }[/math] עבור מספר ממשי [math]\displaystyle{ L }[/math] כלשהו.
לפי ההגדרה עם [math]\displaystyle{ \varepsilon=1 }[/math], קיים [math]\displaystyle{ N }[/math] כך שלכל [math]\displaystyle{ n>N }[/math] מתקיים [math]\displaystyle{ |(-1)^n-L|<1 }[/math].
נבחר [math]\displaystyle{ n>N }[/math] זוגי, ונקבל [math]\displaystyle{ |1-L|<1 }[/math]. נבחר [math]\displaystyle{ n>N }[/math] אי־זוגי, ונקבל [math]\displaystyle{ |-1-L|<1 }[/math], כלומר [math]\displaystyle{ |L+1|<1 }[/math].
לפי אי־שוויון המשולש:

[math]\displaystyle{ 2=|(1-L)+(L+1)| }[/math]

[math]\displaystyle{ \le|1-L|+|L+1| }[/math]

[math]\displaystyle{ <1+1=2 }[/math]

קיבלנו [math]\displaystyle{ 2<2 }[/math], בסתירה. לכן לסדרה אין גבול.

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

▶ סרטון: הוכחת הכלה ושיוויון בין קבוצות

עוד: ▶ בסרטון "קבוצות ופעולות על קבוצות" 25:53 · ▶ "הוכח או הפרך" לשוויון של קבוצות, בהרצאה 2:02:15

ראשית, שימו לב שהקבוצות בתרגילים כאלו יכולות להופיע באופן עקיף ולא ישיר. למשל, במשוואה [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\cap(B\cup C)=(A\cap B)\cup(A\cap C) }[/math]

נוכיח בשיטה II, הכלה דו־כיוונית.

הכלה ראשונה, [math]\displaystyle{ A\cap(B\cup C)\subseteq(A\cap B)\cup(A\cap C) }[/math]: יהי [math]\displaystyle{ x\in A\cap(B\cup C) }[/math]. אזי [math]\displaystyle{ x\in A }[/math] וגם [math]\displaystyle{ x\in B\cup C }[/math]. נחלק למקרים:
- אם [math]\displaystyle{ x\in B }[/math], אזי [math]\displaystyle{ x\in A\cap B }[/math].
- אם [math]\displaystyle{ x\in C }[/math], אזי [math]\displaystyle{ x\in A\cap C }[/math].

בשני המקרים [math]\displaystyle{ x\in(A\cap B)\cup(A\cap C) }[/math].

הכלה שנייה, [math]\displaystyle{ (A\cap B)\cup(A\cap C)\subseteq A\cap(B\cup C) }[/math]: יהי [math]\displaystyle{ x\in(A\cap B)\cup(A\cap C) }[/math]. שוב נחלק למקרים:
- אם [math]\displaystyle{ x\in A\cap B }[/math], אזי [math]\displaystyle{ x\in A }[/math], וגם [math]\displaystyle{ x\in B }[/math] ולכן [math]\displaystyle{ x\in B\cup C }[/math].
- אם [math]\displaystyle{ x\in A\cap C }[/math], אזי [math]\displaystyle{ x\in A }[/math], וגם [math]\displaystyle{ x\in C }[/math] ולכן [math]\displaystyle{ x\in B\cup C }[/math].

בשני המקרים [math]\displaystyle{ x\in A\cap(B\cup C) }[/math].

הוכחנו הכלה בשני הכיוונים, ולכן הקבוצות שוות. בשוויון הזה נשתמש בדוגמה של "אם ורק אם" שבהמשך.

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

סרטונים: ▶ גרירה ו"אם ורק אם" 1:21 · ▶ גרירה ושקילות להיפוך השלילה 25:27 · ▶ אם ורק אם: שני כיוונים, בהרצאה 1:51:30

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

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

דוגמא תהינה קבוצות 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{ \Leftarrow }[/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{ \Rightarrow }[/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].

חלוקה למקרים

סרטונים: ▶ דוגמה להכלה באמצעות חלוקה למקרים 0:40 · ▶ חלוקה למקרים כשנתון איחוד, בהרצאה 2:18:27

דוגמא הוכיחו כי לכל 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>\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] כפי שרצינו.

תרגילים נוספים

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

תרגיל 1 (הוכח או הפרך). הוכיחו או הפריכו: לכל מספר ממשי [math]\displaystyle{ x }[/math] מתקיים [math]\displaystyle{ x^2\ge x }[/math].

הטענה אינה נכונה. היא טענת "לכל", ולכן כדי להפריך אותה מספיקה דוגמה נגדית אחת.
עבור [math]\displaystyle{ x=\frac12 }[/math] מתקיים [math]\displaystyle{ x^2=\frac14<\frac12=x }[/math].
איך מוצאים דוגמה נגדית: בודקים כמה מספרים, ובמיוחד מספרים "חשודים" כמו [math]\displaystyle{ 0 }[/math], שברים בין [math]\displaystyle{ 0 }[/math] ל־[math]\displaystyle{ 1 }[/math] ומספרים שליליים. במקרה הזה כל [math]\displaystyle{ 0<x<1 }[/math] הוא דוגמה נגדית.

תרגיל 2 (סדר הכמתים). האם הטענה [math]\displaystyle{ \exists y>0\ \forall x>0:\ y<x }[/math] נכונה? השוו לטענה [math]\displaystyle{ \forall x>0\ \exists y>0:\ y<x }[/math] שהוכחנו למעלה.

הטענה אינה נכונה. היא אומרת שיש מספר חיובי אחד שקטן מכל המספרים החיוביים.
נוכיח את השלילה שלה: [math]\displaystyle{ \forall y>0\ \exists x>0:\ x\le y }[/math]. יהי [math]\displaystyle{ y>0 }[/math]. נבחר [math]\displaystyle{ x=y }[/math]. אזי [math]\displaystyle{ x>0 }[/math] וגם [math]\displaystyle{ x\le y }[/math].
ההבדל בין שתי הטענות הוא סדר הכמתים: בטענה [math]\displaystyle{ \forall x\ \exists y }[/math] מותר לבחור [math]\displaystyle{ y }[/math] אחר לכל [math]\displaystyle{ x }[/math], ולכן היא נכונה ([math]\displaystyle{ y=\frac x2 }[/math]). בטענה [math]\displaystyle{ \exists y\ \forall x }[/math] אותו [math]\displaystyle{ y }[/math] צריך להתאים לכל ה־[math]\displaystyle{ x }[/math], ולכן היא שגויה.

תרגיל 3 (הוכחה בשלילה). הוכיחו שאין מספר טבעי גדול ביותר.

"אין" היא טענת "לא קיים", ולכן נוכיח אותה בשלילה.
נב"ש שקיים מספר טבעי [math]\displaystyle{ m }[/math] גדול ביותר, כלומר [math]\displaystyle{ n\le m }[/math] לכל [math]\displaystyle{ n }[/math] טבעי.
אבל [math]\displaystyle{ m+1 }[/math] הוא מספר טבעי, ו־[math]\displaystyle{ m+1>m }[/math], בסתירה.

תרגיל 4 (הוכחה בשלילה). הוכיחו כי [math]\displaystyle{ \sqrt2 }[/math] אינו מספר רציונלי.

נב"ש כי [math]\displaystyle{ \sqrt2=\frac pq }[/math], כאשר [math]\displaystyle{ p,q }[/math] טבעיים ([math]\displaystyle{ \sqrt2>0 }[/math]) והשבר מצומצם, כלומר ל־[math]\displaystyle{ p }[/math] ול־[math]\displaystyle{ q }[/math] אין מחלק משותף גדול מ־[math]\displaystyle{ 1 }[/math].
נעלה בריבוע ונכפול ב־[math]\displaystyle{ q^2 }[/math]: [math]\displaystyle{ p^2=2q^2 }[/math]. לכן [math]\displaystyle{ p^2 }[/math] זוגי.
מכאן [math]\displaystyle{ p }[/math] זוגי: אילו [math]\displaystyle{ p }[/math] היה אי־זוגי, [math]\displaystyle{ p=2k+1 }[/math], אז

[math]\displaystyle{ p^2=4k^2+4k+1 }[/math]

והיה אי־זוגי.

נכתוב [math]\displaystyle{ p=2k }[/math]. אזי [math]\displaystyle{ 4k^2=2q^2 }[/math], כלומר [math]\displaystyle{ q^2=2k^2 }[/math], ולכן [math]\displaystyle{ q^2 }[/math] זוגי, ובאותו נימוק [math]\displaystyle{ q }[/math] זוגי.
קיבלנו ש־[math]\displaystyle{ p }[/math] ו־[math]\displaystyle{ q }[/math] זוגיים שניהם, כלומר [math]\displaystyle{ 2 }[/math] מחלק משותף שלהם, בסתירה לכך שהשבר מצומצם.

תרגיל 5 (חלוקה למקרים). הוכיחו כי לכל מספר שלם [math]\displaystyle{ n }[/math], המספר [math]\displaystyle{ n^2+n }[/math] זוגי.

יהי [math]\displaystyle{ n }[/math] שלם. כל מספר שלם הוא זוגי או אי־זוגי, ולכן שני המקרים הבאים מכסים את כל האפשרויות.
[math]\displaystyle{ n }[/math] זוגי, [math]\displaystyle{ n=2k }[/math]:

[math]\displaystyle{ n^2+n=4k^2+2k }[/math]

[math]\displaystyle{ =2(2k^2+k) }[/math]

[math]\displaystyle{ n }[/math] אי־זוגי, [math]\displaystyle{ n=2k+1 }[/math]:

[math]\displaystyle{ n^2+n=(2k+1)(2k+2) }[/math]

[math]\displaystyle{ =2(2k+1)(k+1) }[/math]

בשני המקרים [math]\displaystyle{ n^2+n }[/math] הוא כפולה של [math]\displaystyle{ 2 }[/math], כלומר זוגי.

תרגיל 6 (אם ורק אם). תהיינה [math]\displaystyle{ A,B }[/math] קבוצות. הוכיחו כי [math]\displaystyle{ A\subseteq B }[/math] אם ורק אם [math]\displaystyle{ A\cap B=A }[/math].

[math]\displaystyle{ \Rightarrow }[/math] נניח [math]\displaystyle{ A\subseteq B }[/math], וצ"ל [math]\displaystyle{ A\cap B=A }[/math]. נוכיח בהכלה דו־כיוונית:
- [math]\displaystyle{ A\cap B\subseteq A }[/math]: יהי [math]\displaystyle{ x\in A\cap B }[/math]. אזי בפרט [math]\displaystyle{ x\in A }[/math].
- [math]\displaystyle{ A\subseteq A\cap B }[/math]: יהי [math]\displaystyle{ x\in A }[/math]. כיוון ש־[math]\displaystyle{ A\subseteq B }[/math], גם [math]\displaystyle{ x\in B }[/math]. לכן [math]\displaystyle{ x\in A\cap B }[/math].
[math]\displaystyle{ \Leftarrow }[/math] נניח [math]\displaystyle{ A\cap B=A }[/math], וצ"ל [math]\displaystyle{ A\subseteq B }[/math]. יהי [math]\displaystyle{ x\in A }[/math]. כיוון ש־[math]\displaystyle{ A=A\cap B }[/math], מתקיים [math]\displaystyle{ x\in A\cap B }[/math], ובפרט [math]\displaystyle{ x\in B }[/math].
הוכחנו את שני הכיוונים, ולכן הטענות שקולות.

טעויות נפוצות

להוכיח טענת "לכל" בעזרת דוגמה. בדיקה של [math]\displaystyle{ x=1 }[/math] או של כמה מספרים אינה הוכחה. דוגמה מספיקה רק כדי להוכיח טענת "קיים", או כדי להפריך טענת "לכל".
לבחור את מה שאסור לבחור. בהוכחת "לכל [math]\displaystyle{ x }[/math] קיים [math]\displaystyle{ y }[/math]" לא בוחרים את [math]\displaystyle{ x }[/math]; כותבים "יהי [math]\displaystyle{ x }[/math]". בוחרים רק את [math]\displaystyle{ y }[/math], ומותר לו להיות תלוי ב־[math]\displaystyle{ x }[/math].
לשלול לא נכון בהוכחה בשלילה. השלילה של "לכל [math]\displaystyle{ x }[/math] מתקיים..." היא "קיים [math]\displaystyle{ x }[/math] שלא מתקיים...". השלילה של [math]\displaystyle{ A=B }[/math] היא "קיים איבר שנמצא באחת הקבוצות ולא בשנייה" (כמו בדוגמא 1). השלילה של [math]\displaystyle{ < }[/math] היא [math]\displaystyle{ \ge }[/math].
להוכיח רק חצי. בשוויון קבוצות צריך את שתי ההכלות, ובטענת "אם ורק אם" צריך את שני הכיוונים.
לשכוח מקרה. בחלוקה למקרים, המקרים צריכים לכסות את כל האפשרויות, כמו [math]\displaystyle{ x\le\frac1{n^2} }[/math] ו־[math]\displaystyle{ x>\frac1{n^2} }[/math] בדוגמה למעלה.
לנסות להוכיח בלי לבדוק דוגמאות. בשאלת "הוכח או הפרך" כדאי לבדוק קודם כמה מקרים קטנים, כמו הקבוצה הריקה או מספרים קטנים. אם ההוכחה נתקעת, ייתכן שיש הפרכה.

לתרגול ולקריאה נוספת

88-101 חשיבה מתמטית - הגדרות והוכחות: הגדרות והוכחות מהקורס בחשיבה מתמטית.
אינדקס השאלות במתמטיקה בדידה: שאלות ממבחנים לפי נושא, ובהן "שיטות הוכחה בסיסיות", "לוגיקה" ו"קבוצות ופעולות על קבוצות".
אינדוקציה מתמטית ואי-שוויון ברנולי: שיטת ההוכחה לטענות על כל המספרים הטבעיים.
הגדרת הגבול של סדרה: הוכחות עם כמתים ("לכל אפסילון קיים N") ודוגמאות פתורות.