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

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

P6200200 Paarden in het voorjaar.JPG

הוכחה לכאורה

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

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

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