פרדוקס הסוס
מתוך ויקיפדיה, האנציקלופדיה החופשית
פרדוקס הסוס הוא טיעון מפורסם ה"מוכיח", תוך שימוש שגוי בעקרון האינדוקציה המתמטית, את התוצאה האבסורדית כי לכל הסוסים בעולם אותו צבע. הטיעון ממחיש את רמת ההקפדה הדרושה בעת הוכחות מתמטיות.
[עריכה] "הוכחה"
ננסה להוכיח את המשפט הבא: "בכל קבוצה סופית של סוסים, כל הסוסים הם בעלי אותו צבע". כמו כל הוכחה באינדוקציה גם הוכחה זו כוללת שני מרכיבים:
- בדיקה עבור מקרה אחד: אם בקבוצה יש רק סוס אחד, הטענה נכונה משום שלאותו סוס יש הצבע שלו.
- כעת נניח שבכל קבוצה של k סוסים כל הסוסים הם באותו צבע, ונסיק מכך שאותה טענה נכונה גם עבור קבוצות של k+1 סוסים. נתונה קבוצה שבה k+1 סוסים. נבחר אחד מהם (ששמו, נאמר, בוקפאלוס). קבוצת הסוסים הנותרים היא בת k סוסים, ולפי הנחת האינדוקציה לסוסים אלה יש צבע אחיד. נחזיר את בוקפאלוס לקבוצה, ונוציא סוס אחר (ששמו, נאמר, נגרו קבלו). שוב נשארו k סוסים, ולפי הנחת האינדוקציה לכל הסוסים אותו צבע. אם נחזיר את נגרו קבלו, תתקבל הקבוצה המקורית, כשלכל הסוסים בה אותו צבע.
בכך הוכחנו, לכאורה, את הטענה - ומכיוון שבעולם מספר סופי של סוסים, כולם מוכרחים להיות בעלי אותו צבע.
[עריכה] השגיאה בהוכחה
התאור לעיל שגוי בנקודה חשובה אחת: כדי שאפשר יהיה להסיק שלכל k+1 הסוסים אותו צבע, מוכרח להיות סוס משותף לקבוצת הסוסים מלבד בוקפאלוס, ולקבוצת הסוסים שמלבד נגרו קבלו. דרישה זו מתקיימת אם k>1 (ואכן, לו היינו יודעים שלכל שני סוסים יש אותו צבע, יכולנו להסיק באינדוקציה שלסוסים בכל קבוצה סופית יש אותו צבע). ואולם, במקרה k=1 ההוכחה אינה נכונה (אין שום סיבה להניח שבוקפאלוס ונגרו קבלו הם בעלי אותו צבע, משום שאין סוס שלישי ששניהם שווים לו בצבעם).

