עוצמות של קבוצות אינסופיות - דחוף

nir9696

New member
עוצמות של קבוצות אינסופיות - דחוף

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

אני ממש צריך עזרה!

זה ממש חשוב לי.

תודה לעונים! :)
 

אורי769

New member
הבהרה

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

nir9696

New member
אתה צודק, הייתי צריך להבהיר

בסעיף א' הראשון, כותבים "להיעזר באוסף תרגילים פתורים"... בשאלה שם מוכיחים כי קבוצת כל הסדרות הסופיות ב-N היא בת מניה. ובמקרה זה הבנתי למה (כי לסדרה בת איבר אחד יש N אפשרויות, לסדרה בת שני איברים NXN אפשרויות, 3 איברים NXNXN אפשרויות, וכך הלאה. כל אחת מהסדרות היא בת מניה, ואנו צריכים למצוא את האיחוד, לכן מדובר באיחוד בר מניה של קבוצות בנות מניה). אך לא הצלחתי לחשוב איך לעשות זאת עם קבוצות (צירופים).

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

nir9696

New member
באופן עקרוני

אני יכול להתאים לה את הסדרה {2,6,9}, כי קבוצת תתי הקבוצות הסופיות מוכלת בקבוצת הסדרות הסופיות.
האם זה אומר שבגלל שקבוצת תתי הקבוצות הסופיות היא אינסופית ומוכלת בקבוצת הסדרות הסופיות, אז גם העוצמה שלה היא א0 (כי א0 היא העוצמה האינסופית הקטנה ביותר)?
 

אורי769

New member
פחות או יותר

ראשית, עניין קטן פורמאלי של נוטציה: {2,6,9} זה סימון לקבוצה. (2,6,9) זה סימון לסדרה (שלשה סדורה במקרה הזה).
שנית, הטיעון הוא משפט קנטור-שרדר-ברנשטיין. כלומר, למצוא התאמות חח"ע מ-N לקבוצה ומהקבוצה ל-N. במקרה זה, ההתאמה הזו של קבוצה סופית לסדרה, מראה שניתן לשכן את הקבוצה שלנו בקבוצה אחרת שידוע שהיא א0. לכן הקבוצה שלנו היא לכל היותר א0. מאידך קל להראות שהיא לפחות א0.
 

nir9696

New member
אז ניתן ליצור התאמה חח"ע מ-N

לקבוצת תתי הקבוצות הסופיות ע"י כך שמתאימים לכל מספר טבעי n את תת הקבוצה הסופית המכילה את האיברים 0 עד n?
כלומר: f(n) = An כאשר An = x in N, 0<=x<=n
 

nir9696

New member
יופי! רק

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

לגבי סעיף ב' הראשון, יש לי אולי כיוון: אפשר להתייחס לקבוצת הקבוצות הקו-סופיות ב-N כאל קבוצת המשלימות הסופיות שלהן, ואז לפי סעיף א', הראינו שעוצמתן היא א0... זה כיוון נכון? אם כן- איך אני מנסח את התשובה?

לגבי סעיף א' השני - אני מתקשה להוכיח...
 

אורי769

New member
תשובה

בתור מתמטיקאי הדאגה שלך במקום. כלומר, הבחנת כאן בנקודה עדינה וטוב שכך. בא נרשום את זה בשפה ברורה:
משפט קש"ב:
אם A,B קבוצות וקיימות העתקות f: A --> B ו- g:B --> A שהן חח"ע, אז A ~ B.

לעומת זאת אנו עשינו כך:
אם נתונות קבוצות A1,A2,B וידוע ש-A1 ~ A2 וכן קיימות העתקות f:A1 --> B ו-g:B --> A2 שהן חח"ע, אז A1 ~ B.

הטענה האחרונה היא נכונה והיא הרחבה פשוטה של משפט קש"ב. נסה להוכיח אותה.

הכיוון שלך ל-ב' הוא נכון. איך מנסחים תשובה? בצורה מסודרת :) צריך לרשום במסודר מה צריך להוכיח - כלומר להוכיח קיומה של העתקה חח"ע ועל בין הקבוצה של הקו-סופיות לבין הטבעיים ואז להוכיח זאת.
 

nir9696

