תורת הקבוצות/הלמה של צורן

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

ניסוח

ראשית נגדיר מושג חשוב:

הגדרה: שרשרת תהי $(A,\preceq )$ קבוצה סדורה חלקית לא ריקה. נאמר כי $C\subseteq A$ היא שרשרת, אם $(C,\preceq \!\!|_{C})$ סדורה מלא. (כאשר $\preceq \!\!|_{C}=\preceq \cap (C\times C)$ הוא הצמצום של הסדר לתת הקבוצה $C$.)

כעת נביא את נוסח הלמה:

למה "הלמה של צורן" תהי $(A,\preceq )$ קבוצה סדורה חלקית. אם לכל שרשרת ב$A$ יש חסם מלעיל (כלומר קיים $c\in A$ כך ש$x\preceq c$ לכל $x\in C$), אז יש לפחות מקסימום אחד ב$A$.

הוכחה

נניח בשלילה שלכל $x\in A$ קיים $y\in A$ כך ש$y\succ x$. כלומר הקבוצה $\{y|y\succ x\}$ לא ריקה. מאקסיומת הבחירה קיימת פונקציה המתאימה לכל קבוצה כזו אחד מאיבריה. הרכבת הפונקציה על הפונקציה $x\mapsto \{y|y\succ x\}$ תתן פונקציה $f:A\to A$ כך ש$f(x)\succ x$ לכל $x\in A$.

תהי ${\mathcal {C}}$ קבוצת כל השרשרות ב$A$. מהנתון לכל $C\in {\mathcal {C}}$, הקבוצה $\{x|\forall c\in C,c\preceq x\}$ לא ריקה, לכן קיימת פונקציה המתאימה לכל קבוצה כזו אחד מאיבריה. הרכבת הפונקציה על הפונקציה $C\mapsto \{x|\forall c\in C,c\preceq x\}$ תתן את הפונקציה $g:{\mathcal {C}}\to A$ עבורה $g(C)\succeq c$ לכל $c\in C\in {\mathcal {C}}$.

מהנתון $A$ לא ריקה, לכן מאקסיומת הבחירה יהי $p\in A$. נגדיר באינדוקציה טרנספיניטית פונקציה הפועלת על מספרים סודרים:

• $h(0)=p$
• $h(S(\alpha ))=f(h(\alpha ))$
• $h\left(\lambda \right)=f\left(g\left(\{h(x)|x<\lambda \}\right)\right)$ לכל $\lambda$ גבולי.

בהגדרתנו את הפונקציה על סודרים גבוליים, הנחנו כי $h[\lambda ]=\{h(x)|x<\lambda \}$ היא שרשרת ולכן ניתן להפעיל עליה את הפונקציה $g$. נראה זאת באמצעות שנוכיח כי הפונקציה היא שומרת סדר (כלומר $\alpha <\beta \Rightarrow h(\alpha )\prec h(\beta )$) עד $\lambda$ (כלומר לכל $x,y\in \lambda$ מתקיים $x<y\Rightarrow h(x)\prec h(y)$), ולכן לכל $x,y\in h[\lambda ]$ מתקיים $(x<y)\lor (x>y)\lor (x=y)\Rightarrow (h(x)\prec h(y))\lor (h(x)\succ h(y))\lor (h(x)=hx(y))$. נוכיח זאת באינדוקציה טרנספיניטית: עבור $\lambda =0$, הטענה מתקיימת באופן ריק. נניח נכונות עבור $\alpha$, ונוכיח עבור $S(\alpha )$: אם $x,y\in \alpha$, העניין ברור. לכן נניח כי $x\in \alpha ,y=\alpha$. אם $\alpha =S(\beta )$ עוקב, אז $x<\alpha \Rightarrow x\leq \beta \Rightarrow h(x)\preceq h(\beta )\prec f(h(\beta ))=h(\alpha )$. אם $\alpha =\bigcup _{\zeta <\alpha }\zeta$ גבולי, אז $x<\alpha$ גורר את $h(x)\in h[\alpha ]$, ומכיוון ש$h(\alpha )=f(g(h[\alpha ]))\succ g(h[\alpha ])$, ו$g(h[\alpha ])$ חסם מלעיל של $h[\alpha ]$, נקבל $h(x)\prec h(\alpha )$. כעת נניח כי $\lambda =\bigcup _{\zeta <\lambda }\zeta$ גבולי. אז $x,y\in \lambda =\bigcup _{\zeta <\lambda }\zeta \Rightarrow \exists \alpha ,\beta <\lambda :x\in \alpha \land y\in \beta \Rightarrow x,y\in \max\{\alpha ,\beta \}<\lambda$, ומהנחת התכונה לכל $\zeta <\lambda$, היא מתקיימת בפרט עבור $\zeta :=\max\{\alpha ,\beta \}$, ולכן $x<y\Rightarrow h(x)\prec h(y)$.

כשהוכחנו שהפונקציה מוגדרת, הוכחנו גם כי היא שומרת סדר, ובפרט חד-חד-ערכית (כי אם $x\not =y$, אז או $x<y$, ואז $h(x)\prec h(y)\Rightarrow h(x)\not =h(y)$, או ש$y<x$, ואז $h(y)\prec h(x)\Rightarrow h(x)\not =h(y)$). נגדיר על הקבוצה $A$ את הטענה $\phi (x,y)\equiv ((\exists \alpha (h(\alpha )=x)\Rightarrow y=x)\land (\lnot \exists \alpha (h(\alpha )=x)\Rightarrow y=p))$. מאקסיומת ההחלפה נובע כי קיימת תמונת הטענה, אותה נסמן ${\text{Im}}(h)$. קל לראות שלכל $x\in {\text{Im}}(h)$ קיים סודר $\alpha$ כך ש$h(\alpha )=x$, ומכך ש$h$ חד חד ערכית נובע ש$\alpha$ באופן יחיד. לכן הגדרת הטענה $\varphi (x,\alpha )\equiv (h(\alpha )=x)$ על הקבוצה ${\text{Im}}(h)$ תגרור, באמצעות אקסיומת ההחלפה, את קיום תמונת הטענה. כל סודר $\alpha$ הוא בתמונת הטענה, כי מתקיים $\varphi (h(\alpha ),\alpha )$, לכן תמונת הטענה היא מחלקת כל הסודרים ${\text{On}}$. מצד שני, מהפרדוקס של בורלי פורטי (טרם נכתב) נובע כי ${\text{On}}$ אינה קבוצה. סתירה.