הלמה של צורן

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

הלמה של צורן

ניסוח

תהי [math]\displaystyle{ X }[/math] קבוצה סדורה חלקית (קבוצה עם יחס סדר חלקי [math]\displaystyle{ \le }[/math]). תת-קבוצה [math]\displaystyle{ C }[/math] של [math]\displaystyle{ X }[/math] הסדורה קוית (כל שני איברים של [math]\displaystyle{ C }[/math] ניתנים להשוואה) נקראת שרשרת.

דוגמאות: אם [math]\displaystyle{ x_1\lt x_2 \lt \cdots }[/math] אז [math]\displaystyle{ \{x_1,x_2,\dots\} }[/math] היא שרשרת, שבה לכל איבר יש עוקב מיידי. אבל בדרך כלל אין זה המצב. למשל, המספרים הרציונליים מהווים שרשרת שבה אין לאף איבר עוקב מיידי. המספרים הממשיים הם שרשרת שאינה בת מניה.

הלמה של צורן. תהי [math]\displaystyle{ X }[/math] קבוצה לא ריקה, עם התכונה שלכל שרשרת (לא ריקה) ב-[math]\displaystyle{ X }[/math] יש חסם מלעיל. אז יש ב-[math]\displaystyle{ X }[/math] איבר מקסימלי.

הערות

1. הטענה כמובן אינה נכונה אם [math]\displaystyle{ X }[/math] ריקה. זו אינה נקודה שולית: הלמה של צורן מספקת הוכחת קיום, וכדי להפעיל אותה יש לוודא שקיים איזשהו איבר בקבוצה [math]\displaystyle{ X }[/math]; רק אחר-כך מספקת הלמה איבר מקסימלי בקבוצה.
2. הכיוון ההפוך ללמה הוא טריוויאלי: איבר מקסימלי של [math]\displaystyle{ X }[/math] הוא חסם מלעיל לכל תת-קבוצה.
3. אם [math]\displaystyle{ X }[/math] קבוצה סדורה לינארית, טענת הלמה נכונה באופן טריוויאלי (משום ש-[math]\displaystyle{ X }[/math] עצמה היא שרשרת, ולפי ההנחה יש לה חסם מלעיל, שהוא איבר מקסימלי). הלמה נועדה, איפוא, לטפל במקרים שבהם הסדר של [math]\displaystyle{ X }[/math] אינו לינארי.
4. במקרה שהקבוצה הסדורה [math]\displaystyle{ X }[/math] סופית, אין צורך בלמה: ניקח איבר כלשהו של [math]\displaystyle{ X }[/math]. אם הוא מקסימלי, סיימנו. אחרת, ניקח איבר שגדול ממנו. אם האיבר החדש מקסימלי, סיימנו. אחרת, ניקח איבר שגדול ממנו, וכו'. כל עוד איננו נעצרים באיבר מקסימלי, אנו מקבלים איברים חדשים של [math]\displaystyle{ X }[/math]. כיון שהקבוצה [math]\displaystyle{ X }[/math] סופית, התהליך חייב להפסק לאחר מספר סופי של צעדים, כלומר ניעצר באיבר מקסימלי.
5. מבחינה אינטואיטיבית, אפשר לבצע את התהליך של ההערה הקודמת גם במקרה ש [math]\displaystyle{ X }[/math] קבוצה אינסופית. כאן, מופיע מרכיב נוסף: לאחר שבחרנו איברים [math]\displaystyle{ x_1\lt x_2\lt x_3\lt \cdots }[/math], ייתכן שאף אחד מהם אינו מקסימלי. זה המקום שעלינו להשתמש בתנאי של הלמה של צורן, האומר שלכל שרשרת, ובפרט לשרשרת הזו, יש חסם מלעיל. נקרא לו, למשל, [math]\displaystyle{ x_\omega }[/math]. כעת אפשר להמשיך את התהליך של בחירת איברים יותר ויותר גדולים, ואם לא ניעצר, נקבל שוב שרשרת, ושוב יהיה לה חסם מלעיל, ושוב אפשר להמשיך. בכל צעד, מוסיפים לשרשרת איבר חדש של X. לכן, התהליך חייב להיעצר מתישהו לפני שהקבוצה [math]\displaystyle{ X }[/math] "נגמרת". כיון שהקבוצה אינסופית, לא ברורה המשמעות של הטיעון הזה כל עוד לא מפתחים מנגנון עבור בניה באינדוקציה מעבר למקרה הבן מניה. כיון שאין כאן המקום להאריך בזה, ניתן במקום זאת הוכחה בצורה אחרת.

