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

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

הוכחה לכאורה

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

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

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

השגיאה בהוכחה

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