בתשובה לגדי אלכסנדרוביץ', 01/02/07 14:01
 |
|
 |
||
|
||||
 |
למה צריך כאן את אקסיומת הבחירה? הסדר הטוב לא מובן מאליו כשמדובר בקבוצה בת מניה? |  |
 |
 |
|
|
|
||
|
||||
|
אני צריך אותה לא בשביל סדר טוב, אלא כדי לבחור נציג של כל מחלקת שקילות. יש מספר לא בן מניה של מחלקות שקילות, ואין לי מושג איך להציג בחירה מפורשת של נציג לכל מחלקה, או אם אפשר בכלל. | |
|
|
|
|
|
||
|
||||
|
רגע, חשבתי שהבנתי אבל מסתבר שטעיתי. אתם אומרים שיש א1 מחלקות שקילות, נציג לכל מלחקה, ומספר הנציגים הוא א0? ובצד, איך מוכיחים שמס' מחלקות השקילות אינו בן-מניה? | |
|
|
|
|
|
||
|
||||
|
מכיון שעוצמת כל מחלקת שקילות היא א0, ויש 2^א0 איברים בקבוצה, הרי שיש 2^א0 מחלקות שקילות (ו2^א0 נציגים). | |
|
|
|
|
|
||
|
||||
|
לא יודע מי אמר שמספר הנציגים הוא א0, אבל הוא עבד עליך. איך מוכיחים: מספר כל הסידורים האפשריים של כובעים הוא לא בן-מנייה (אלכסון קנטור); כל מחלקת שקילות היא כן בת-מנייה (מנה את הדרכים האפשריות לבצע מספר סופי של שינויים), ולכן מספר המחלקות איננו בן-מנייה. |
|
|
|
|
|
|
||
|
||||
|
סליחה, הבנתי לא נכון את הפתרון של גדי - משום מה חשבתי שבוחרים אדם לייצג כל מחלקת שקילות (אולי הטעה אותי המשפט "יביט על הנציג"), ולשם כך אין מספיק אנשים. תודה על ההוכחה; יש לי הרבה חלודה על גלגלי השיניים האלה, אבל כיף להתאמץ ולסובב אותם בכל זאת. ניסיתי ולא הצלחתי ללכסן קונסטרוקטיבית את מחלקות השקילות של החידה. יש דרך אלגנטית שפספסתי? |
|
|
|
|
|
|
||
|
||||
|
לא רק אותך זה בלבל, גם את ראובן. מה זה "ללכסן קונסטרוקטיבית"? לבחור קונסטרוקטיבית נציג לכל מחלקת שקילות? את זה אני חושש שאי-אפשר לעשות - אקסיומת הבחירה כנראה ממש נחוצה כאן. הפתרון דורש מאיתנו לדמיין שאינסוף אנשים המתכנסים לטכס עצה יכולים גם להכין פתקים עם מספר לא בן-מנייה של סידורים אפשריים מוסכמים. |
|
|
|
|
|
|
||
|
||||
|
לא, ב''ללכסן קונסטרוקטיבית'' כוונתי להוכחה שקבוצת מחלקות השקילות לא בת-מנייה - האם אתה יכול לעשות זאת בדרך ה''קלאסית'' של נניח-בשלילה-שכן-נסדר-בשורה-נבנה-נציג-שלא-שייך. | |
|
|
|
|
|
||
|
||||
|
כן - חלק את האנשים לאינסוף קבוצות בגודל אינסוף A1,A2,A3...(אתה יודע איך...) ותשתמש באלכסון של קנטור: מנה את מחלקות השקילות: M1,M2,M3... (M עבור מחלקה :-) ) תגדיר את סידור הכובעים B הבא לכל מחלקת שקילות,Mx, צבעי הכובעים של האנשים ב-Ax בסידור B הפוכים מאלה שב-Mx. תוצאה: B אינו שקול ל-Mk לכל k טבעי. (לפחות את זה הצלחתי) |
|
|
|
|
|
|
||
|
||||
|
אופס.. צ"ל "צבעי הכובעים... הפוכים מאלה שבנציג כלשהו של Mx" (הופ - אקסיומת הבחירה) | |
|
|
|
|
|
||
|
||||
|
מתברר שרק להודות באייל על הבורות שלי גורם לי לפתור: קודם עם גדי, עכשיו איתך. את מה שאתה כותב ניסיתי, אבל לא הצלחתי לחלק את האינסוף לקבוצות (השלב הראשון שלך, שהנחת שהוא קל; צריך כמובן שהקבוצות תהיינה "זרות מספיק"). עכשיו גיליתי לבד איך. תודה בכל אופן (-: | |
|
|
|
|
|
||
|
||||
|
איך? אני חושב על חלוקה לקבוצות בעזרת ראשוניים (קבוצה אחת של כל האיברים שמספרם הסידורי הוא חזקה של 2; קבוצה אחרת של חזקות של 3, וכן הלאה - ועוד קבוצה של כל אלו שלא נכנסו לאף אחת מהקבוצות הללו) אבל בטח יש משהו יותר פשוט. | |
|
|
|
|
|
||
|
||||
|
אוי, אני חמור. כל הזמן חשבתי מסביב לראשוניים, אבל על חזקות שלהם לא חשבתי. מה שכן חשבתי בסוף הוא טיפה יותר מסובך משלך: הראשון הוא כפולות של 2; השני הוא כפולות של 3 שאינן כפולות של 2; ... ה-N הוא כפולות של המספר הראשוני ה-N שאינן כפולות של שום מספר ראשוני קטן יותר. אגב, אאל"ט אינך צריך את הקבוצה האחרונה שלך (מתי בכלל תשתמש בה?). מה שמעניין הוא ששני הפתרונות שלנו נותנים קבוצות זרות לחלוטין, שזה יותר חזק ממה שנחוץ - אאעל"ט[*] מספיק שלכל שתי קבוצות An, Am יהיו ב-An אינסוף אברים שאין ב-Am. [*]עדיין |
|
|
|
|
|
|
||
|
||||
|
אתה חמור? לעולם אל תכנה את עצמך בכינויים מעליבים. תמיד יימצאו אחרים שיעשו את זה טוב ממך :) | |
|
|
|
|
|
||
|
||||
|
איפה תשים את 6 למשל? ועוד אפשרות: "מנה את הרציונליים החיוביים" (= העתקה חח"ע ועל מהם לשלמים החיוביים. אופס, לא ממש עזרתי נכון?), ותגדיר את הקבוצות כמספרים הסידוריים של כל הרציונליים בין 0 ל-1, בין 1 ל-2, בין 2 ל-3 וכו'. אבל זאת סתם התחכמות, ובטח יש מלא דרכים אחרות יפות. אגב, אולי מישהו סוף סוף יגיד לי מה זה אאל"ט ותטל"א? |
|
|
|
|
|
|
||
|
||||
|
אם אני לא טועה. תשובה טובה לשאלה אחרת. |
|
|
|
|
|
|
||
|
||||
|
בקבוצה הראשונה: כל האי זוגיים. בשניה: האי זוגיים כפול 2. ב-n: האי זוגיים כפול 2 בחזקת (n-1). |
|
|
|
|
|
|
||
|
||||
|
הקבוצה השנייה מכילה את השלישית, לא? | |
|
|
|
|
|
||
|
||||
|
לי יוצא שהן זרות: ...2,6,10,14,18 לעומת ...4,12,20,28 תקן אותי אם אני טועה. (הרעיון: מפרידים את הטבעיים לאי-זוגיים וזוגיים; קבוצת הזוגיים מתאימה לטבעיים כפול 2, אז אפשר לבצע בה הפרדה כמקודם; וחוזר חלילה). |
|
|
|
|
|
|
||
|
||||
|
צודק, התבלבלתי. | |
|
|
|
|
|
||
|
||||
|
את 6 אני אשים בסדרה הראשונה, כפולות של 2. אבל כפי שאמרתי לגדי בנוגע לקבוצת-כל-השאר שלו, אני לא חייב בכלל לשים אותו - אני צריך תתי קבוצות אינסופיות של השלמים, אבל אני לא חייב לכסות את *כל* השלמים; רק במקרה יצא לי כך. גם הדרך שלך לא פחות טובה - ואת ההעתקה מהרציונליים לטבעיים אני דווקא זוכר עדיין, לפחות זה (-: |
|
|
|
|
|
|
||
|
||||
|
גם אני סברתי שיש אדם שמייצג כל מחלקה. אם לא, מהו הנציג המוסכם? | |
|
|
|
|
|
||
|
||||
|
אכן היה עדיף להשתמש בתיאור כמו "סידור כובעים מוסכם". מחלקות השקילות הן של *סידורי כובעים* ששונים זה מזה רק במספר סופי של כובעים - לכן, לכל מחלקת שקילות בוחרים סידור כובעים מסויים מתוכה, ש"ייצג" אותה. אני פשוט כבר רגיל למחלקות שקילות ולכן "נציג" מתורגם אצלי אוטומטית ל"נציג של מחלקת שקילות", ולא לקונוטציות אפשריות אחרות. | |
|
|
|
|
|
||
|
||||
|
עם מחלקות שקילות אין לי בעיה, אבל מה פירוש "סידור כובעים מסוים" מתוך המחלקה? ומי בוחר את הסידור הזה? | |
|
|
|
|
|
||
|
||||
|
זו פשוט ההתאמה של כובע לכל אדם בקבוצה. למשל, סידור אחד הוא זה שבו לכל האנשים כובע שחור, סידור אחר הוא זה שבו לכולם כובע לבן, באחד אחר יש כובע שחור לכל האנשים שמספרם זוגי ולבן לכל אלו שמספרם אי זוגי (אם יש מספר בן מניה של אנשים, אפשר להתאים לכל אחד מספר מזהה שלם חיובי), וכו'. | |
|
|
|
|
|
||
|
||||
|
כל מחלקת שקילות היא בת מניה, אבל אוסף המחלקות אינו כזה! (בפרט, בטקס התיאום והחלפת האינפורמציה שלפני חשיפת הכובעים יש להעביר כמות אינפורמציה שאינה בת מניה, וזה גם צריך להיות גודל הזכרון הנגיש לכל משתתף). | |
|
|
| חזרה לעמוד הראשי |  |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |