שאלה בתורת הקבוצות

[גרעאפס]

שאלה בתורת הקבוצות

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

 

[Deathatred]

ניסיון לעזרה

חלק את N לשתי קבוצות זרות אך ממצות (למשל הקבוצה 1 והקבוצה כל השאר וכו). נסה להוכיח שמספר החלוקות הנ"ל הוא לפחות

card(P(N))​

 

[גרעאפס]

אני מנסה

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

 

[yontanbn]

את זה אפשר לתקן

אם אתה מתאים באופן חח"ע מכל *שני איברים* בקבוצת הקבוצות החלקיות לחלוקה, זה מספיק לך... אינטואטיבית, אפשר לומר ש(2 בחזקת אלף_אפס) חלקי 2 זה עדיין 2 בחזקת אלף_אפס ופורמלית, אתה באמת יכול להגדיר קבוצה כזאת, שנקרא לה A נגיד, כך שכל איבר בA הוא זוג לא-סדור (קבוצה בת שני איברים) של איברים מקבוצת הקבוצות החלקיות, כך שאיבר אחד משלים לאיבר השני אז A נראית ככה: אחד האיברים בה מכיל את הקבוצה הריקה ואת הקבוצה כולה (N) אחד האיברים בה מכיל את הקבוצה {2,17} ואת הקבוצה {כל המספרים הטבעיים שאינם 2 או 17} וכו´ וכו´. קל להראות שעוצמת הקבוצה הזאת היא גם 2 בחזקת אלף_אפס (אפשר להשתמש בזה ש 2R שקול לR (כאשר R קבוצת הממשיים) או בכל מיני דרכים מעניינות אחרות ואז סיימת, כי מהקבוצה הזאת יש לך התאמה חח"ע לחלוקות. אני לא יודע איזה פתרון עדיף, זה או של מנהל הפורום היקר שלנו, כי שלו יותר קצר, אבל טריקי, ואני לא אוהב פתרונות טריקיים בתורת הקבוצות, שלי יותר ארוך, אבל במקום להשתמש בטריק, הוא "מסביר" למה זה לא משנה שמתאימה לך חלוקה אחת לשתי קבוצות חלקיות. אתה תבחר

 

[Halfbaked]

פתרון

לקבוצה P חלקית ל-N, נתאים את יחס השקילות # המוגדר על ידי: x#y אם אחד מהתנאים הבאים מתקיים: 1. (1-x) ו-(1-y) שניהם ב-P 2. (x-1) ו-(y-1) שניהם אינם ב-P 3. x=0 ו-(1-y) אינו ב-P 4. y=0 ו-(x-1) אינו ב-P 5. x=0 ו-y=0 נשמע מסובך, אך זה בעצם פשוט - הגדר את הקבוצה Q המכילה את כל העוקבים של המספרים ב-P. התאם את P ליחס השקילות שמחלקותיו הן Q ו-N-Q. קל לראות שזוהי התאמה חד-חד ערכית בין קבוצת החזקה של P לבין קבוצת יחסי השקילות בעלי שתי מחלקות. ואם לא קל, אסביר זאת בפרוט.

 

[גרעאפס]

אני חושב שהבנתי.

ז´תומרת, עשית בדרך מתוחכמת שהאיבר 0 תמיד יהיה במחלקה של האיברים שלא קיימים בקבוצה, כך שלתת קבוצה ולמשלים שלה לא תתאים אותה השקילות. כן?

 

[Halfbaked]

בדיוק!

למעשה יחס שקילות בעל שתי מחלקות מאופיין באופן חד-חד ערכי על ידי ציון האיברים שאינם שקולים ל-0 (או שאינם שקולים ל-13, או ששקולים ל-254, וכו´). בפתרון שהבאתי מידע זה מקודד על ידי P, בכך שכל איבר ב-P "אומר" שהעוקב שלו לא שקול לאפס.