עוצמות של קבוצות

[ohad]

בקשו להוכיח שוויון עוצמות בין הקבוצות:

[jstex]\mathcal{P}(\mathbb{N})\sim\mathbb{N}\times\mathcal{P}(\mathbb{N})\sim\mathcal{P}(\mathbb{N})^{\mathbb{N}}[/jstex]

 

קל להוכיח (בניית פונקציות חח"ע די פשוטות) כי:

[jstex]\mathcal{P}(\mathbb{N})\preceq\mathbb{N}\times\mathcal{P}(\mathbb{N})\preceq\mathcal{P}(\mathbb{N})^{\mathbb{N}}[/jstex]

 

איך אני מוכיח את השוויון בין הראשונה לאחרונה? (שיגרור בסנדוויץ' את האמצעית)

יש כאן איזה פונקצייה חח"ע שאני מפספס או שצריך ללכת על משהו אחר?

 

בנוסף (ואולי איכשהו זה קשור):

נתקלתי בהתייחסות ל [jstex]\{0,1\}^\mathbb{N}[/jstex] כקבוצת הווקטורים הבינאריים האינסופיים, למה? זה לא סימון לקבוצת כל הפונקציות מ {0,1} ל N?

 

תודה!

 

(אגב, מישהו יודע למה בתצוגה מקדימה ה latex לא מוצג כמו שצריך?)

[incog]

הפוך, הסימון הוא של כל הפונקציות מ-N ל- {0,1} (אפשר לראות פונקציה כזו כווקטור בינארי אינסופי, לכן זה באמת שקול).

 

לגבי שאלתך, מאוד קל לראות את זה על ידי חשבון עוצמות מתקיים:

[jstex]$|P(\mathbb{N})^{\mathbb{N}}|=(2^{\aleph_{0}})^{\aleph_{0}}=2^{\aleph_{0}\times\aleph_{0}}=2^{\aleph_{0}}=|P(\mathbb{N})|$[/jstex]

[ohad]

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

נקווה שלא יבדקו את השאלה שזה היה משמעותי בה, מזל שהרוב הוא ממילא [jstex]\mathbb{N^N}[/jstex]

 

לצערי אסור להשתמש בחשבון עוצמות.

 

כרגיל תודה!

[incog]

אז מה שצריך זה לשחזר את ההוכחה.

P(N)  d שקול לפונקציות מ-N ל- {0,1}

ו- P(N)^N שקול לפונקציות מ-N ל-(פונקציות מ-N ל- {0,1} (זה כמעט מיידי מההגדרה).

זה שקול לפונקציות מ-NXN ל- {0,1}

וזה שקול לפונקציות מ- N ל- {0,1} כמו שצריך להוכיח.

 

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

[ohad]

אנסה לבנות את זה מחר, תודה בינתיים :hat: