משפט טרסקי

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

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

הוכחה

מטרתנו להוכיח כי אקסיומת הבחירה נובעת מן הטענה "לכל קבוצה אינסופית $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}$ הן זרות. על כן g משרה סדר טוב על $B$: לכל שני איברים $x,y\in B$ נגדיר $x\leq y\iff g(x)\leq g(y)$, שהרי התמונה של $g$, קרי $g[B]$, היא קבוצת סודרים ולכן סדורה היטב.