פרדוקס הסוסים

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

P6200200 Paarden in het voorjaar.JPG

הוכחה לכאורה[עריכת קוד מקור | עריכה]

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

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

בכך הוכחנו, לכאורה, את הטענה - ומכיוון שבעולם מספר סופי של סוסים, כולם מוכרחים להיות בעלי אותו צבע.

השגיאה בהוכחה[עריכת קוד מקור | עריכה]

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