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

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

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

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

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

אם יש רק סוס אחד, ברור הצבע שלו. מניחים שעבור k סוסים כלם באותו צבע. נבחן קבוצה של k+1 סוסים. יוצאים סוס אחד, נשארים k סוסים בצבע אחד. מחזירים אותו ומוציאים סוס אחר. שוב נשארים k סוסים בצבע אחד. לכן נדמה שכל ה-k+1 סוסים באותו צבע.

הבעיה מתגלה כאשר יש רק שני סוסים. אז אין סוס שבאמצע שמקשר בין שתי הקבוצות. לכן אי אפשר להסיק שהשניים הם באותו צבע. זהו הכשל של ההוכחה.