שינויים

תהי <math>X </math> '''קבוצה סדורהחלקית''' (קבוצה עם יחס סדר חלקי חלש<math>\le</math>). תת-קבוצה <math>C</math> של <math>X </math> הסדורה לינארית קוית (כל שני איברים של <math>C</math> ניתנים להשוואה) נקראת '''שרשרת'''.

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

'''הלמה של צורן'''. תהי <math>X </math> קבוצה לא ריקה, עם התכונה שלכל שרשרת (לא ריקה) ב-<math>X </math> יש חסם מלעיל. אז יש ב-<math>X </math> איבר מקסימלי.

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

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

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

== הוכחת '''הלמה של צורן ==עבור משפחה של קבוצות:''' תהי <math>X</math> משפחה לא ריקה של קבוצות, הסגורה לאיחוד של שרשראות. אז יש ב-<math>X</math> איבר מקסימלי.

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

=== קבוצות סדורות היטב =שימושים ==

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

'''הערהמשפט'''. כל תת-קבוצה של קבוצה סדורה היטב לכל שתי קבוצות <math>A, גם היא סדורה היטב. (משום שתת-קבוצה של תת-הקבוצה היא גם תת-קבוצה של B</math> מתקיים<math>\ |A, ולכן יש לה מינימום)| \leq |B|</math> או <math>\ |B| \leq |A|</math>.

תת-קבוצה H של קבוצה סדורה A נקראת '''רישא''', אם היא "סגורה כלפי מטה", כלומר לכל הוכחה: תהי <math>\ a \in AX</math> ולכל משפחת כל הפונקציות <math>\ h \in Hf</math>, אם שתחומן מוכל בקבוצה <math>\ a < hA</math> אז ותמונתן מוכלת בקבוצה <math>\ a \in HB</math> (בפרט, הקבוצה הריקה היא רישא).

'''הערה'''. איחוד משפחה תרגיל: המשפחה <math>X</math> מקיימת את תנאי הלמה של רישות של A הוא רישאצורן עבור קבוצות.

לכל לכן, יש במשפחה <math>\ a\in AX</math> מסמנים איבר מקסימלי <math>\ A_{f<a} = \{x \in /math>. (מבחינת הכלה) מ <math>A\, | \, x < a\}/math> ל <math>B</math>; זוהי תמיד רישא של A. נבחן את האפשרויות השונות:

'''טענה'''א. לכל רישא אמיתית H של קבוצה סדורה היטב A קיים תחום הפונקציה <math>\ a \in Af</math> כך ש-<math>\ H = A_{<a}</math>. '''הוכחה'''. הוא הקבוצה <math>\ H^\circ = \{x \in A | H < x\}</math> אינה ריקה משום שבשרשרת, הרישא היחידה שאינה חסומה היא הקבוצה כולה. קח אז <math>f\ a = \min H^\circ</math> (קיים משום ש-colon A סדורה היטב). ברור ש-<math>\ H < ato B</math> ולכן <math>\ H \subseteq A_{<a}</math>. מצד שני לכל <math>\ a' \in A_{<a}</math> מתקיים <math>\ a' < a</math>, ולפי בחירת a פירושו של דבר הוא שפונקציה חד-<math>\ a' \not \in H^{\circ}</math>חד ערכית, כלומר קיים ולכן <math>|A|\ x\in H</math> כך ש-<math>\ a' \leq x</math>, ומכיוון ש-H רישא, <math>\ a' \in Hle |B|</math>.

'''מסקנה'''ב. תהי תמונת הפונקציה <math>f</math> היא הקבוצה <math>B</math> כולה. אז <math>f^{-1}\colon B\to A קבוצה סדורה היטב. יש התאמה </math> היא פונקציה (במובן הרגיל) חד-חד-ערכית ועל, השומרת סדר, בין ולכן <math>|B|\le |A לבין קבוצת הרישות האמיתיות של A. (במלים אחרות, קבוצת הרישות האמיתיות של A, הסדורה ביחס ההכלה, איזומורפית כקבוצה סדורה ל-A)|</math>.

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

