תורת הקבוצות/הלמה של צורן: הבדלים בין גרסאות בדף

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה
שורה 19: שורה 19:


כשהוכחנו שהפונקציה מוגדרת, הוכחנו גם כי היא שומרת סדר, ובפרט חד-חד-ערכית (כי אם <math>x\not=y</math>, אז או <math>x<y</math>, ואז <math>h(x)\prec h(y)\Rightarrow h(x)\not= h(y)</math>, או ש<math>y<x</math>, ואז <math>h(y)\prec h(x)\Rightarrow h(x)\not=h(y)</math>). נגדיר על הקבוצה <math>A</math> את הטענה <math>\phi(x,y)\equiv((\exist\alpha(h(\alpha)=x)\Rightarrow y=x)\land(\lnot\exist\alpha(h(\alpha)=x)\Rightarrow y=p))</math>. מ[[תורת הקבוצות/תורת הקבוצות האקסיומטית#אקסיומת ההחלפה|אקסיומת ההחלפה]] נובע כי קיימת תמונת הטענה, אותה נסמן <math>\text{Im}(h)</math>. קל לראות שלכל <math>x\in\text{Im}(h)</math> קיים סודר <math>\alpha</math> כך ש<math>h(\alpha)=x</math>, ומכך ש<math>h</math> חד חד ערכית נובע ש<math>\alpha</math> באופן יחיד. לכן הגדרת הטענה <math>\varphi(x,\alpha)\equiv(h(\alpha)=x)</math> על הקבוצה <math>\text{Im}(h)</math> תגרור, באמצעות אקסיומת ההחלפה, את קיום תמונת הטענה. כל סודר <math>\alpha</math> הוא בתמונת הטענה, כי מתקיים <math>\varphi(h(\alpha),\alpha)</math>, לכן תמונת הטענה היא מחלקת כל הסודרים <math>\text{On}</math>. מצד שני, מ[[תורת הקבוצות/סודרים#הפרדוקס של בורלי-פורטי|הפרדוקס של בורלי פורטי]] (טרם נכתב) נובע כי <math>\text{On}</math> אינה קבוצה. סתירה.
כשהוכחנו שהפונקציה מוגדרת, הוכחנו גם כי היא שומרת סדר, ובפרט חד-חד-ערכית (כי אם <math>x\not=y</math>, אז או <math>x<y</math>, ואז <math>h(x)\prec h(y)\Rightarrow h(x)\not= h(y)</math>, או ש<math>y<x</math>, ואז <math>h(y)\prec h(x)\Rightarrow h(x)\not=h(y)</math>). נגדיר על הקבוצה <math>A</math> את הטענה <math>\phi(x,y)\equiv((\exist\alpha(h(\alpha)=x)\Rightarrow y=x)\land(\lnot\exist\alpha(h(\alpha)=x)\Rightarrow y=p))</math>. מ[[תורת הקבוצות/תורת הקבוצות האקסיומטית#אקסיומת ההחלפה|אקסיומת ההחלפה]] נובע כי קיימת תמונת הטענה, אותה נסמן <math>\text{Im}(h)</math>. קל לראות שלכל <math>x\in\text{Im}(h)</math> קיים סודר <math>\alpha</math> כך ש<math>h(\alpha)=x</math>, ומכך ש<math>h</math> חד חד ערכית נובע ש<math>\alpha</math> באופן יחיד. לכן הגדרת הטענה <math>\varphi(x,\alpha)\equiv(h(\alpha)=x)</math> על הקבוצה <math>\text{Im}(h)</math> תגרור, באמצעות אקסיומת ההחלפה, את קיום תמונת הטענה. כל סודר <math>\alpha</math> הוא בתמונת הטענה, כי מתקיים <math>\varphi(h(\alpha),\alpha)</math>, לכן תמונת הטענה היא מחלקת כל הסודרים <math>\text{On}</math>. מצד שני, מ[[תורת הקבוצות/סודרים#הפרדוקס של בורלי-פורטי|הפרדוקס של בורלי פורטי]] (טרם נכתב) נובע כי <math>\text{On}</math> אינה קבוצה. סתירה.
==שקילות לאקסיומת הבחירה==
{{בעבודה}}
בהוכחת הלמה עשינו שימוש ב[[תורת הקבוצות/תורת הקבוצות האקסיומטית#אקסיומת הבחירה|אקסיומת הבחירה]]. מתברר שגם המשפט ההפוך נכון, כלומר אם ניקח את מערכת אקסיומות ZF (שהיא ZFC ללא אקסיומת הבחירה) ונוסיף לה את הלמה של צורן כאקסיומה, נוכל להוכיח את אקסיומת הבחירה. נראה זאת:

נניח כי הלמה של צורן נכונה כאקסיומה. תהי <math>E</math> קבוצה של קבוצות לא ריקות, ונסמן את איחוד איבריה בקצרה <math>\cup E</math>. נסמן ב<math>S</math> את קבוצת הפונקציות <math>f:D\to \cup E</math> כך ש<math>D\subseteq\mathcal P(\cup E)\setminus\{\empty\}</math>, וכן <math>f(x)\in x</math> לכל <math>x\in D</math>. נגדיר יחס סדר על <math>S</math> באופן הבא: <math>f_1\le f_2</math> אם ורק אם <math>f_1=f_2|_{D}</math> כאשר <math>D</math> היא התחום של <math>f_1</math>, והפונקציה <math>f_1|_D</math> מוגדרת על פי [[תורת הקבוצות/פונקציות#צמצום|צמצום של פונקציה]].

גרסה מ־15:13, 30 ביוני 2021

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

ניסוח

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

הגדרה: שרשרת

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

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

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

הוכחה

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

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

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

  • לכל גבולי.

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

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

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

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


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

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