הלמה של צורן עבור משפחה של קבוצות

כדי להפעיל את הלמה של צורן יש להראות (אחרי שמוודאים שהקבוצה [math]\displaystyle{ X }[/math] אינה ריקה) שלכל שרשרת יש חסם מלעיל. אם [math]\displaystyle{ X }[/math] היא משפחה של קבוצות, זה עשוי להיות קל במיוחד. אנו אומרים ש-[math]\displaystyle{ X }[/math] סגורה לאיחוד של שרשראות אם לכל שרשרת [math]\displaystyle{ C \subseteq X }[/math], האיחוד [math]\displaystyle{ \bigcup_{A \in C} A }[/math] של כל הקבוצות בשרשרת שייך ל-[math]\displaystyle{ X }[/math].

(שוב, אם [math]\displaystyle{ X }[/math] היתה סדורה לינארית, אפשר היה לקחת את האיחוד של כל הקבוצות ב-[math]\displaystyle{ X }[/math]; אלא שבכל המקרים המעניינים, [math]\displaystyle{ X }[/math] אינה לינארית, ואפילו אינה סגורה ביחס לאיחוד סופי של סתם שני אברים).

הלמה של צורן עבור משפחה של קבוצות: תהי [math]\displaystyle{ X }[/math] משפחה לא ריקה של קבוצות, הסגורה לאיחוד של שרשראות. אז יש ב-[math]\displaystyle{ X }[/math] איבר מקסימלי.

הוכחת הלמה של צורן תובא בהמשך. ראשית, נראה דוגמאות ליישומיה החשובים.

שימושים

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

יחס הסדר בין עוצמות הוא לינארי

משפט. לכל שתי קבוצות [math]\displaystyle{ A,B }[/math] מתקיים [math]\displaystyle{ \ |A| \leq |B| }[/math] או [math]\displaystyle{ \ |B| \leq |A| }[/math].

הוכחה: פונקציה [math]\displaystyle{ f }[/math] שתחומה הוא תת-קבוצה של הקבוצה [math]\displaystyle{ A }[/math] והתמונה שלה היא תת-קבוצה של הקבוצה [math]\displaystyle{ B }[/math] תיקרא פונקציה חלקית מ [math]\displaystyle{ A }[/math] ל [math]\displaystyle{ B }[/math]. תהי [math]\displaystyle{ X }[/math] משפחת כל הפונקציות החלקיות החד-חד ערכיות מ [math]\displaystyle{ A }[/math] ל [math]\displaystyle{ B }[/math].

תרגיל: המשפחה [math]\displaystyle{ X }[/math] מקיימת את תנאי הלמה של צורן עבור קבוצות.

לכן, יש במשפחה [math]\displaystyle{ X }[/math] איבר מקסימלי [math]\displaystyle{ f }[/math]. זוהי פונקציה חלקית חד-חד ערכית מקסימלית (מבחינת הכלה) מ [math]\displaystyle{ A }[/math] ל [math]\displaystyle{ B }[/math]. נבחן את האפשרויות השונות:

א. תחום הפונקציה [math]\displaystyle{ f }[/math] הוא הקבוצה [math]\displaystyle{ A }[/math] כולה. אז [math]\displaystyle{ f\colon A\to B }[/math] פונקציה חד-חד ערכית, ולכן [math]\displaystyle{ |A|\le |B| }[/math].

ב. תמונת הפונקציה [math]\displaystyle{ f }[/math] היא הקבוצה [math]\displaystyle{ B }[/math] כולה. אז [math]\displaystyle{ f^{-1}\colon B\to A }[/math] היא פונקציה (במובן הרגיל) חד-חד ערכית, ולכן [math]\displaystyle{ |B|\le |A| }[/math].

