הפרדוקס של ראסל

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

מוסכמה בסיסית בתורת הקבוצות קובעת שקבוצה מוגדרת על-פי האיברים השייכים לה. ראסל התייחס להנחה יסודית אחרת, שלפיה אפשר (לכאורה) להגדיר קבוצה באמצעות כלל שיקבע מהם האיברים השייכים לה.

הפרדוקס

כדי להציג את הפרדוקס של ראסל, נאמר שקבוצה גדולה היא קבוצה הכוללת את עצמה כאיבר, וכל קבוצה אחרת (כלומר, שאיננה איבר של עצמה), היא קבוצה קטנה.

ראסל הגדיר את קבוצת כל הקבוצות הקטנות, X, ושאל:

  • האם X היא קבוצה קטנה או גדולה?

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

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