משפט טרסקי

בתורת הקבוצות האקסיומטית, משפט טַרְסְקִי, אותו הוכיח אלפרד טרסקי, מציג טענה השקולה לאקסיומת הבחירה: טרסקי הוכיח שאם מניחים רק את מערכת אקסיומות צרמלו־פרנקל, אז אקסיומת הבחירה נובעת מן הטענה "לכל קבוצה אינסופית $A$ , עוצמתה של המכפלה הקרטזית $A\times A$ שווה לזו של $A$ ", ובקיצור " $\alpha ^{2}=\alpha$ לכל עוצמה אינסופית". הכיוון ההפוך היה ידוע עוד קודם לכן, וכך הטענה שקולה לאקסיומת הבחירה.

כאשר טרסקי הציע את המאמר לפרסום ב- Comptes Rendus Acad. Sci. Paris, דחה אותו מוריס פרשה בטענה שגרירה לוגית בין שתי טענות שהן נכונות ממילא, אינה תוצאה מעניינת. אנרי לבג דחה אף הוא את המאמר, באומרו שהוא אינו מוצא כל עניין בקשר לוגי בין שתי טענות שקריות.^[1] אפיזודה זו משקפת את הלוך הרוחות בין אנשי תורת הקבוצות בתחילת המאה ה-20, כאשר מעמדה של אקסיומת הבחירה היה שנוי במחלוקת.

הוכחה

מטרתנו להוכיח כי אקסיומת הבחירה נובעת מן הטענה "לכל קבוצה אינסופית $A$ מתקיים $|A|=|A\times A|$ ". כידוע, משפט הסדר הטוב שקול לאקסיומת הבחירה, ולכן יהיה מספיק להראות שמן הטענה נובע כי לכל קבוצה $B$ קיים סדר טוב.

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

כיוון שאוסף כל הסודרים כך שיש פונקציה על מ- $B$ אל הסודר היא קבוצה – יש סודר מינימלי $\beta$ , כך שאין פונקציה על מ- $B$ ל- $\beta$ . נניח ללא הגבלת הכלליות שהקבוצות $B,\beta$ זרות. לפי ההנחה, $|B\cup \beta |=|(B\cup \beta )\times (B\cup \beta )|$ , ולכן קיימת פונקציה חד-חד-ערכית ועל $f:B\cup \beta \to (B\cup \beta )\times (B\cup \beta )$ .

לכל $x\in B$ , לא ייתכן שהקבוצה $\beta \times \{x\}$ מכוסה על ידי הפעלת $f$ על איברי $B$ בלבד (כלומר לא ייתכן שמתקים $\beta \times \{x\}\subseteq f[B]$ ), שכן אחרת ניתן היה להגדיר פונקציה על מ- $B$ ל- $\beta$ . לכן, קיים לפחות סודר אחד $\gamma \in \beta$ המקיים $f(\gamma )\in \beta \times \{x\}$ , ומכאן שהקבוצה $S_{x}=\{\gamma |f(\gamma )\in \beta \times \{x\}\}$ אינה ריקה.

בעזרת תכונה זו נוכל להגדיר פונקציה חדשה: $g(x)=\min S_{x}$ . פונקציה זו מוגדרת היטב שכן $S_{x}$ הינה קבוצה לא ריקה של סודרים, ולכן קיים לה מינימום. נזכור כי לכל $x,y\in B,x\neq y$ הקבוצות $S_{x},S_{y}$ הנן זרות. על כן, פונקציה זו משרה סדר טוב על $B$ , לכל שני איברים $x,y\in B$ נגדיר $x\leq y\iff g(x)\leq g(y)$ , שהרי התמונה של $g$ , קרי $g[B]$ , היא קבוצת סודרים ולכן סדורה היטב.