New member
אני חושב

שלגבי ההרחבה של משפט הקש"ב, זה עניין פשוט של הצבה: אם g:B --> A2 חח"ע אז העוצמה של B קטנה שווה מהעוצמה של A2, ומשום שהעוצמה של A2 שווה לעוצמה של A1, אז נציב, והרי לנו שהעוצמה של B קטנה שווה מהעוצמה של A1. כמו כן f:A1 --> B חח"ע, אז מצד שני העוצמה של A1 קטנה שווה מהעוצמה של B, ומכאן, לפי קש"ב, A1 ~ B. אני פשוט חושש כבר לעשות פעולות פשוטות בקבוצות אינסופיות ולא לוקח אותן בכלל כמובן מאליו :)

לגבי ההוכחה של ב' הראשון - לא חשבתי על התאמה חח"ע ועל, אלא להתייחס רק אל המשלימות, אשר מהוות את קבוצת כל תתי הקבוצות הסופיות ב-N אשר הוכחנו ב-א' כי היא בת מניה. אני מפספס פה משהו??

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

אורי769

New member
תשובה

הנקודה הבעיתית במה שאתה כותב, זה שזה כתוב לא מדוייק. במתמטיקה, ובפרט בתורת הקבוצות חייבים להיות מדוייקים. יש הגדרות ובעזרתן מוכיחים דברים. הוכחה מסודרת מתחילה מלרשום מה נתון.
ההגדרה של |B| <= |A1| היא שקיימת העתקה חח"ע f: B --> A1. זאת ההגדרה של >= בין עוצמות.
כנ"ל |B| <= |A2| אומר שקיימת העתקה חח"ע g: B --> A2.
ההגדרה של |A2| = |A1| היא שקיימת העתקה חח"ע ועל h: A2 --> A1. זאת ההגדרה של = בין עוצמות. (חשוב להבין שזה שהשתמשו כאן בסימן השוויון המוכר לך מעולם המספרים לא אומר שאתה יכול בהכרח לעשות כל דבר שאתה עושה עם מספרים. מה זה אומר "להציב"?)

עכשיו מה צריך להוכיח? צריך להוכיח ש |B| = |A1|.
איך מוכיחים? אפשר לפי הגדרה - כלומר למצוא פונקציה חח"ע ועל בין שתי הקבוצות. אבל במקרה זה נוכיח בעזרת משפט קש"ב. כדי להשתמש במשפט, צריך שתנאי המשפט ייתקיימו. כלומר צריך פונקציות חח"ע בשני הכיוונים. בכיוון אחד כבר קיימת הפונקציה f : B --> A1. צריך למצוא פונקציה k : A1 --> B. אז מה היא k?


בסעיף ב' זה אותו סיפור - אתה צריך להוכיח בצורה מדוייקת. לא הבנתי מה כוונתך ב"רק להתייחס". יש לך קבוצה - קבוצת כל תתי הקבוצות הקו-סופיות ב-N. אתה רוצה להוכיח שעוצמתה א0. מה אתה עושה? אחת האפשרויות זה לבנות העתקה חח"ע ועל בינה לבין קבוצה שכבר ידוע שהיא א0.


אתה צודק שהקבוצות אינן מוכלות בסדרות. אלה יישויות שונות בהגדרה.שים לב שמה שאתה צריך זה העתקה חח"ע מהקבוצות לסדרות. סיכמנו שאת {2,6,9} לדוגמא, אתה שולח לסדרה (2,6,9). זה שיש עוד דרכים לסדר את המספרים האלה זה נכון. אבל זה לא מונע מההעתקה הזו להיות חח"ע.
 

nir9696

New member
התייחסות

לגבי העניין הראשון עם משפט קש"ב - באמת חששתי שאני לא יכול "להציב" סתם. אז בעצם, משום שהצלחנו להתאים פונקציה חח"ע מ-A2 ל-B (נקרא לה g), ומפני שאנו יודעים כי העוצמה של A1 שווה לעוצמה של A2, כלומר קיים העתק חחע" ועל ביניהן, אז fg היא גם חח"ע (בהתבסס על הידע שלי בפונקציות), כלומר, יש פונקציה חח"ע מ-A1 ל-B [כי f חח"ע ו-g חח"ע].

