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

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

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

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

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

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

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

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

החזירו רעיון פשוט: יש קבוצות שמכילות את עצמן, ויש כאלה שלא. ראסל בנה את X, שהיא הקבוצה של כל הקבוצות שלא שייכות לעצמן. נשאלת שאלה: האם X שייכת ל‑X?

אם X שייכת ל‑X, אז היא לא יכולה להיות ברשימת הקבוצות שלא שייכות לעצמן. אם X לא שייכת ל‑X, אז היא כן צריכה להיות ברשימה. בשני המקרים יש סתירה.

המקרה הזה מוסבר בסיפור על ספר בעיירה. הספר מספר רק אנשים שלא מספרים את עצמם. מה קורה אם הספר צריך להסתפר? זה יוצר בעיית לוגיקה דומה.

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

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

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