בתשובה לעוזי ו., 29/08/03 17:58
 |
|
 |
||
|
||||
 |
סודר הוא קבוצה טרנזיטיבית1 של סודרים. 1 לגבי יחס ההכלה: עם כל איבר (שהוא במקרה קבוצה), היא מכילה את כל האיברים שלו. |
 |
 |
 |
|
|
|
||
|
||||
|
למען האמת הודעתך הקודמת קצת בילבלה אותי אז הלכתי לרפרף במצגת שקישרת אליה במעלה הדיון. הוא מגדיר שם את הסודרים בצורה שהיא בעיני מפוקפקת למדי (שזה בסדר עבור סמינר אבל בכל זאת). בפעם ראשונה הסודרים מוגדרים על ידי פעולות העוקב והגבול - הגדרה בעייתית מכיוון שלא ברור בדיוק מה ההגדרה של "גבול" בהקשר הזה וקשה לדבר על תוצר של פעולה שאינה מוגדרת היטב. בפעם השניה הוא למעשה נותן מודל להגדרת העוקב באמצעות בניה של הסודרים כקבוצות סגורות טרנזיטיבית כפי שתיקנת. גם כאן הגדרת הגבול נשארת עמומה (אם כי ברורה למדי אינטואיטיבית). עוד פעולה שלא אהבתי היא פעולת ה"כמו-מניה" שהוא מבצע על קבוצות סודרים. כפי שכתבת, לא כל קבוצת סודרים היא בהכרח ברת מניה אך הוא משתמש בתהליך בעל אופי של מניה על מנת "לעבור על כולם" אף כי ברור שלא מדובר בתהליך סופי. התהליך הזה הוא אבן בנין מרכזית בכל הטיעון שנבנה לאחר מכן והופך את כולו ללא ברור בעיני. בכל אופן, לענייננו, מי אמר שיש סודר שאינו בר מניה? למעשה (אני משתדל לא להיות פסקני מדי מכיוון שמן הסתם אני מחמיץ משהו) הבנייה הסדרתית של הסודרים מרמזת שכל קבוצת סודרים (שים לב שלא אמרתי "קבוצת הסודרים" כדי להמנע מהכלה עצמית) היא בת מניה. עכשיו תסביר לי (בבקשה) איפה אני טועה לגמרי. |
|
|
|
|
|
|
||
|
||||
|
קל לראות שקיימות *קבוצות* שאינן בנות מניה1. כדי לדעת שיש *סודר* כזה, צריך להוכיח שאפשר לבנות סדר טוב2 על הקבוצות האלה, וזוהי למעשה גרסה חלשה של אקסיומת הבחירה3. מכיוון שאקסיומת הבחירה אינה נובעת משאר האקסיומות של תורת הקבוצות, נדמה לי שאפשר לחיות בשלום עם האפשרות שכל הסודרים4 הם בני מניה. 1 (קבוצת החזקה של הטבעיים, למשל) 2 סדר טוב הוא סדר שעבורו לכל תת-קבוצה לא ריקה יש מינימום. 3 אקסיומת הבחירה שקולה ל"כל קבוצה אפשר לסדר בסדר-טוב". 4 כתבת "כל קבוצת סודרים"; אבל ממילא איחוד של סודרים הוא סודר. |
|
|
|
|
|
|
||
|
||||
|
למה סדר טוב גורר סודר? נראה לי שזה עובד רק אם אתה מגדיר סודר בתור כל קבוצה סגורה טרנזיטיבית, במצגת ההגדרה היתה באמצעות פעולות עוקב וגבול. בהצגה כזו, נראה כאילו כל הזמן יש לך איחוד בן מניה של קבוצות בנות מניה. לגבי אקסיומת הבחירה, היא מתחילה להשמע לי פחות ופחות מתאימה למודלים אינטואיטיבים. סדר טוב על הממשיים נשמע "לא טבעי". |
|
|
|
|
|
|
||
|
||||
|
אולי זו סטיה של האינטואציה שלי, אבל כל דבר שקשור ל"אינסופים" גדולים יותר מאלף-אפס נשמע לי "לא טבעי". מעניין גם, אותי לפחות, לדעת למה אני מתכוון כשאני אומר "לא טבעי". למה אתה מתכוון? |
|
|
|
|
|
|
||
|
||||
|
המספרים הטבעיים, מן הסתם, טבעיים בעיניך. קבוצות של מספרים טבעיים - גם (יש להניח). אלא מה, אי-אפשר למנות את כל הקבוצות של מספרים טבעיים (כלומר, למספר אותן, 1,2,3,..., בלי לפספס אפילו אחת). מכאן שהגודל של קבוצת הקבוצות של מספרים טבעיים הוא "יותר מאלף-אפס". מה לא טבעי כאן? |
|
|
|
|
|
|
||
|
||||
|
ראשית, "סודר" מוגדר כקבוצה טרנזיטיבית שהיא גם סדורה-היטב (לגבי יחס השייכות). מסתבר שכל סודר שייך לאחד משני סוגים: עוקב ("גדול באחד" מן הסודר שקדם לו, כמו כל המספרים הטבעיים), או גבול (איחוד כל הסודרים שקטנים ממנו, כמו למשל omega). כמובן שהסודר הראשון שאינו בן מניה, לא יכול להיות עוקב, ולכן הוא גבולי. אם כך, הוא מהווה איחוד (שאינו בן מניה!) של קבוצות בנות מניה. לא בעיה. לא אנסה לשכנע אותך באינטואיטיביות של אקסיומת הבחירה (מה לסאוונות אפריקאיות ולאקסיומות של תורת הקבוצות?). הסדר הרגיל על הממשיים, כמובן, אינו סדר טוב - ואולי בגלל זה נראה לך מוזר ש*קיים* סדר טוב. |
|
|
|
|
|
|
||
|
||||
|
הכל ברור מלבד ה"מסתבר" בראשית המשפט השני בתגובתך, הרי זו בדיוק שאלתי. לגבי סדר טוב על הממשיים, לא "טענתי" שהוא לא אינטואיטיבי אלא "סיפרתי" שהוא לא כזה בעיני. הסדר הרגיל הוא לא סדר טוב גם על הרציונליים ובכל זאת מאוד משכנע (ונכון) שיש עליהם סדר טוב. אגב, האם מספיק להניח את אקסיומת הבחירה על קבוצות בעוצמה כלשהי או שיש צורך להניח אותה על כל הקבוצות? האם קונסיסטנטי להניח, למשל, שאקסיומת הבחירה מתקיימת לעוצמת הרצף אבל לא לעוצמות גבוהות יותר? |
|
|
|
|
|
|
||
|
||||
|
הטענה היא שכל סודר1 הוא עוקב3 או גבולי4. "Take the following rule on faith": כל שני סודרים אפשר להשוות (אם הם שונים, אחד מהם קטן מהשני).כעת, יהי a סודר, ו- b האיחוד של כל האיברים של a (שכמובן גם הוא סודר). אם a=b, סיימנו. אם b>a אז a הוא איבר של b, ולכן איבר של אחת הקבוצות המשתתפות באיחוד של b, שהן איברי a. זה בלתי אפשרי (כי השייכות היא יחס א-סימטרי). נשאר המקרה b<a. אלא שאז, ניקח b'=b+1 (כפי שהוגדר ב3). אם b'>a אז a שייך ל- b+1, ואז a=b או a<b (וזה בלתי אפשרי). אם b'=a, סיימנו. נשאר המקרה b'<a; אז b (המוגדר כאיחוד אברי a) מכיל את b', ובפרט {b} הוא איבר של b - שוב סתירה לא-סימטריות. 1 אולי הגיע הזמן לתת הגדרה מסודרת: סודר הוא קבוצה שיחס השייכות עליה הוא טרנזיטיבי (כלומר, לכל איבר של הקבוצה, כל האיברים שלו הם איברים שלה2) ו*טוב* (לכל תת-קבוצה לא ריקה יש איבר מינימלי). 2 זו תורת-הקבוצות פמיניסטית. 3 דהיינו, מהצורה b+1 כאשר b הוא סודר. הסודר החדש b+1 מוגדר כאיחוד הקבוצה b עם הקבוצה {b} (שיש לה איבר אחד). מבחינת הסדר, זה כמו להדביק נקודה חדשה בראש הסודר הקודם. 4 שווה לאיחוד כל הסודרים הקטנים ממנו (= שייכים לו). |
|
|
|
|
|
|
||
|
||||
|
את קיום W (אומגה, יעני) מניחים ב"אקסיומת האינסוף". מכאן אפשר להגיע לסודרים מעוצמות גבוהות יותר ע"י אקסיומה נוספת ומספר עובדות בסיסיות: ראשית, איחוד של קבוצת סודרים היא בברור סודר. מכאן נגיע למסקנה ש"אוסף כל הסודרים" או כל אוסף של סודרים אשר -איננו חסום-, לא יכול להיות קבוצה. כעת נניח בשלילה שכל סודר K מעל W הוא מעוצמה א0. אם כך, קיימת פונקציה חח"ע f:K ----> W, ופונקציה זו מגדירה על W סדר טוב מה"טיפוס סדר" של K. אולם אם כך, נוכל כעת להגדיר פונקציה שתחומה (P(WxW (קבוצת החזקה של WxW), כך שתמונתו של איבר היא אפס אם איננו סדר טוב, והסודר המתאים a באם הוא סדר טוב מטיפוס a. בכך יצרנו פונקציה שתחומה הוא קבוצה (לפי אקסיומת החזקה), והטווח שלה הוא מחלקת כל הסודרים פחות W, אשר איננה קבוצה. זה בלתי אפשרי לפי "אקסיומת ההחלפה". עד כמה שאני מבין עוזי מדייק - הרבה מאוד מודלים שמוכיחים טענות אי-תלות בתורת הקבוצות הם בני-מניה לחלוטין. זה נוח מאוד מכיוון שבדר"כ מנסים "להרחיב" מודל בן-מניה כך שיכלול מה שקרוי "קבוצה גנרית", ובכך "לכפות" על ההרחבה הגנרית לקיים תכונות מסוימות. במודל בן-מניה מובטח לנו שקיימת קבוצה גנרית לכל אוסף תנאים מתיישבים, גם מבלי להשתמש בכלים כגון אקסיומת מרטין (אשר מבטיחה לנו קיום קבוצה גנרית לעוצמות גדולות יותר מ א0). במודל בן-מניה, בפרט כל הסודרים והמונים הם בני מניה. |
|
|
|
|
|
|
||
|
||||
|
עוזי אחי (מה לעשות יש לי משפחה גדולה), מה לכהן בבית הקברות: תן לקברן לדבר. משפט (בלי אקסיומת הבחירה, חברים! ובלונים מחלקים רק אחרי ההוכחה): לכל סודר קיים סודר שעוצמתו גדולה יותר. הוכחה: לוקחים את קבוצת כל הסודרים שאיזומורפיים לאיזשהו סדר טוב על הסודר הנתון (לאו דוקא הסדר המקורי שלו). איחוד של קבוצת סודרים הוא סודר. קל לראות שהסודר המתקבל מהאיחוד של הקבוצה הנתונה – עוצמתו גדולה יותר מעוצמת הסודר המקורי. אז חברה, שלא תעיזו לומר שאפשר להניח שכל הסודרים בני מניה, אפילו אם אין חופש בחירה. אגב, הויכוח על קבלת אקסיומת הבחירה למתמטיקה נקבר כבר מזמן. רובם ככולם קיבלו אותה. |
|
|
|
|
|
|
||
|
||||
|
מה זה איזומורפיזם בין סודר לסדר טוב? נגיד ש"הסודר הנתון" הוא אומגה. מהי קבוצת כל הסודרים שאיזומורפיים לסדר המקורי שלו (לדוגמא)? למה איחוד של קבוצת סודרים הוא סודר? למה הסודר המתקבל מהאיחוד של הקבוצה שתיארת הוא מעוצמה גבוהה מהסודר המקורי? | |
|
|
|
|
|
||
|
||||
|
"איזומורפיזם" כאן הוא התאמה חח"ע ועל בין הקבוצות, ששומרת על יחס הסדר. סודרים ש"איזומורפיים לאיזשהו סדר טוב על הסודר הנתון" - ניסוח מוארך ל"איזומורפיים *כקבוצות* לסודר הנתון" (בלי לדרוש שום דבר על הסדר). במלים אחרות, מדובר על קבוצת כל הסודרים מן ה*עוצמה* של הסודר שלנו - ומכיוון שזו קבוצה לא חסומה1, האיחוד שלה גדול מכל אחד מאבריה. (במקרה של אומגה, לוקחים איחוד של כל הסודרים שהם בני מניה; למשל: omega^omega). איחוד של סודרים הוא סודר - לפי ההגדרה (זו קבוצה טרנזיטיבית של סודרים). העוצמה חייבת להיות גבוהה מן העוצמה המקורית, משום שבחרנו לשתף באיחוד את כל הסודרים מן העוצמה המקורית; אילו האיחוד היה כזה, הוא היה משתתף באיחוד ולכן קטן מעצמו. סיכום: בניגוד להצעתי בתגובה 167089, ד"ר טי מציין שאין צורך להניח את הקיום של אותם סודרים מראש - האיחוד של כל הסודרים מעוצמה א_0 הוא בעל עוצמה א_1, וכו'. 1 מדובר על עוצמה לא סופית, ויחד עם כל סודר a נמצא שם גם a+1. |
|
|
|
|
|
|
||
|
||||
|
טריוויאלי. אבל ברור (או שלא?) שבניה כזו לא יכולה לספק סודר בכל עוצמה שהיא מכיוון שסודר מגדיר סדר טוב ואם קיים סדר טוב על קבוצה בכל עוצמה אז אקסיומת הבחירה מתקיימת. | |
|
|
|
|
|
||
|
||||
|
הבניה הזו מייצרת סודרים מכל העוצמות; (למעשה "עוצמה" היא מקרה פרטי של סודרים). לו היית יודע שכל קבוצה שקולה לאחד המונים, זה היה מוכיח את אקסיומת הבחירה. אלא שזה בכלל לא ברור - הטענה "אם A ו- B קבוצות, אז הן שקולות, או שאחת מהן שקולה לתת-קבוצה של השניה" שקולה בעצמה לאקסיומת הבחירה. | |
|
|
|
|
|
||
|
||||
|
מאיפה הגיעו הנה מונים פתאום? אתה אומר שלא לכל קבוצה יש עוצמה? עד כמה שאני מבין, עוצמה היא למעשה סוג של סדר המוגדר על ידי פונקציות על (נניח). כלומר אם יש פונקציה מ- A על B, נאמר שעוצמת A גדולה שווה לעוצמת B. לא ככה? למה צריך מונים עבור ההגדרה הזו? אתה רוצה לומר שהטענה "קיימת פונקציה מ- A על B או שקיימת פונקציה מ- B על A" שקולה לאקסיומת הבחירה? |
|
|
|
|
|
|
||
|
||||
|
אתה למעשה כותב בדיוק על הבעיה. לכאורה, ההגדרה של "עוצמה" של קבוצה כפי שלומדים אותה בקורס מבוא של מתמטיקה בדידה נראית משונה מאוד. אתה יכול לנסות להשוות בין עוצמות, אבל אתה לא ממש יכול להגדיר מה זו ה"עוצמה" הזו שאתה משווה כל הזמן. המונה א0 (או אומגה) הוא -הקבוצה- בהא הידיעה לה אנו קוראים "העוצמה" א0. כנ"ל לגבי הסודר (והמונה) המכונה א1. ואכן, ללא אקסיומת הבחירה אי אפשר להראות שיש פונקציה מ A על B או להפך. ההוכחה משתמשת בלמה של צורן. |
|
|
|
|
|
|
||
|
||||
|
חברים, רק הראיתי שלכל עוצמה יש עוצמה גדולה ממנה (בלי להניח את אקסיומת הבחירה). אבל זה *לא* אומר שבדרך הזאת אפשר לקבל את כל המונים/עוצמות!!! זהירות, אחיי. |
|
|
|
|
|
|
||
|
||||
|
בהנחה שמדובר על אינדוקציה טרנס-פיניטית, זה לא בדיוק מניה. אם תכונה עוברת לסודר עוקב ולגבול של סודרים, אז קל לראות שהיא נכונה לכל הסודרים - פשוט מחפשים את הראשון בו היא נכשלת. | |
|
|
|
|
|
||
|
||||
|
לא, אין לי משהו קונסטרוקטיבי לתרום, רק שתגובתך הזכירה לי נשכחות- פעם, בעודי באוניברסיטה, הגיע אלי נפעם ידידי מ.א. משעור בתורת הקבוצות ( אאלט) והצהיר " מי שלא למד אינדוקציה טרנס פיניטית הוא לא בן תרבות!". אני מנצל את ההזדמנות לשאול כאן האם מישהו יוכל לסכם בקצרה ובמינוחים יחסית פשוטים מה זה אינדוקציה טרנס פיניטית? |
|
|
|
|
|
|
||
|
||||
|
אם לא היו שינויים דרסטיים בתורת הקבוצות בזמן האחרון, אז זה בדיוק מה שהזכרתי למעלה - סתם הרחבה של עיקרון האינדוקציה הרגיל. אם לתכונה כלשהיא P ידוע שאם היא נכונה לכל איבריו של סודר K היא נכונה גם ל K עצמו, אז תכונה P נכונה לכל הסודרים. | |
|
|
|
|
|
||
|
||||
|
אפשר <לקבל> דוגמה פשוטה? | |
|
|
|
|
|
||
|
||||
|
למשל אפשר להראות באינדוקציה טרנס פיניטית שלכל מונה K מתקיים האי-שוויון אK <= K : 1. לגבי א0 או א1 זה ברור. 2. נניח שזה נכון ל אK, אז ברור שעוצמת K ו K+1 זהה, אולם זו של א(K+1) היא גדולה יותר משל אK, וממילא משל K+1. 3. נניח B סודר גבולי, ובשלילה אB קטן ממש מ B, ולכן מהווה איבר ב B. ניקח אחד מעליו ב B, למשל סודר A. כעת לפי הנחת אינדוקציה אA <= A ובפרט אA > אB , אולם זה לא ייתכן משום ש B > A (בעיקרון יש להראות גם נכונות עובדה זו). |
|
|
|
|
|
|
||
|
||||
|
טוב, למרות שרפרפתי על הדיון הקודם לא ממש הבנתי. נדמה לי ש1 ו2 זה מספיק, לא? זכור- אני לא "בן תרבות". |
|
|
|
|
|
|
||
|
||||
|
לא בדיוק, משום שלסודר כלשהוא לא בהכרח יש אחד "לפניו", ולכן אינדוקציה רגילה לא "תגיע" אל הסודר הזה (שנקרא גבולי. אחרת, אפשר למשל להוכיח שכל הסודרים הם מעוצמה סופית: 1 מעוצמה סופית, ואם K מעוצמה סופית בוודאי ש K+1 הוא מעוצמה סופית. | |
|
|
|
|
|
||
|
||||
|
אבל במשפט דיברת על מונים ולא על סודרים? | |
|
|
|
|
|
||
|
||||
|
גם וגם. לכל סודר K יש גם מונה אK (ולהפך, אבל זה לא משנה כאן). | |
|
|
|
|
|
||
|
||||
|
יותר טוב. אני מתחיל להבין, תודה על המאמץ. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |