שינויים
/* תרגיל (ממבחן) */
==אריתמטיקה של עוצמות==
'''הגדרה''' יהיו A,B קבוצות אזי <math>A^B:=\{f:B\rightarrow A\}</math>.
===תרגיל===יהיו A,B,C קבוצות כך ש <math>|A|\leq |B|</math>. הוכיחו כי <math>|A^C|\leq|B^C|</math>. פתרון: נתון שקיימת <math>f:A\to B</math> חח"ע. נגדיר <math>g:A^C\to B^C</math> ע"י <math>h:C\to A\mapsto f\circ h</math>. מתקיים כי g חח"ע כי f חח"ע ויש לה הפיכה שמאלית. הערה: <math>|A|< |B|</math> '''לא''' גורר <math>|A^C|<|B^C|</math>. ===תרגיל===הוכח שעוצמת קבוצת החזקה של A תמיד גדולה מעוצמתה של A '''הוכחה.''' יש התאמה חח"ע ועל <math>g:P(A)\to \{0,1\}^A</math> ע"י <math>\forall B\subseteq A : g(B)=f_B=\chi_B</math> לפי תרגיל קודם <math>|A|<|\{0,1\}^A|=|P(A)|</math> '''הערה: (למי שלמד תורת הקבוצות)''' מסיבה זו אוסף העוצמות אינו קבוצה אלא מחלקה. שכן אם הוא היה קבוצה, הייתה לו עוצמה ===תרגיל===יהיו A,B קבוצות כך ש <math>|B|>1</math>. הוכח כי <math>|A|<|B^A|</math>.
'''פתרון.'''
לפי הבנייה <math>\forall a\in A f\not=f_a</math> כיוון ש <math>f(a)\not=f_a(a)</math>. סתירה לכך ש g על.
'''הגדרה:'''
**<math>a^0=1</math> שכן יש פונקציה יחידה מהקבוצה הריקה לכל מקום - היחס שהוא הקבוצה הריקה.
**<math>0^0=1</math> זה מקרה פרטי של הסעיף הקודם, ועדיין מתקיים
**<math>1^a=1</math>
**<math>a\neq 0 \rightarrow 0^a=0</math> אין אף פונקציה מקבוצה לא ריקה אל קבוצה ריקה, שכן יחס כזה לא יכול להיות שלם.
===תכונות האריתמטיקה===
*<math>ab=ba</math>
*<math>(ab)c=a(bc)</math>
*<math>a^ba^c=a^{b+c}</math>
*<math>a^cb^c=(ab)^c</math>
*<math>(a^b)^c=a^{bc}</math>
כלומר מתקיימים חוקי החזקות ה"רגילים"
נוכיח למשל <math>a^ba^c=a^{b+c}</math> יהיו <math>|A|=a,|B|=b,|C|=c</math> קבוצות זרות
נגדיר פונקציה מ <math>A^{B\cup C} \to A^B\times A^C</math> ע"י <math>f \mapsto (f|_B,f|_C)</math>. היא חח"ע ועל.
נוכיח למשל <math>(a^b)^c=a^{bc}</math> יהיו <math>|A|=a,|B|=b,|C|=c</math> קבוצות זרות
נגדיר פונקציה מ <math>(A^B)^C \to A^{B\times C} </math> ע"י <math>f \mapsto g(b,c)= f(c)(b)</math>. היא חח"ע ועל.
בנוסף אם מניחים את אקסיומת הבחירה אזי מתקיים עבור a,b עוצמות כאשר אחד מהם אין סופי
הוכחה <math>2^b\leq a^b\leq (2^a)^b=2^{ab}=2^b</math>
===תרגיל===
הוכח כי <math>\aleph \cdot \aleph=\aleph </math>
:א. מצא את <math>|C|</math>
'''פתרון.'''
א. <math>|C|=(2^a)^a=2^{aa}=2^a</math>
ב.<math>|F\times H|=|F||H|=a2^a(2^a)^{2^a}=2^{a2^a}=2^{2^a}</math>
ג. כל יחס שקילות שקבוצת המנה 2 מתאים לחלוקה של <math>\mathbb{N}</math> ל-2 קבוצות זרות.
ולכן יש התאמה חח"ע ועל <math>\{R:|\mathbb{N}/R|=2\} \leftrightarrow W=\{\{A,A^c\}|A\subseteq \mathbb{N}\}</math> ולכן 2 הקבוצות מאותה עוצמה.
ט: <math>|W|=2^{\aleph_0}</math>
ה: נסמן <math>|W|=a</math>. בנוסף <math>\bigcup_{\{A,A^c\}\in W}\{A,A^c\}=P(\mathbb{N})</math>
ולכן <math>2^{\aleph_0}=|P(\mathbb{N})|=2a=a</math>.
=== תרגיל ===
נגדיר <math>X=\left\{ 0,1\right\} ^{\mathbb{N}}</math> קבוצת כל הסדרות הבינאריות. נגדיר יחס <math>\sim</math> על <math>X</math> כך <math>f\sim g</math> אמ"מ הקבוצה<math>\left\{ n\in\mathbb{N}\mid f(n)\neq g(n)\right\}</math> סופית
הוכיחו כי <math>\sim</math> יח"ש
לכל <math>f\in X</math>, מצאו את העוצמה של <math>[f]</math>.
מצאו את העוצמה של קבוצת המנה.
=== תרגיל ===
תהא <math>X\subseteq P(\mathbb{N})</math>.
מצאו <math>X</math> המקיימת: כל <math>A,B\in X</math> שונות הן זרות (כלומר <math>A\cap B=\emptyset</math>).
ניח <math>X</math> מקיימת: כל <math>A,B\in X</math> שונות הן זרות. הוכיחו כי <math>X</math> בת מנייה.
תהא <math>C\subseteq\mathbb{N}</math>. נניח <math>X</math> מקיימת: החיתוך של <math>A,B\in X</math> שונות הוא <math>C</math> (כלומר <math>A\cap B=C</math>). הוכיחו כי <math>X</math> בת מנייה.
נניח <math>X</math> מקיימת: החיתוך של <math>A,B\in X</math> שונות הוא לכל היותר בן 10 איברים (כלומר <math>\left|A\cap B\right|\leq10</math> ). הוכיחו כי <math>X</math> בת מנייה.רמז: <math>\cup_{B\in I}X_{B}</math> כאשר <math>I=\left\{ B\subseteq\mathbb{N}\mid\left|B\right|=10\right\}</math> ו <math>X_{B}=\left\{ S\in X\mid B\subseteq S\right\}</math>
יהי S יחס על <math>\mathbb{R}^\mathbb{R}</math> (קבוצת כל הפונקציות הממשיות), המוגדר על ידי <math>(f,g)\in S</math> אם"ם לכל <math>x\in\mathbb{R}</math> מתקיים <math>f(x)-g(x)\in\mathbb{Z}</math>
:1. הוכיחו שS ש S הינו יחס שקילות
:2. תהי <math>f\in\mathbb{R}^\mathbb{R}</math> מצאו את <math>|[f]|</math>
2.
נראה כי ל F קיימת הופכית. נגדיר <math>G: \mathbb{Z}^{\mathbb{R}} \to [f]</math>. ע"י <math>G(h):=f-h </math>. הפונקציה מוגדרת היטב כי <math>f-(f-h)\in \mathbb{Z}^{\mathbb{R}}</math> וקל לוודא שזוהי ההופכית חח"ע: נניח <math>SF(g)=SF(h)</math> לכן <math>\forall x\in\mathbb{R} f(x)-g(x)=f(x)-h(x)</math> ולכן h=g, זה מוכיח חח"ע. נוכיח על: תהי h פונקציה כלשהי מהממשיים לשלמים, ברור שf-h במחלקת השקילות של f.
על: תהי h פונקציה כלשהי מהממשיים לשלמים, ברור ש(f-h) במחלקת השקילות של f והיא תהיה המקור.
אם כך, העוצמה של מחלקת השקילות זהה לעוצמה של אוסף הפונקציות מהממשיים לשלמים והוא <math>{\aleph_0}^\aleph</math>. לפי התכונות שלמדנו לעיל מתקיים <math>2^\aleph\leq{\aleph_0}^\aleph\leq 2^\aleph</math> ולכן לפי קנטור מתקיים <math>{\aleph_0}^\aleph=2^\aleph</math>
נזכור בסימון <math>\lfloor x\rfloor</math> שהוא המספר השלם הגדול ביותר הקטן או שווה לx.
נגדיר S F פונקציה השולחת את <math>f\in\mathbb{R}^\mathbb{R}</math> לפונקציה <math>SF(f):=f-\lfloor f\rfloor\in [0,1)^\mathbb{R}</math>. נראה ש-S F מוגדרת היטב בהתחשב ביחס השקילות שלנו, ובנוסף שהפונקציה השולחת מחלקת שקילות ל-S של נציג כלשהו של המחלקה הינה (על קבוצת המנה)וההפעלה שלה על קבוצת המנה תהיה חח"ע ועל. יהיו שתי פונקציות באותה מחלקת שקילות g,f. אזי, <math>S(g)-S(f)=g-\lfloor g\rfloor -f + \lfloor f\rfloor</math>. מכיוון שזהו הפרש של שני מספרים אי שליליים קטנים מאחד, זה שווה למספר אי שלילי קטן מאחד. מכיוון שההפרש בין f ל-g שלם, המספר הזה הוא שלם. המספר השלם האי שלילי היחיד שקטן מאחד הינו אפס. לכן הפונקציה S מוגדרת היטב שכן היא שולחת נציגים שונים של מחלקת שקילות לאותו מקום.
על: ניקח פונקציה כלשהי r מהממשיים לקטע <math>[0,1)</math>. קל לראות ש <math>F[r]=r</math> שכן
<math>\lfloor r \rfloor = 0</math>. לכן r ישמש מקור ולכן F הינה על.
סה"כ קיבלנו שעוצמת קבוצת המנה שווה ל<math>\aleph^\aleph</math> וזה שווה ל<math>2^\aleph</math> לפי התכונות לעיל.
א. תהי A קבוצה אינסופית מעוצמה a.
:1. נגדיר עבור <math>2\leq n\in\mathbb{N}</math> את הקבוצה הבאה: <math>YX=\{(X_1,...,X_n):1<n\in\mathbb{N}\and\Big[\bigcup_i X_i=A\Big] \and \Big[\forall i\neq j: X_i\cap X_j = \emptyset\Big] \and \big[ \forall i X_i \neq \emptyset\big]\}</math>. '''הוכח''' <math>|Y|=2^a</math>
כלומר אוסף החלקות הסופיות הלא טרי' הסדורות של A'''הוכח''' <math>|X|=2^a</math> :2. מצא את <math>|\mathbb{N}\times YX|,|\mathbb{N}\cup YX|</math> וגם את <math>|YX|^{|\mathbb{N}|},|\mathbb{N}|^{|YX|}</math>
:1.
נביט באוסף הפונקציות <math>XY=\{f:A\rightarrow\mathbb{N}\}</math>. נגדיר <math>g:Y\rightarrow X\to Y</math> על ידי לכל <math>x=(X_1,...,X_n)\in X</math> נשלח אותו ל <math>g(yx)=f_x</math> המוגדר<math>\forall a\in A :\; f_x(a)=k</math> אם כאשר <math>a\in X_k</math> בתוך ה-כלומר שולחת איבר לאינדקס של הקבוצה שהוא נמצא בה בחלוקה. נוכיח שהפונקציה מוגדרת וחח"ע. מוגדרת: כיוון ש x הוא חלוקה של A אזי האיבר a יופיע ויופיע בדיוק באחת מהקבוצות. חח"ע: נניח <math>n(X_1,...,X_n)=x\neq x'=(X'_1,...,X'_m)</math>-יה הסדורה y. נוכיח שזו אזי קיים <math>X_i\not=X'_i</math>, לכן קיים יהיה <math>a\in X_i/X'_i</math> (או להיפך) ואז <math>i=f_x(a)\not= f_{x'}(a)</math> כלומר <math>g(x)\not=g(x') </math> דרך 2- נגדיר פונקציה מוגדרת היטב וחח"<math>g:X\to P(A)^{\mathbb{N}}</math> ע"י <math>g((X_1,. ..,X_n))(i) = \begin{cases}X_i & \text{if } 1\leq i \leq n \\ \emptyset & \text{if } n<i \end{cases} </math>
כעת, קל למצוא פונקציה חח"ע מקבוצת החזקה של A ל-Y X - נשלח כל תת קבוצה לזוג שמכיל אותה ואת המשלים שלה.
לכן <math>2^{|A|} \leq |YX| \leq |XY| = \aleph_0^{|A|}</math>, ולפי התכונות לעיל שני הקצוות שווים. לכן עוצמת Y X הינה <math>2^a</math>.
:2.
<math>|\mathbb{N}\cup YX|=\aleph_0+2^a=2^a</math>
<math>|\mathbb{N}\times YX|=\aleph_0\cdot 2^a=2^a</math>
<math>|YX|^{|\mathbb{N}|}=(2^a)^{\aleph_0}=2^{a\cdot \aleph_0}=2^a</math>
<math>|\mathbb{N}|^{|YX|}=(\aleph_0)^{2^a}=2^{2^a}</math>
ב.
בעצם אנו רוצים לחשב איחוד בן מנייה של קבוצות מעוצמת <math>\aleph</math>. לכל עותק של <math>\aleph</math> נתאים <math>A_n</math> קיימת פונקציה ופונקציה חח"ע ועל <math>g_nf_n:\mathbb{R}\rightarrow A_n</math>. לכן סה"כ נבנה כעת נגדיר פונקציה <math>fg:\mathbb{N}\times\mathbb{R}\rightarrow\bigcup_{n\in\mathbb{N}}A_n</math> המוגדרת על ידי ע"י <math>fg(k,x)=g_kf_k(x)</math>. מכיוון שהקבוצות זרות ו<math>g_kf_k</math> חח"ע ברור שf שg חח"ע. מכיוון ש<math>g_kf_k</math> על גם f g על ולכן סה"כ עוצמת הסכום הינה <math>\aleph_0\cdot\aleph=\aleph</math>