לגבי סעיף ב' - צודק לחלוטין. אני מתאים פונקציה חח"ע ועל בין כל תת קבוצה קו-סופית ב-N לבין משלימתה, 'f(A) = A, כאשר ברור שלכל 'A מתאימה A יחידה (מהגדרת משלים) [חח"ע], וכן לכל תת הקבוצות הסופיות, קרי 'A, יש מקור A בקבוצת התת קבוצות הקו-ספיות [על]. לכן העוצמה של תת הקבוצות הקו-סופיות ותת הקבוצות הסופיות שווה. הוכחנו בא' כי עוצמת תת הקבוצות הסופיות ב-N היא א0, ולכן עוצמת התת קבוצות הקו-סופיות היא גם א0.

לגבי העניין של סדרות לעומת קבוצות - ברור לי שאני צריך שאת {2,6,9} לדוגמא, אניא שולח לסדרה (2,6,9), אבל אני לא מצליח לכתוב את הפונקציה כנוסחה... חשבתי אולי משהו כזה:
(יכול להיות שאני סתם מסתבך)
n in N >=1
נגדיר את הקבוצה An = {a1,a2,...an} ונגדיר את הסדרה Bn = {b1, b2... bn}
ואז נגדיר את הפונקציה

f(An) = (Bn| ai = bi, 1<=i<=n)
 

אורי769

New member
תשובות

לעניין ההכללה של קש"ב. אני טיפה התבלבלתי בתוגבה הקודמת. בא נרשום שוב מסודר...
לפי נתוני הטענה המרוחבת
קיימת f: A1 --> B חח"ע
קיימת g: B --> A2 חח"א
קיימת h: A2 --> A1 חח"ע ועל

אתה רוצה להוכיח |B| = |A2|, בעזרת קש"ב. כלומר אתה צריך להראות קיומה של העתקה חח"ע בכל כיוון. כיוון אחד בכר נתון (הפונקציה f). נותר להוכיח קיומה של k: A2 --> B שהיא חח"ע. מיהי k?


מה שכתבת על סעיף ב' נכון ומדויק.


לגבי הסדרות - בהנתן קבוצה סופית A בת n איברים, אני טעון שקיימת ויחידה סדרה בת n איברים (a1,...an) המקיימת: ai < a(i+1) וכן ai in A לכל i. או במילים פשוטות, כל קבוצה סופית אפשר לסדר מגדול לקטן באופן יחיד.
 

nir9696

New member
תשובה

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

קיימת f: A1 --> B חח"ע - פונקציה חח"ע מ-N לקבוצת תת הקבוצות הסופיות ב-N
קיימת g: B --> A2 חח"ע - פונקציה חח"ע מקבוצת תת הקבוצות הסופיות ב-N לקבוצת הסדרות הסופיות ב-N
קיימת h: A2 --> A1 חח"ע ועל - פונקציה חח"ע ועל מקבוצת הסדרות הסופיות ב-N ל-N

לפי מה שאני מבין אני צריך להוכיח כי |B| = |A1| בעזרת קש"ב. כלומר אני צריך להראות קיומה של העתקה חח"ע בכל כיוון. כיוון אחד כבר נתון (הפונקציה f). נותר להוכיח קיומה של k: B --> A1 שהיא חח"ע.
שאלת מהי k, בתשובה הקודמת שלי הסברתי שאני חושב ש- k היא בעצם gh (יש הנוהגים לכתוב h(g(b)) q ) [סתם הוספתי את ה-q כדי שיצא מסודר :)]. אני צודק?

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

- לגבי סעיף א' הראשון, אני לא מצליח להוכיח מבלי להסתמך על אריתמטיקה בין עוצמות אינסופיות, שזה קשור רק לסעיף ב'. אני חושב על כך ש- P(N) לאיחוד של:
קבוצת כל התת קבוצות הסופיות ב-N (עוצמה א0)
עם קבוצת כל התת קבוצות הקו-סופיות (עוצמה א0)
עם הקבוצה M (עוצמה אינסופית כלשהי k)