ג. נניח בשלילה שאף אחד מבין (א) או (ב) אינו מתקיים. אז יש איברים [math]\displaystyle{ a\in A,b\in B }[/math] כך ש [math]\displaystyle{ a }[/math] אינו בתחום הפונקציה [math]\displaystyle{ b }[/math] ו [math]\displaystyle{ f }[/math] אינו בתמונת הפונקציה [math]\displaystyle{ f }[/math]. במקרה זה, אפשר להרחיב את הפונקציה [math]\displaystyle{ f }[/math] לפונקציה [math]\displaystyle{ f':=f\cup\{(a,b)\} }[/math], או במלים אחרות, על ידי הגדרת [math]\displaystyle{ f'(a)=b }[/math] (ועבור [math]\displaystyle{ x\in\operatorname{dom}(f) }[/math] נגדיר [math]\displaystyle{ f'(x)=f(x) }[/math]). נקבל פונקציה חלקית חד-חד ערכית (בדוק!) מ [math]\displaystyle{ A }[/math] ל [math]\displaystyle{ B }[/math] המרחיבה ממש את הפונקציה [math]\displaystyle{ f }[/math], בסתירה למקסימליות [math]\displaystyle{ f }[/math] במשפחה [math]\displaystyle{ X }[/math].

לסיכום, בהכרח מתקיים (א) (ואז [math]\displaystyle{ |A|\le |B| }[/math]) או (ב) (ואז [math]\displaystyle{ |B|\le |A| }[/math]). מ.ש.ל

סכום ומכפלה של עוצמות

משפט. לכל קבוצה אינסופית A מתקיים [math]\displaystyle{ \ |A\times A| = |A| }[/math].

מסקנה. אם [math]\displaystyle{ \max\{|A|,|B|\} }[/math] עוצמה אינסופית, אז [math]\displaystyle{ \ |A|\cdot |B| = \max\{|A|,|B|\} }[/math].

הוכחה. נניח ש-[math]\displaystyle{ \ |A|\leq |B| }[/math]; לפי ההנחה |B| אינסופית, ולכן [math]\displaystyle{ \ |B| = 1\cdot |B| \leq |A|\cdot |B| \leq |B| \cdot |B| = |B| }[/math].

מסקנה. לכל שתי קבוצות אינסופיות A,B מתקיים [math]\displaystyle{ \ |A| + |B| = \max\{|A|,|B|\} }[/math].

הוכחה. [math]\displaystyle{ \ \max\{|A|,|B|\} \leq |A| + |B| \leq = 2 \max\{|A|,|B|\} = \max\{|A|,|B|\} }[/math].

לכל מרחב וקטורי יש בסיס

משפט. לכל מרחב וקטורי יש בסיס.

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

הוכחה. יהי V מרחב וקטורי מעל שדה F. נסמן ב-X את משפחת תת-הקבוצות של V שאינן תלויות לינארית (הקבוצה הריקה שייכת ל-X, ולכן X אינה ריקה). נוכיח ש-X סגורה לאיחוד של שרשראות. אכן, תהי C שרשרת ב-X. נתבונן באיחוד [math]\displaystyle{ \ \bigcup_{A \in C} A }[/math]. יהיו [math]\displaystyle{ \ v_1,\dots,v_n \in \bigcup_{A \in C} A }[/math] אברים של המרחב, כך שקיימים סקלרים [math]\displaystyle{ \ \alpha_1,\dots,\alpha_n \in F }[/math] כך ש-[math]\displaystyle{ \ \alpha_1v_1+\cdots+\alpha_nv_n = 0 }[/math]. לכל [math]\displaystyle{ \ i=1,\dots,n }[/math] יש איבר [math]\displaystyle{ \ A_i \in C }[/math] כך ש-[math]\displaystyle{ \ v_i \in A_i }[/math]; אבל C היא שרשרת, ולכן מבין האברים [math]\displaystyle{ \ A_1,\dots,A_n }[/math] יש אחד המכיל את כולם; נאמר שזהו [math]\displaystyle{ \ A_n }[/math]. אז [math]\displaystyle{ \ v_1,\dots,v_n \in A_n }[/math], אבל [math]\displaystyle{ \ A_n }[/math] בלתי תלויה לינארית (משום שהיא שייכת ל-X), ולכן המקדמים [math]\displaystyle{ \ \alpha_1,\dots,\alpha_n }[/math] שווים כולם לאפס.

לפי הלמה של צורן, יש ב-X קבוצה מקסימלית, שנסמן ב-B. היא בלתי-תלויה לינארית (משום שכל הקבוצות ב-X כאלה). נשאר להראות שהיא פורשת את המרחב V. יהי [math]\displaystyle{ \ v\in V }[/math]. אם הוקטור v אינו נפרש על-ידי B, אז הקבוצה [math]\displaystyle{ \ B \cup \{v\} }[/math] בלתי-תלויה לינארית, וזו סתירה למקסימליות של B. לכן כל וקטור נפרש על-ידי B, ומכאן ש-B בסיס.

עקרון המקסימום של האוסדורף

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

למה. איחוד של שרשרת של שרשראות הוא בעצמו שרשרת. אכן, תהי [math]\displaystyle{ \ \Lambda = \{A_{\alpha}\} }[/math] שרשרת של שרשראות (היינו, כל [math]\displaystyle{ \ A_{\alpha} }[/math] היא שרשרת, ולכל [math]\displaystyle{ \ \alpha,\beta }[/math] מתקיים [math]\displaystyle{ \ A_{\alpha} \subseteq A_{\beta} }[/math] או [math]\displaystyle{ \ A_{\beta} \subseteq A_{\alpha} }[/math]). יהיו [math]\displaystyle{ \ x,y \in \bigcup \Lambda }[/math], אז יש [math]\displaystyle{ \ \alpha, \beta }[/math] כך ש-[math]\displaystyle{ \ x\in A_{\alpha}, y \in A_{\beta} }[/math]. נניח, בלי הגבלת הכלליות, ש-[math]\displaystyle{ \ A_{\alpha} \subseteq A_{\beta} }[/math]. אז [math]\displaystyle{ \ x,y \in A_{\beta} }[/math], והם נתנים להשוואה משום ש-[math]\displaystyle{ \ A_{\beta} }[/math] שרשרת.

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

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

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

טענה. הלמה של צורן נובעת מעקרון המקסימום. אכן, קח שרשרת מקסימלית, A. לפי ההנחה יש לה חסם מלעיל, a, שהוא איבר מקסימלי, משום שאם יש [math]\displaystyle{ \ a \lt b }[/math] אז [math]\displaystyle{ \ A \cup \{b\} }[/math] היתה שרשרת גדולה יותר.

עקרון הסדר הטוב

משפט. על כל קבוצה X קיים סדר טוב.

הוכחה. נסמן ב-[math]\displaystyle{ \ \Omega }[/math] את אוסף הזוגות הסדורים [math]\displaystyle{ (A,R) }[/math] כאשר [math]\displaystyle{ A \subseteq X }[/math] ו-[math]\displaystyle{ R \subseteq A \times A }[/math] יחס סדר טוב על A. מגדירים על [math]\displaystyle{ \Omega }[/math] יחס סדר: [math]\displaystyle{ (A,R) \leq (A',R') }[/math] אם [math]\displaystyle{ A \subseteq A' }[/math] ו-[math]\displaystyle{ R = (A \times A) \cap R' }[/math]. לכל שרשרת [math]\displaystyle{ (A_{\lambda},R_{\lambda}) }[/math] ב-[math]\displaystyle{ \Omega }[/math], האיחוד [math]\displaystyle{ (\bigcup A_{\lambda}, \bigcup R_{\lambda}) }[/math] הוא קבוצה סדורה היטב, ולכן איבר של [math]\displaystyle{ \Omega }[/math] שהוא חסם מלעיל של השרשרת. לפי הלמה של צורן, יש ל-[math]\displaystyle{ \Omega }[/math] איבר מקסימלי, [math]\displaystyle{ (Y,S) }[/math]. אם יש איבר [math]\displaystyle{ x \in X \setminus Y }[/math]; אם נעשיר את [math]\displaystyle{ Y }[/math] בקביעה ש-[math]\displaystyle{ y \leq x }[/math] לכל [math]\displaystyle{ y\in Y }[/math], נקבל סדר טוב על [math]\displaystyle{ Y \cup \{x\} }[/math], בסתירה למקסימליות של [math]\displaystyle{ (Y,S) }[/math]. מכאן ש-[math]\displaystyle{ Y = X }[/math], וסיימנו.

יש על-מסנן לא ראשי

"מסנן" על קבוצה D הוא אוסף של תת-קבוצות, הסגור לחיתוך סופי ולהגדלה (אם A שייכת למסנן אז גם כל תת-קבוצה של D המכילה אותה שייכת למסנן). בנוסף דורשים שהמסנן לא יכלול את הקבוצה הריקה (משום שבמקרה כזה הוא צריך להיות שווה לקבוצת החזקה של D. "על-מסנן" הוא מסנן הכולל את אחד החלקים בכל פירוק של D כאיחוד של שתי קבוצות זרות. למשל, תהי a נקודה ב-X; אוסף תת-הקבוצות ש-a שייך אליהן הוא על-מסנן. על-מסנן כזה נקרא "על-מסנן ראשי", והוא נחשב לטריוויאלי. האם קיים על-מסנן שאינו ראשי?

למה. מסנן מהווה על-מסנן אם ורק אם הוא מקסימלי (כלומר, אינו מוכל באף מסנן גדול יותר).

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

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

מסקנה. על כל קבוצה אינסופית יש על-מסנן לא ראשי. אכן, אוסף הקבוצות שהמשלים שלהן סופי הוא מסנן (קרוי "מסנן פרשה", על-שם Maurice Frechet), ואינו יכול להיות מוכל בעל-מסנן ראשי.

בכל חוג יש אידאל מקסימלי

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

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

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

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

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

תרגיל. יהי S מונויד כפלי בחוג R, שאינו כולל את 0. הראה שיש אידיאל שהוא מקסימלי בין אלו שאינם חותכים את S. (כל אידיאל כזה הוא "אידיאל ראשוני").

תרגיל. לכל מודול נוצר סופית יש תת-מודול (אמיתי) מקסימלי.

לכל שדה יש סגור אלגברי

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

משפט. לכל שדה F יש סגור אלגברי.

ההוכחה מתחילה באידיאל הנוצר על-ידי הצבות של משתנים פורמליים בכל הפולינומים (המתוקנים) מעל השדה. כפי שראינו לעיל (בעזרת הלמה של צורן), האידיאל הזה מוכל באידיאל מקסימלי, וחוג המנה (של כל חוג קומוטטיבי מעל אידיאל מקסימלי) הוא שדה. לפרטים, ראה כאן, סעיף 4.1.5 בעמ' 65.

הסגור האלגברי יחיד עד-כדי איזומורפיזם

משפט. כל שני סגורים אלגבריים של אותו שדה F, הם איזומורפיים (כהרחבות של F).

יהיו E_1, E_2 שני סגורים אלגבריים של F. הפעם מבוססת ההוכחה על משפחת השיכונים של תת-שדות של E_1 בתוך E_2. גם כאן, השיכון ה"מקסימלי" (מושג שיש להגדיר, כמובן) מהווה שיכון מלא של E_1 לתוך E_2; אבל אז E_2 הוא הרחבה אלגברית של השדה E_1, שהוא סגור אלגברית, ולכן השיכון הוא על. ראה כאן, סעיף 4.1.6, עמ' 66 לפרטים.

התשתית של מודול היא סכום ישר של תת-מודולים פשוטים

יהי M מודול מעל חוג R. התשתית שלו, אותה מסמנים ב-[math]\displaystyle{ \ \operatorname{soc}(M) }[/math], היא הסכום של כל תת-המודולים הפשוטים של M.

משפט. [math]\displaystyle{ \ \operatorname{soc}(M) }[/math] הוא סכום ישר של תת-מודולים פשוטים של M (בדרך כלל לא כולם).

הוכחה. נסמן ב-X את המשפחות של תת-מודולים פשוטים שהסכום שלהם הוא ישר (המשפחה הריקה היא כזו, ולכן X לא ריקה). X סגור לאיחוד של שרשראות (ההוכחה דומה לזו של קיום הבסיס למרחב וקטורי). לכן יש ב-X משפחה מקסימלית, שנסמן ב-S. אם קיים תת-מודול פשוט שאינו מוכל בסכום שלה, אז צירופו למשפחה נותן משפחה בלתי-תלויה גדולה יותר, בסתירה למקסימליות. לכן כל תת-מודול פשוט מוכל בסכום של אברי S; מכן שהסכום הזה (שהוא סכום ישר כי S שייכת ל-X) שווה ל-[math]\displaystyle{ \ \operatorname{soc}(M) }[/math].

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

הוכחת הלמה של צורן

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

קבוצות סדורות היטב

אומרים שקבוצה סדורה [math]\displaystyle{ A }[/math] היא סדורה היטב אם בכל תת-קבוצה לא ריקה שלה יש איבר ראשון (איבר שהוא קטן או שווה לכל איבר אחר בתת-הקבוצה; לא די בקיומו של איבר מינימלי).

הערות

1. כל קבוצה סדורה היטב היא שרשרת. אכן, יהיו [math]\displaystyle{ a,b }[/math] אברים בקבוצה, אז בקבוצה הלא-ריקה [math]\displaystyle{ \{a,b\} }[/math] יש איבר ראשון, שהוא איבר הקטן מן האיבר השני. לכן כל שני אברים ניתנים להשוואה.

1. כל תת-קבוצה של קבוצה סדורה היטב [math]\displaystyle{ A }[/math] - גם היא סדורה היטב. (משום שכל תת-קבוצה של תת-הקבוצה היא גם תת-קבוצה של [math]\displaystyle{ A }[/math], ולכן יש בה איבר ראשון).
2. שרשרת היא סדורה היטב אם בכל תת-קבוצה לא ריקה שלה יש איבר מינימלי.

רישות

תת-קבוצה [math]\displaystyle{ H }[/math] של קבוצה סדורה היטב [math]\displaystyle{ A }[/math] נקראת רישא, אם היא "סגורה כלפי מטה", כלומר כל איבר של [math]\displaystyle{ A }[/math] הקטן מאיזשהו איבר של [math]\displaystyle{ H }[/math] שייך גם הוא ל [math]\displaystyle{ H }[/math].

בפרט, הקבוצה הריקה היא רישא.

הערה. איחוד משפחה של רישות של [math]\displaystyle{ A }[/math] הוא רישא.

לכל [math]\displaystyle{ a\in A }[/math] נסמן [math]\displaystyle{ \ A_{\lt a} = \{x \in A : x \lt a\} }[/math]. זוהי תמיד רישא של A.

טענה. לכל רישא [math]\displaystyle{ H\neq A }[/math] של קבוצה סדורה היטב [math]\displaystyle{ A }[/math] קיים [math]\displaystyle{ a \in A }[/math] כך ש-[math]\displaystyle{ H = A_{\lt a} }[/math].

הוכחה. כיון ש [math]\displaystyle{ H }[/math] סגורה כלפי מטה ו [math]\displaystyle{ A }[/math] סדורה קוית, כל איבר של [math]\displaystyle{ A }[/math] שאינו ב [math]\displaystyle{ H }[/math] הוא חסם מלעיל של [math]\displaystyle{ H }[/math]. בפרט, קבוצת החסמים מלעיל של [math]\displaystyle{ H }[/math] אינה ריקה ויש בה איבר ראשון [math]\displaystyle{ a }[/math]. מאותה סיבה, קל לראות ש [math]\displaystyle{ H=A_{\lt a} }[/math].

מסקנה. תהי [math]\displaystyle{ A }[/math] קבוצה סדורה היטב. יש התאמה חד-חד-ערכית ועל, השומרת סדר, בין [math]\displaystyle{ A }[/math] לבין קבוצת הרישות האמיתיות של A.

במלים אחרות, קבוצת הרישות האמיתיות של [math]\displaystyle{ A }[/math], הסדורה על ידי היחס [math]\displaystyle{ \subseteq }[/math], איזומורפית כקבוצה סדורה ל-[math]\displaystyle{ A }[/math].

הגרסה החזקה של הלמה של צורן

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

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

שאר הסעיף מוקדש להוכחת הלמה (על-פי Pierre-Yves Gaillard). ההוכחה בדרך השלילה. נניח שאין ל-X איבר מקסימלי.

נסמן ב-[math]\displaystyle{ \ \Omega }[/math] את אוסף תת-הקבוצות הסדורות היטב של X. לפי ההנחה, כל [math]\displaystyle{ W\in \Omega }[/math] היא חסומה מלעיל. יתרה מזו, לפי הנחת השלילה אין ב-W איבר מקסימלי של X, ולכן אפילו הקבוצה [math]\displaystyle{ \ W^{\circ} = \{x \in X : W \lt x\} }[/math] אינה ריקה. לפי אקסיומת הבחירה, קיימת פונקציה [math]\displaystyle{ \ p : \Omega \rightarrow X }[/math], המתאימה לכל [math]\displaystyle{ \ W \in \Omega }[/math] איבר [math]\displaystyle{ \ p(W) \in W^{\circ} }[/math], כלומר לכל W מתקיים [math]\displaystyle{ \ W \lt p(W) }[/math].

נאמר שתת-קבוצה סדורה היטב W היא מדוייקת אם לכל [math]\displaystyle{ \ w\in W }[/math] מתקיים [math]\displaystyle{ p(W_{\lt w}) = w }[/math]. (שימו לב שבכל מקרה האיבר w הוא חסם מלעיל של הרישא [math]\displaystyle{ \ W_{\lt w} }[/math], ולכן יתכן ש-[math]\displaystyle{ \ p(W_{\lt w})=w }[/math]). (הערה. השאלה איזו תת-קבוצה W היא מדוייקת תלויה בפונקציה p, שעצם קיומה תלוי בהנחת השלילה על כך שאין ל-X איברים מקסימליים; משנוכיח שהנחה זו מביאה לסתירה, יתברר שאי-אפשר להגדיר את p, וממילא יתפוגג המושג הזה ויאבד את משמעותו).

נסמן ב-[math]\displaystyle{ \ \Omega^* }[/math] את קבוצת תת-הקבוצות המדוייקות של X. תהי U האיחוד של כל הקבוצות השייכות ל-[math]\displaystyle{ \ \Omega^* }[/math]. מטרתנו להוכיח ש-U עצמה היא קבוצה מדוייקת.

טענה 1. לכל [math]\displaystyle{ \ W,W' \in \Omega^* }[/math], אחת מהן היא רישא של השניה. אכן, תהי Q האיחוד של כל הרישות המשותפות ל-[math]\displaystyle{ \ W,W' }[/math]; אז Q רישא משותפת בעצמה. אם נניח ש-[math]\displaystyle{ \ Q \neq W,W' }[/math], אז יש [math]\displaystyle{ \ a\in W, a'\in W' }[/math] כך ש- [math]\displaystyle{ \ Q = W_{\lt a} = W'_{\lt a'} }[/math], אבל אז [math]\displaystyle{ \ a = p(Q) = a' }[/math] מכיוון ש-[math]\displaystyle{ \ W,W' }[/math] מדוייקות, ויוצא ש-[math]\displaystyle{ \ Q \cup \{p(Q)\} }[/math] גם היא רישא משותפת ל-[math]\displaystyle{ \ W,W' }[/math], בסתירה להגדרה של Q. מכאן ש- [math]\displaystyle{ \ Q = W }[/math] או [math]\displaystyle{ \ Q = W' }[/math], וזה מוכיח את טענה 1.

מסקנה 2. [math]\displaystyle{ \ \Omega^* }[/math] סדורה לינארית. אכן, מכל שני אברים של [math]\displaystyle{ \ \Omega^* }[/math], אחד הוא רישא של השני, ולכן מוכל בו.

מסקנה 3. [math]\displaystyle{ \ U }[/math] היא שרשרת. אכן, לכל [math]\displaystyle{ \ a,a' \in U }[/math] יש [math]\displaystyle{ \ W,W' \in \Omega^* }[/math] כך ש-[math]\displaystyle{ \ a\in W, a' \in W' }[/math]; ולפי מסקנה 2 אפשר להניח [math]\displaystyle{ \ W \subseteq W' }[/math] (או להיפך) ואז [math]\displaystyle{ \ a,a' \in W' }[/math], והרי [math]\displaystyle{ \ W' }[/math] שרשרת.

טענה 4. כל [math]\displaystyle{ \ W \in\Omega^* }[/math] הוא רישא של U. אכן, [math]\displaystyle{ \ W \subseteq U }[/math] לפי ההגדרה של U כאיחוד הקבוצות השייכות ל-[math]\displaystyle{ \ \Omega^* }[/math], ולפי טענה 1, W היא רישא של U.

טענה 5. U סדורה היטב. תהי A תת-קבוצה לא ריקה של U, אז יש [math]\displaystyle{ \ W \in \Omega^* }[/math] החותכת את A באופן לא ריק, ומכיוון ש-W סדורה היטב, יש לחיתוך [math]\displaystyle{ \ A \cap W\neq \emptyset }[/math] איבר מינימלי, m. נראה ש-m הוא המינימום של A כולה. יהי [math]\displaystyle{ \ a \in A }[/math]. לפי מסקנה 3, a בר-השוואה עם m. אם [math]\displaystyle{ \ a \lt m }[/math] נקבל מטענה 4 ש-[math]\displaystyle{ \ a \in W }[/math] בסתירה למינימליות של m. לכן [math]\displaystyle{ \ m \leq a }[/math], כפי שרצינו.

טענה 6. [math]\displaystyle{ \ U \in \Omega^* }[/math]. עלינו להראות ש-U מדוייקת, ולאור טענה 5, די להראות שלכל [math]\displaystyle{ \ u \in U }[/math] מתקיים [math]\displaystyle{ \ p(U_{\lt u}) = u }[/math]. אבל לפי הגדרת U, יש [math]\displaystyle{ \ W \in \Omega^* }[/math] כך ש-[math]\displaystyle{ \ u \in W }[/math], ואז [math]\displaystyle{ \ U_{\lt u} \subset W }[/math] והטענה נובעת מכך ש-W מדוייקת.

מכיוון ש-U סדורה היטב, יש איבר [math]\displaystyle{ \ p(U) \in X }[/math]. כצעד אחרון בהוכחה, נראה שגם [math]\displaystyle{ \ \bar{U} = U\cup\{p(U)\} \in \Omega^* }[/math]. ברור ש-[math]\displaystyle{ \ \bar{U} }[/math] היא שרשרת. אם [math]\displaystyle{ \ u \in \bar{U} }[/math], יש שתי אפשרויות: אם [math]\displaystyle{ \ u = p(U) }[/math] אז [math]\displaystyle{ \ \bar{U}_{\lt u} = U }[/math] וממילא [math]\displaystyle{ \ p(U) = u }[/math]; ואחרת [math]\displaystyle{ \ p(\bar{U}_{\lt u}) = p(U_{\lt u}) = u }[/math] לפי טענה 6. אבל מהגדרת U נובע עכשיו ש-[math]\displaystyle{ \ \bar{U} \subseteq U }[/math], וזו סתירה משום שלפי הנחת השלילה [math]\displaystyle{ \ U \lt p(U) }[/math].

קשרים לאקסיומות של המתמטיקה

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

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

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

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

אקסיומת הבחירה

((ניסוח, הסבר. בהוכחת הלמה של צורן השתמשנו באקסיומת הבחירה בכך שבחרנו את החסמים [math]\displaystyle{ \ p(U) }[/math] לכל U. ))

((הוכחה שאקסיומת הבחירה נובעת מן הלמה של צורן.))