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

[ohad]

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

\mathcal{P}(\mathbb{N})\sim\mathbb{N}\times\mathcal{P}(\mathbb{N})\sim\mathcal{P}(\mathbb{N})^{\mathbb{N}}

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

\mathcal{P}(\mathbb{N})\preceq\mathbb{N}\times\mathcal{P}(\mathbb{N})\preceq\mathcal{P}(\mathbb{N})^{\mathbb{N}}

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

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

\{0,1\}^\mathbb{N}

כקבוצת הווקטורים הבינאריים האינסופיים, למה? זה לא סימון לקבוצת כל הפונקציות מ {0,1} ל N?

תודה!

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

[incog]

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

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

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

[ohad]

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

\mathbb{N^N}

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

כרגיל תודה!

[incog]

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

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

[ohad]

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