מכיוון שכל הקבוצות הנ"ל זרות זו לזו, ניתן לחבר בין העוצמות שלהן: א0 + א0 + k, שזה שווה כמובן ל-א0 + k, שזה שווה לעוצמה של P(N) = C. ומכיוון שקיים המשפט שלפיו k+א0 = k, אז הרי ש-k שווה ל-C.

זו כבר התשובה לסעיף ב' השני, נדמה לי. את סעיף א' אני לא מצליח להוכיח אחרת...
 

אורי769

New member
יפה

מה שכתבת על ההכללה של משפט קש"ב מדוייק.


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


לגבי השאלה השניה. הפתרון שלך בעזרת חשבון עוצמות הוא מדוייק וניסחת אותו יפה. אני לא יודע מה היתה כוונת מחבר התרגיל, אבל ניתן להוכיח שהקבוצה M של כל תת הקבוצות של N שהן אינסופיות ממש (כינוי שהמצאתי עכשיו לתת קבוצה שהיא אינסופית וגם המשלים שלה אינסופי) היא לא בת מניה באופן ישיר. הרעיון הוא להשתמש בקש"ב ע"י השוואה ל-P(N) q. זה ש- q |M| =< |P(N)| q זה ברור. הכיוון ההפוך הוא מעט טריקי. הרעיון הוא כזה - נסתכל על ההעתקה הלוקחת מספר טבעי n ל-2*n. זה שיכון של N בעצמו. ניתן להרחיב שיכון זה לשיכון של (P(N בעצמו. לדוגמא הקבוצה {1,2,5} תלך לקבוצה {2,4,10} בשיכון הזה. נשים לב שהשיכון הזה שולח כל תת קבוצה ב-N לתת קבוצה אחרת שהמשלים שלה הוא אינסופי. אבל זה לא מספיק, כי אנו רוצים שכל תת קבוצה תלך לתת קבוצה שהיא אינסופית ממש. אז מה עושים? מוסיפים לתמונה של כל קבוצה תת קבוצה אינסופית ממש של האי-זוגיים. לדוגמא את החזקות של 3. לדוגמא הקבוצה {1,2,5} תלך לקבוצה q {2,4,10} U {3^k : k in N} q. משאיר לך להבין את הפתרון הזה ואם אתה רוצה גם לנסח אותו בצורה מדוייקת.
 

nir9696

New member
תודה!!! עוד שאלה קטנה

אתה יכול להסביר מה אומר המינוח "שיכון של N בעצמו"?

הבנתי זאת כך: אתה בתחילה מכפיל כל איבר בתת הקבוצה שב-P(N) m ב-2 (זה השיכון של P(N) בעצמה??), דבר שמבטיח לך שעתה תת הקבוצה תהיה בעלת איברים זוגיים. לאחר מכן אתה מאחד אותה עם קבוצה אינסופית ממש של איברים אי-זוגיים. הדבר מבטיח שתת הקבוצה (סופית או אינסופית) עם האיברים הזוגיים ותת הקבוצה האינסופית ממש עם האיברים האי-זוגיים שהתקבלו בתמונה, הן זרות, ולכן אף פעם לא תהיה לכמה תתי קבוצות שלP(N) q תמונה שווה. כלומר הפונקציה חח"ע.
אם מה שכתבתי נכון - אוכל לדוגמא לקחת פשוט בתור הקבוצה האינסופית ממש את קבוצת המספרים האי-זוגיים ב-N, ולאו דווקא את החזקות של 3?
 

אורי769

New member
תשובה

"שיכון של A ב-B" זו לעתים דרך מקוצרת לומר "פונקציה חח"ע מ-A ל-B". בכל מקום שכתבתי שיכון התכוונתי לכך.

אם במקום החזקות של 3 הייתי לוקח את כל האי-זוגיים, מה היתה התמונה של N כולו (כאיבר ב-(P(N ) ?
 

nir9696

New member
אוקיי

תודה על ההסבר על "השיכון", לא הכרתי את המינוח הזה.

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

אתה בעצם אומר לי שבמקרה שהצעתי, יש לאותה תמונה (N) יותר ממקור אחד? [גם אם הייתי לוקח את N כמקור וגם אם הייתי לוקח את קבוצת הטבעיים הזוגיים]
 

אורי769

New member
לא בדיוק

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