משתמש:בר/Minimal counterexample
במתמטיקה, דוגמה נגדית מינימלית היא הדוגמה הקטנה ביותר המפריכה טענה. הוכחה באמצעות דוגמה נגדית מינימלית היא שיטת הוכחה המשלבת שימוש בדוגמה נגדית מינימלית עם רעיונות הוכחה באמצעות אינדוקציה והוכחה בדרך השלילה[1].
שיטת ההוכחה[עריכת קוד מקור | עריכה]
כדי להוכיח טענה P, נניח בשלילה שהטענה P שקרית. ולכן חייבת להיות לפחות דוגמה נגדית אחת. אז לפי עקרון הסדר הטוב, קיימת דוגמה נגדית מינימלית.
לגבי הטיעון, C הוא בדרך כלל משהו די היפותטי (מכיוון שהאמיתות של P שוללת את האפשרות של C), אבל אפשר לטעון שאם C היה קיים, מאפייניו יובילו לסתירה. ובכך נראה באופן דומה להוכחה אינדוקטיבית, שהטענה P אכן נכונה[2].
אם צורת הסתירה היא שאנו יכולים להסיק דוגמה נגדית נוספת D, שהיא קטנה מ- C במובן של השערת העבודה של מינימליות, אז טכניקה זו נקראת באופן מסורתי הוכחה בנסיגה אינסופית. במקרה זה, עשויות להיות דרכים מרובות ומורכבות יותר לבנות את טיעון ההוכחה.
ההנחה שאם יש דוגמה נגדית, יש דוגמה נגדית מינימלית, מבוססת על סידור טוב מסוג כלשהו. הסדר הרגיל על המספרים הטבעיים אפשרי בבירור, על ידי הניסוח הרגיל ביותר של אינדוקציה מתמטית ; אך היקף השיטה יכול לכלול אינדוקציה מסודרת מכל סוג שהוא.
אלגוריתם[עריכת קוד מקור | עריכה]
- נרצה להוכיח טענה P.
- נגדיר קבוצה C כקבוצת הדוגמאות הנגדיות לטענה P.
- נניח בשלילה ש-C קבוצה לא ריקה.
- מעקרון הסדר הטוב נובע שקיים לקבוצה C איבר מינימלי נסמנו m.
- נבחר איבר n שקטן יותר מהאיבר המינימלי, ולכן לא שייך ל-C, ולכן מקיים את הטענה P.
- באמצעות n נראה שגם m מקיים את הטענה ולכן הוא לא שייך ל-C.
- אז m לא המינימום של C.
- הגענו לסתירה ולכן C קבוצה ריקה.
- לא קיים x עבורו P(x) ולכן P אמת.
[[קטגוריה:מושגים במתמטיקה]]
[[קטגוריה:הוכחה]]
הערות שוליים[עריכת קוד מקור | עריכה]
- ^ Klipper, Michael (Fall 2012). "Proof by Minimum Counterexample" (PDF). alpha.math.uga.edu. נבדק ב-2019-11-28.(הקישור אינו פעיל, September 2020)
- ^ Lewis, Tom (Fall 2010). "§20 Smallest Counterexample" (PDF). math.furman.edu. נבדק ב-2019-11-28.