'''הלמה של צורן''' לסיכום, בהכרח מתקיים (גרסה חזקהא). תהי X קבוצה סדורה היטב לא ריקה, עם התכונה שלכל תת-קבוצה סדורה היטב (ולא ריקהואז <math>|A|\le |B|</math>) או (ב-X יש חסם מלעיל) (ואז <math>|B|\le |A|</math>). אז יש ב-X איבר מקסימלימ.ש.ל

שאר הסעיף מוקדש ל'''הוכחת הלמהמשפט''' (על-פי Pierre-Yves Gaillard). ההוכחה בדרך השלילה. נניח שאין ל-X איבר מקסימלילכל קבוצה אינסופית A מתקיים <math>\ |A\times A| = |A|</math>.

נסמן ב-<math>\ \Omega</math> את אוסף תת-הקבוצות הסדורות היטב של X'''מסקנה'''. לפי ההנחה, כל אם <math>W\in max\Omega</math> היא חסומה מלעיל. יתרה מזו{|A|, לפי הנחת השלילה אין ב-W איבר מקסימלי של X, ולכן אפילו הקבוצה <math>\ \hat{W} = \{x \in X : W < x|B|\}</math> אינה ריקה (כאןעוצמה אינסופית, "<math>W < x</math>" הוא כתיב מקוצר לטענה "<math>w<x</math> לכל אז <math>\ w|A|\in W</math>"). לפי אקסיומת הבחירה, קיימת פונקציה <math>cdot |B| = \ p : max\Omega \rightarrow X</math>{|A|, המתאימה לכל <math>|B|\ W \in \Omega</math> איבר <math>\ p(W) \in \hat{W}</math>, כלומר לכל W מתקיים <math>\ W < p(W)</math>.

נאמר שתת-קבוצה סדורה היטב W היא '''מדוייקתהוכחה''' אם לכל . נניח ש-<math>|A|\ w\in W</math> מתקיים <math>p(W_{<w}) = wleq |B|</math>. (שימו לב שבכל מקרה האיבר w הוא חסם מלעיל של הרישא לפי ההנחה <math>\ W_{<w}|B|</math>אינסופית, ולכן ''יתכן'' ש-<math>\ p(W_{<w})|B| =w1\cdot |B| \leq |A|\cdot |B| \leq |B| \cdot |B| = |B|</math>). ('''הערה'''. השאלה איזו תת-קבוצה W היא מדוייקת תלויה בפונקציה p, שעצם קיומה תלוי בהנחת השלילה על כך שאין ל-X איברים מקסימליים; משנוכיח שהנחה זו מביאה לסתירה, יתברר שאי-אפשר להגדיר את p, וממילא יתפוגג המושג הזה ויאבד את משמעותו).

נסמן ב-'''מסקנה'''. לכל שתי קבוצות אינסופיות A,B מתקיים <math>\ |A| + |B| = \Omega</math> את קבוצת תת-הקבוצות המדוייקות של X. תהי U האיחוד של כל הקבוצות השייכות ל-<math>max\ {|A|,|B|\Omega}</math>. מטרתנו להוכיח ש-U עצמה היא קבוצה מדוייקת.

'''טענה 1הוכחה'''. לכל <math>\ W,W' \in \Omega</math>, אחת מהן היא רישא של השניה. אכן, תהי Q האיחוד של כל הרישות המשותפות ל-<math>\ W,W'</math>; אז Q רישא משותפת בעצמה. אם נניח ש-<math>|A|\ Q \neq W,W'leq |B|</math>, . אז יש <math>\ a\in W, a'\in W'</math> כך ש- <math>\ Q = W_{<a} = W'_{<a'}</math>, אבל אז <math>\ a = p(Q) = a'</math> מכיוון ש-<math>\ W,W'</math> מדוייקות, ויוצא ש-<math>\ Q \cup \{p(Q)\}</math> גם היא רישא משותפת ל-<math>\ W,W'|B|</math>, בסתירה להגדרה של Q. מכאן ש- <math>\ Q = W</math> או <math>\ Q = W'</math>, וזה מוכיח את טענה 1.  '''מסקנה 2'''. <math>\ \Omega</math> סדורה לינארית. אכן, מכל שני אברים של <math>\ \Omega</math>, אחד הוא רישא של השניאינסופית, ולכן מוכל בו.  '''מסקנה 3'''. <math>|B|\ U</math> היא שרשרת. אכן, לכל <math>\ a,a' \in U</math> יש <math>\ W,W' \in \Omega</math> כך ש-<math>\ a\in W, a' \in W'</math>; ולפי מסקנה 2 אפשר להניח <math>\ W \subseteq W'</math> (או להיפך) ואז <math>\ a,a' \in W'</math>, והרי <math>\ W'</math> שרשרת. '''טענה 4'''. כל <math>\ W \in\Omega</math> הוא רישא של U. אכן, <math>\ W \subseteq U</math> לפי ההגדרה של U כאיחוד הקבוצות השייכות ל-<math>\ \Omega</math>, ולפי טענה 1, W היא רישא של U. '''טענה 5'''. U סדורה היטב. תהי leq |A תת-קבוצה לא ריקה של U, אז יש <math>\ W \in \Omega</math> החותכת את A באופן לא ריק, ומכיוון ש-W סדורה היטב, יש לחיתוך <math>\ A \cap W\neq \emptyset</math> איבר מינימלי, m. נראה ש-m הוא המינימום של A כולה. יהי <math>\ a \in A</math>. לפי מסקנה 3, a בר-השוואה עם m. אם <math>\ a < m</math> נקבל מטענה 4 ש-<math>\ a \in W</math> בסתירה למינימליות של m. לכן <math>\ m | + |B| \leq a</math>, כפי שרצינו. '''טענה 6'''. <math>\ U \in \Omega</math>. עלינו להראות ש-U מדוייקת, ולאור טענה 5, די להראות שלכל <math>\ u \in U</math> מתקיים <math>\ p(U_{<u}) = u</math>. אבל לפי הגדרת U, יש <math>\ W \in \Omega</math> כך ש-<math>\ u \in W</math>, ואז <math>\ U_{<u} \subset W</math> והטענה נובעת מכך ש-W מדוייקת. מכיוון ש-U סדורה היטב, יש איבר <math>\ p(U) \in X</math>. כצעד אחרון בהוכחה, נראה שגם <math>\ \bar{U} 2 |B| = U\cupmax\{p(U)\} \in \Omega</math>. ברור ש-<math>\ \bar{U}</math> היא שרשרת. אם <math>\ u \in \bar{U}</math>2, יש שתי אפשרויות: אם <math>|B|\ u = p(U)</math> אז <math>\ \bar{U}_{<u} = U|B|</math> וממילא <math>\ p(U) = u</math>; ואחרת <math>\ p(\bar{U}_{<u}) = p(U_{<u}) = u</math> לפי טענה 6. אבל מהגדרת U נובע עכשיו ש-<math>\ \bar{U} \subseteq U</math>, וזו סתירה משום שלפי הנחת השלילה <math>\ U < p(U)</math>. == שימושים == ללמה של צורן שימושים רבים בכל תחומי המתמטיקה. נדגים כמה מהם. הקורא מוזמן להתמקד באלו העוסקות בתחומים המוכרים לו, ויכול לדלג ללא חשש.

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

אוסף השרשראות בקבוצה סדורה חלקית, סדור בעצמו על-ידי יחס ההכלה. שרשרת היא '''משפטמקסימלית'''. לכל שתי קבוצות A,B מתקיים <math>\ |A| \leq |B|</math> או <math>\ |B| \leq |A|</math>אם אינה מוכלת באף שרשרת אחרת.

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

'''משפטעקרון המקסימום של האוסדורף'''. לכל בכל קבוצה אינסופית A מתקיים <math>\ |A\times A| = |A|</math>סדורה חלקית יש שרשרת מקסימלית.

'''מסקנההוכחה'''. לכל שתי קבוצות אינסופיות Aלפי הלמה,B מתקיים <math>\ |A|\cdot |B| = \max\{|A|אוסף השרשראות מקיים את תנאי הלמה של צורן,|B|\}</math>ולכן יש בו איבר מקסימלי.

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