הבדלים בין גרסאות בדף "88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 7"

גרסה אחרונה מ־17:46, 5 באוגוסט 2020

אריתמטיקה של עוצמות

הגדרה יהיו A,B קבוצות אזי $A^B:=\{f:B\rightarrow A\}$ .

תרגיל

יהיו A,B,C קבוצות כך ש $|A|\leq |B|$ . הוכיחו כי $|A^C|\leq|B^C|$ .

פתרון: נתון שקיימת $f:A\to B$ חח"ע. נגדיר $g:A^C\to B^C$ ע"י $h:C\to A\mapsto f\circ h$ . מתקיים כי g חח"ע כי f חח"ע ויש לה הפיכה שמאלית.

הערה: $|A|< |B|$ לא גורר $|A^C|<|B^C|$ .

תרגיל

הוכח שעוצמת קבוצת החזקה של A תמיד גדולה מעוצמתה של A

הוכחה. יש התאמה חח"ע ועל $g:P(A)\to \{0,1\}^A$ ע"י $\forall B\subseteq A : g(B)=f_B=\chi_B$

לפי תרגיל קודם $|A|<|\{0,1\}^A|=|P(A)|$

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

תרגיל

יהיו A,B קבוצות כך ש $|B|>1$ . הוכח כי $|A|<|B^A|$ .

פתרון. נבחר 2 איברים שונים $b_0,b_1\in B$ ונגדיר פונקציה חח"ע $g:A\to B^A$ ע"י $g(a)=f_a$ כאשר $f_a(a)=b_1$ ו $\forall a'\not=a :f_a(a')=b_0$ ולכן $|A|\leq|B^A|$ .

נניח בשלילה שקיים שיוויון אזי קיימת התאמה חח"ע ועל $g:A\to B^A$ . נסמן $\forall a\in A:g(a)=f_a$ .

נראה באופן דומה לתירגול קודם כי g איננה על ע"י שנמצא פונקציה f שאין לה מקור:

נבחר 2 איברים שונים $b_0,b_1\in B$ ונגדיר פונקציה באופן הבא $f:A\rightarrow B$ ע"י $f(a)=b_0$ אם $f_a(a)=b_1$ . ו- $f(a)=b_1$ אחרת. לפי הבנייה $\forall a\in A f\not=f_a$ כיוון ש $f(a)\not=f_a(a)$ . סתירה לכך ש g על.

הערה: התרגיל הזה הוא מסקנה מהתרגילים הקודמים כי $|\{0,1\}|\leq |B|$ ולכן $|A|<|\{0,1\}^A|\leq |B^A|$

הגדרה: יהיו שתי קבוצות זרות A,B כך ש $|A|=a, |B|=b$ . אזי נגדיר פעולות בין עוצמות:

$a+b:=|A\cup B|$
$a\cdot b := |A\times B|$
$a^b := |\{f:B\rightarrow A\}|$

דוגמא: ראינו בתירגול קודם את הזיהוי $[0,1)=\{f:\mathbb{N} \to \{0,1,...9\}\}$ לכן $\aleph=|\mathbb{R}|=|[0,1)|=|\{f:\mathbb{N} \to \{0,1,...9\}\}|=10^{\aleph_0}$

הערות:

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

למשל $2+1=|\{1,2\}\cup\{3\}|=3$

שימו לב: מתוך הגדרה זו קל לראות את חוקי החזקות למקרי הקצה:
- $a^0=1$ שכן יש פונקציה יחידה מהקבוצה הריקה לכל מקום - היחס שהוא הקבוצה הריקה.
- $0^0=1$ זה מקרה פרטי של הסעיף הקודם, ועדיין מתקיים
- $1^a=1$
- $a\neq 0 \rightarrow 0^a=0$ אין אף פונקציה מקבוצה לא ריקה אל קבוצה ריקה, שכן יחס כזה לא יכול להיות שלם.

תכונות האריתמטיקה

יהיו a,b,c עוצמות אזי מתקיים

$ab=ba$
$(ab)c=a(bc)$
$a^ba^c=a^{b+c}$
$a^cb^c=(ab)^c$
$(a^b)^c=a^{bc}$

כלומר מתקיימים חוקי החזקות ה"רגילים"

נוכיח למשל $a^ba^c=a^{b+c}$ יהיו $|A|=a,|B|=b,|C|=c$ קבוצות זרות נגדיר פונקציה מ $A^{B\cup C} \to A^B\times A^C$ ע"י $f \mapsto (f|_B,f|_C)$ . היא חח"ע ועל.

נוכיח למשל $(a^b)^c=a^{bc}$ יהיו $|A|=a,|B|=b,|C|=c$ קבוצות זרות נגדיר פונקציה מ $(A^B)^C \to A^{B\times C}$ ע"י $f \mapsto g(b,c)= f(c)(b)$ . היא חח"ע ועל.

בנוסף אם מניחים את אקסיומת הבחירה אזי מתקיים עבור a,b עוצמות כאשר אחד מהם אין סופי

$a+b=max\{a,b\}$
אם שניהם אינם אפס אזי $a\cdot b=max\{a,b\}$
מסקנה: אם $2\leq a \leq b$ אזי $a^b=2^b$

הוכחה $2^b\leq a^b\leq (2^a)^b=2^{ab}=2^b$

תרגיל

הוכח כי $\aleph_0+\aleph=\aleph$

הוכחה: דרך א- ישירות מהגדרה. נבחר $A=[\frac{1}{4},\frac{1}{2}],B=\mathbb{N}$ אזי $\aleph=|A|\leq |A\cup B |\leq |\mathbb {R}|=\aleph$

דרך ב- מהנוסחא. $\aleph_0+\aleph=max\{\aleph_0,\aleph\}=\aleph$

תרגיל

הוכח כי $\aleph \cdot \aleph=\aleph$

הוכחה: $\aleph=|\{f:\mathbb{N}\to \{ 0,1\dots 9 \} \}|=10^{\aleph_0}=2^{\aleph_0}$

דרך א- ישירות מהגדרה. נבחר $A=\{f:\mathbb{N}\to \{0,1\dots 9\}\},B=A\times A$ אזי נגדיר פונקציה $A\to A\times A$ ע"י $f(n)\mapsto (f(2n),f(2n+1))$ . זו פונקציה חח" ועל.

דרך ב- אריתמטיקה- $\aleph \cdot \aleph=2^{\aleph_0}\cdot 2^{\aleph_0}=2^{\aleph_0+\aleph_0}=2^{\aleph_0}=\aleph$

דרך ג- מהנוסחא- $\aleph \cdot \aleph=max\{\aleph,\aleph\}=\aleph$

תרגיל

הוכח כי $|\mathbb{R}\backslash \mathbb{Q}|=\aleph$

פתרון:

כיוון ש $\mathbb{R}\backslash \mathbb{Q}$ מוכל בממשיים עוצמתה לכל היותר אלף. נניח בשלילה כי עוצמתה שווה a קטנה ממש מאלף אזי $\aleph=|\mathbb{R}|=|\mathbb{R}\backslash \mathbb{Q}|+|\mathbb{Q}|=a+\aleph_0=a<\aleph$ . סתירה

תרגיל

חשבו את $\aleph^{\aleph_0},{\aleph_0}^{\aleph}$

פתרון: $\aleph^{\aleph_0}=\aleph,{\aleph_0}^{\aleph}=2^{\aleph}$

הסיקו כי עוצמת קבוצת הפונקציות מהרציונאלים לממשיים היא $\aleph$ .

תרגיל

תהא $A$ קבוצה אינסופית ו $B\subseteq A$ תת קבוצה.

הוכח/הפרך

1. $|A\backslash B|=|A|\Rightarrow |B|<|A|$

2. $|A\backslash B|=|A|\Leftarrow |B|<|A|$

פתרון:

1. הפרכה: ניקח את השלמים והטבעיים

2. נכון כי ניתן להציג A כאיחוד זר $A=A\backslash B \cup B$ ולכן $|A|=|A\backslash B| + |B|$ . אם $|A\backslash B|<|A|$ נקבל סתירה

תרגיל

1. מה עוצמת $\mathbb{N}^\mathbb{N}$

פתרון: $\aleph_0^{\aleph_0} =2^{\aleph_0}$

2. מה עוצמת $X=\{f\in \mathbb{N}^\mathbb{N}:f(1)\leq f(2)\}$

פתרון: לכל היותר $\mathbb{N}^\mathbb{N}$ ולכל הפחות $\mathbb{N}^\mathbb{N}$ כי לכל $g\in \mathbb{N}^{\mathbb{N}\setminus \{1,2\}}$ נתאים $f\in X$ ע"י $f(1)=f(2)=1$ ועבור $x\neq 1,2$ נגדיר $f(x)=g(x)$ ולכן $|\mathbb{N}^{\mathbb{N}\setminus \{1,2\}}|\leq|X|\leq |\mathbb{N}^\mathbb{N}|$ ולפי ק.ש.ב יש שיווון

3. מה עוצמת $X=\{f\in \mathbb{R}^\mathbb{R}:\forall x\notin \mathbb{Q} f(x)=1\}$

פתרון: X שווה עוצמה ל $\mathbb{R}^{\mathbb{Q}}$ כי $g\in\mathbb{R}^{\mathbb{Q}}$ ממופה ל $f\in X$ המוגדרת $f|_{\mathbb{Q}}=g,f|_{\mathbb{R}\setminus\mathbb{Q}}=1$

תרגיל

תהי $\{A_i\}_{i\in I}$ משפחה של קבוצות הזרות זו לזו כך שעוצמת כל אחת מהן ב $a$ . נגדיר $\sum_{i\in I} a = |\bigcup_{i\in I}A_i|$ . הוכח כי $\sum_{i\in I} a = |I|\cdot a$

פתרון:

תהא $A$ קבוצה נוספת מעוצמה $a$ . לכל $i\in I$ קיימת פונקציה חח"ע ועל $f_i:A\rightarrow A_i$ . כעת נגדיר פונקציה $g:I\times A\rightarrow\bigcup_{i\in I}A_i$ ע"י $g(k,x)=f_k(x)$ . מכיוון שהקבוצות זרות ו $f_k$ חח"ע ברור שg חח"ע. מכיוון ש $f_k$ על גם g על ולכן קיבלנו את המבוקש.

תרגיל

נגדיר $F$ להיות אוסף תתי הקבוצות הסופיות של הטבעיים $F=\{X\subseteq \mathbb{N}:|X|<\aleph_0\}$ . מה עוצמתה?

פתרון: לכל $i\in \mathbb{N}$ נגדיר $F_i=\{X\subseteq \mathbb{N}:|X|=i\}$ (אוסף תתי הקבוצות מגודל $i$ ). אזי $|F_i|\leq \aleph_0^i=\aleph_0$ ואז $|F|=|\cup_{i\in \mathbb{N}}F_i|\leq \aleph_0\cdot \aleph_0 =\aleph_0$

תרגיל (בש.ב.)

נגדיר $A$ להיות אוסף תתי הקבוצות האינסופיות של הטבעיים. מה עוצמתה?

פתרון: מתקיים כי $P(\mathbb{N})=A\cup A^c$ כאשר A היא תתי הקבוצות הסופיות מתרגיל קודם שעוצמת $\aleph_0$ ולכן $2^{\aleph_0}=\aleph_0+|A^c|=\max\{\aleph_0,|A^c|\}=|A^c|$

תרגיל

נגדיר $A=\{X\subseteq \mathbb{R}: |X|=\aleph_0 \}$ ,מה עוצמתה?

פתרון: לכל הפחות $2^{\aleph_0}$ כי תתי הקבוצות האינסופיות של הטבעיים מעוצמה זאת. בצד שני נגדיר $F:\mathbb{R}^{\mathbb{N}}\to P(\mathbb{R})$ ע"י $f\mapsto Im(f)$ טענה: $A\subseteq Im(F)$ הוכחה: תהא $X\in A$ ומהגדרת A, נסיק כי X מעוצמה הטבעיים ולכן קיימת $f:\mathbb{N}\to X$ חח"ע ועל ולכן $F(f)=Im(f)=X$ . מסקנה מכך $|A|\leq |Im(F)|\leq |\mathbb{R}^{\mathbb{N}}|=\aleph^{\aleph_0}=\aleph$ . לפי ק.ש.ב $|A|=2^{\aleph_0}=\aleph$

תרגיל

נגדיר $A=\{X\subseteq \mathbb{R}: |X|=\aleph \}$ ,מה עוצמתה?

פתרון: לכל היותר $2^\aleph$ מצד שני $F:P((0,1))\to A$ המוגדרת $B\mapsto B\cup (1,2)$ חח"ע ולפי ק.ש.ב. סימנו

תרגיל ממבחן תשסח מועד א (ד"ר שי סרוסי וד"ר אלי בגנו)

תהי A קבוצה אינסופית. נסמן $a=|A|,\;B=P(A),\;F=A\times P(A),\; C=P(A)^A,\; H=B^B$

א. מצא את

|C|

ב. מצא את

|F\times H|

ג. מצא את

|\{R:|\mathbb{N}/R|=2\}|

המוכלת באוסף יחסי השקילות על הטבעיים.

פתרון. א. $|C|=(2^a)^a=2^{aa}=2^a$

ב. $|F\times H|=|F||H|=a2^a(2^a)^{2^a}=2^{a2^a}=2^{2^a}$

ג. כל יחס שקילות שקבוצת המנה 2 מתאים לחלוקה של $\mathbb{N}$ ל-2 קבוצות זרות. ולכן יש התאמה חח"ע ועל $\{R:|\mathbb{N}/R|=2\} \leftrightarrow W=\{\{A,A^c\}|A\subseteq \mathbb{N}\}$ ולכן 2 הקבוצות מאותה עוצמה.

ט: $|W|=2^{\aleph_0}$

ה: נסמן $|W|=a$ . בנוסף $\bigcup_{\{A,A^c\}\in W}\{A,A^c\}=P(\mathbb{N})$ ולכן $2^{\aleph_0}=|P(\mathbb{N})|=2a=a$ .

תרגיל

נגדיר $X=\left\{ 0,1\right\} ^{\mathbb{N}}$ קבוצת כל הסדרות הבינאריות. נגדיר יחס $\sim$ על $X$ כך $f\sim g$ אמ"מ הקבוצה $\left\{ n\in\mathbb{N}\mid f(n)\neq g(n)\right\}$ סופית

הוכיחו כי $\sim$ יח"ש

לכל $f\in X$ , מצאו את העוצמה של $[f]$ .

מצאו את העוצמה של קבוצת המנה.

תרגיל

תהא $X\subseteq P(\mathbb{N})$ .

מצאו $X$ המקיימת: כל $A,B\in X$ שונות הן זרות (כלומר $A\cap B=\emptyset$ ).

ניח $X$ מקיימת: כל $A,B\in X$ שונות הן זרות. הוכיחו כי $X$ בת מנייה.

תהא $C\subseteq\mathbb{N}$ . נניח $X$ מקיימת: החיתוך של $A,B\in X$ שונות הוא $C$ (כלומר $A\cap B=C$ ). הוכיחו כי $X$ בת מנייה.

נניח $X$ מקיימת: החיתוך של $A,B\in X$ שונות הוא לכל היותר בן 10 איברים (כלומר $\left|A\cap B\right|\leq10$ ). הוכיחו כי $X$ בת מנייה.רמז: $\cup_{B\in I}X_{B}$ כאשר $I=\left\{ B\subseteq\mathbb{N}\mid\left|B\right|=10\right\}$ ו $X_{B}=\left\{ S\in X\mid B\subseteq S\right\}$

תרגיל ממבחן תשע מועד א (ד"ר שי סרוסי וד"ר אפי כהן)

יהי S יחס על $\mathbb{R}^\mathbb{R}$ (קבוצת כל הפונקציות הממשיות), המוגדר על ידי $(f,g)\in S$ אם"ם לכל $x\in\mathbb{R}$ מתקיים $f(x)-g(x)\in\mathbb{Z}$

1. הוכיחו ש S הינו יחס שקילות

2. תהי

f\in\mathbb{R}^\mathbb{R}

מצאו את

|[f]|

3. מצאו את

|\mathbb{R}^\mathbb{R}/S|

פתרון:

1.

רפלקסיביות: $\forall x\in\mathbb{R} f(x)-f(x)=0\in\mathbb{Z}$
סימטריות: $f(x)-g(x)\in\mathbb{Z}$ גורר שגם $g(x)-f(x)\in\mathbb{Z}$ כי יש נגדי לחיבור
טרנזיטיביות: נובעת בקלות מסגירות לחיבור בשלמים: $f-h=f-g+g-h$

2.

עבור $[f]\in \mathbb{R}^\mathbb{R}/S$ נגדיר $F:[f] \to \mathbb{Z}^{\mathbb{R}}$ . ע"י $F(g):=f-g$ נראה כי היא מוגדרת,חח"ע ועל.

מוגדרת: לפי ההגדרה של יחס השקילות אכן מתקיים $f-g\in \mathbb{Z}^{\mathbb{R}}$

נראה כי ל F קיימת הופכית. נגדיר $G: \mathbb{Z}^{\mathbb{R}} \to [f]$ . ע"י $G(h):=f-h$ . הפונקציה מוגדרת היטב כי $f-(f-h)\in \mathbb{Z}^{\mathbb{R}}$ וקל לוודא שזוהי ההופכית

חח"ע: נניח $F(g)=F(h)$ לכן $\forall x\in\mathbb{R} f(x)-g(x)=f(x)-h(x)$ ולכן h=g.

על: תהי h פונקציה כלשהי מהממשיים לשלמים, ברור ש(f-h) במחלקת השקילות של f והיא תהיה המקור.

אם כך, העוצמה של מחלקת השקילות זהה לעוצמה של אוסף הפונקציות מהממשיים לשלמים והוא ${\aleph_0}^\aleph$ . לפי התכונות שלמדנו לעיל מתקיים $2^\aleph\leq{\aleph_0}^\aleph\leq 2^\aleph$ ולכן לפי קנטור מתקיים ${\aleph_0}^\aleph=2^\aleph$

3.

נזכור בסימון $\lfloor x\rfloor$ שהוא המספר השלם הגדול ביותר הקטן או שווה לx.

נגדיר F פונקציה השולחת את $f\in\mathbb{R}^\mathbb{R}$ לפונקציה $F(f):=f-\lfloor f\rfloor\in [0,1)^\mathbb{R}$ . נראה ש-F מוגדרת היטב (על קבוצת המנה)וההפעלה שלה על קבוצת המנה תהיה חח"ע ועל.

מוגדרות: יהיו שתי פונקציות באותה מחלקת שקילות g,f. אזי, $F(g)-F(f)=g-\lfloor g\rfloor -f + \lfloor f\rfloor$ . מכיוון שזהו הפרש של שני מספרים אי שליליים קטנים מאחד, זה שווה למספר שבערכו המוחלט קטן מאחד. מכיוון שההפרש בין f ל-g שלם, המספר הזה הוא שלם. המספר השלם האי שלילי היחיד שקטן מאחד הינו אפס כלומר $F(f)=F(g)$ . לכן הפונקציה F מוגדרת היטב שכן היא שולחת נציגים שונים של מחלקת שקילות לאותו מקום.

חח"ע: נניח $F(f)=F(g)$ אז $f-g=\lfloor f\rfloor - \lfloor g\rfloor$ כיוון ש $\lfloor f\rfloor - \lfloor g\rfloor\in \mathbb{Z}^\mathbb{R}$ אזי הם נציגים של אותה מחלקת שקילות כלומר $[f]=[g]$

על: ניקח פונקציה כלשהי r מהממשיים לקטע $[0,1)$ . קל לראות ש $F[r]=r$ שכן $\lfloor r \rfloor = 0$ . לכן r ישמש מקור ולכן F הינה על.

סה"כ קיבלנו שעוצמת קבוצת המנה שווה ל $\aleph^\aleph$ וזה שווה ל $2^\aleph$ לפי התכונות לעיל.

תרגיל ממבחן תשע מועד ב (ד"ר שי סרוסי וד"ר אפי כהן)

א. תהי A קבוצה אינסופית מעוצמה a.

1. נגדיר עבור :

$X=\{(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]\}$ .

כלומר אוסף החלקות הסופיות הלא טרי' הסדורות של A הוכח $|X|=2^a$

2. מצא את

|\mathbb{N}\times X|,|\mathbb{N}\cup X|

וגם את

|X|^{|\mathbb{N}|},|\mathbb{N}|^{|X|}

ב.תהי $\{A_i\}_{i\in I}$ משפחה של קבוצות הזרות זו לזו. נסמן את עוצמת כל אחת מהן ב $a_i$ בהתאמה. נגדיר $\sum_{i\in I} a_i = |\bigcup_{i\in I}A_i|$ .

חשב את $\sum_{n\in\mathbb{N}}\aleph$

פתרון.

א.

1.

נביט באוסף הפונקציות $Y=\{f:A\rightarrow\mathbb{N}\}$ . נגדיר $g:X\to Y$ על ידי לכל $x=(X_1,...,X_n)\in X$

נשלח אותו ל $g(x)=f_x$ המוגדר $\forall a\in A :\; f_x(a)=k$ כאשר $a\in X_k$ כלומר שולחת איבר לאינדקס של הקבוצה שהוא נמצא בה בחלוקה.

נוכיח שהפונקציה מוגדרת וחח"ע.

מוגדרת: כיוון ש x הוא חלוקה של A אזי האיבר a יופיע ויופיע בדיוק באחת מהקבוצות.

חח"ע: נניח $(X_1,...,X_n)=x\neq x'=(X'_1,...,X'_m)$ . אזי קיים $X_i\not=X'_i$ , לכן קיים יהיה $a\in X_i/X'_i$ (או להיפך) ואז $i=f_x(a)\not= f_{x'}(a)$ כלומר $g(x)\not=g(x')$

דרך 2- נגדיר פונקציה $g:X\to P(A)^{\mathbb{N}}$ ע"י $g((X_1,...,X_n))(i) = \begin{cases}X_i & \text{if } 1\leq i \leq n \\ \emptyset & \text{if } n<i \end{cases}$

קל לראות כי הפונקציה חח"ע ולכן $|X| \leq (2^{a})^{\aleph_0} = 2^{a\cdot \aleph_0} =2^a$

דרך 3- נציג את X כאיחוד זר $X=\cup_{1<n\in \mathbb {N}}Y_n$ כאשר $Y_n$ זה חלוקות סדורות של A עם n קבוצות. כעת לכל n קיימת פונקציה $g:Y_n \to P(A)^n$ המוגדרת $g((X_1,...,X_n))=X_1 \times \cdots \times X_n$ קל לראות שהיא חח"ע ולכן $|Y_n|=|A|^n =|A|$ ולכן $|X|\leq \sum_{1<n\in \mathbb {N}}|A|=|A|\cdot \aleph_0 =|A|$

כעת, קל למצוא פונקציה חח"ע מקבוצת החזקה של A ל-X - נשלח כל תת קבוצה לזוג שמכיל אותה ואת המשלים שלה.

לכן $2^{|A|} \leq |X| \leq |Y| = \aleph_0^{|A|}$ , ולפי התכונות לעיל שני הקצוות שווים. לכן עוצמת X הינה $2^a$ .

2.

$|\mathbb{N}\cup X|=\aleph_0+2^a=2^a$

$|\mathbb{N}\times X|=\aleph_0\cdot 2^a=2^a$

$|X|^{|\mathbb{N}|}=(2^a)^{\aleph_0}=2^{a\cdot \aleph_0}=2^a$

$|\mathbb{N}|^{|X|}=(\aleph_0)^{2^a}=2^{2^a}$

ב.

בעצם אנו רוצים לחשב איחוד בן מנייה של קבוצות מעוצמת $\aleph$ . לכל עותק של $\aleph$ נתאים $A_n$ ופונקציה חח"ע ועל $f_n:\mathbb{R}\rightarrow A_n$ . כעת נגדיר פונקציה $g:\mathbb{N}\times\mathbb{R}\rightarrow\bigcup_{n\in\mathbb{N}}A_n$ ע"י $g(k,x)=f_k(x)$ . מכיוון שהקבוצות זרות ו $f_k$ חח"ע ברור שg חח"ע. מכיוון ש $f_k$ על גם g על ולכן סה"כ עוצמת הסכום הינה $\aleph_0\cdot\aleph=\aleph$

הבדלים בין גרסאות בדף "88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 7"

גרסה אחרונה מ־17:46, 5 באוגוסט 2020

תוכן עניינים

אריתמטיקה של עוצמות

תרגיל

תרגיל

תרגיל

תכונות האריתמטיקה

תרגיל

תרגיל

תרגיל

תרגיל

תרגיל

תרגיל

תרגיל

תרגיל

תרגיל (בש.ב.)

תרגיל

תרגיל

תרגיל ממבחן תשסח מועד א (ד"ר שי סרוסי וד"ר אלי בגנו)

תרגיל

תרגיל

תרגיל ממבחן תשע מועד א (ד"ר שי סרוסי וד"ר אפי כהן)

תרגיל ממבחן תשע מועד ב (ד"ר שי סרוסי וד"ר אפי כהן)

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים

@@ שורה 2: / שורה 2: @@
 ==אריתמטיקה של עוצמות==
 '''הגדרה''' יהיו A,B קבוצות אזי <math>A^B:=\{f:B\rightarrow A\}</math>.
-'''תרגיל.''' יהיו A,B קבוצות כך ש <math>|B|>1</math>. הוכח כי <math>|A|<|B^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>.
 '''פתרון.'''
@@ שורה 19: / שורה 41: @@
 לפי הבנייה <math>\forall a\in A f\not=f_a</math> כיוון ש <math>f(a)\not=f_a(a)</math>. סתירה לכך ש g על.
+הערה: התרגיל הזה הוא מסקנה מהתרגילים הקודמים כי <math>|\{0,1\}|\leq |B|</math> ולכן <math>|A|<|\{0,1\}^A|\leq |B^A|</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>
-'''הערה: (למי שלמד תורת הקבוצות)''' מסיבה זו אוסף העוצמות אינו קבוצה אלא מחלקה. שכן אם הוא היה קבוצה, הייתה לו עוצמה
 '''הגדרה:'''
@@ שורה 46: / שורה 59: @@
 **<math>a^0=1</math> שכן יש פונקציה יחידה מהקבוצה הריקה לכל מקום - היחס שהוא הקבוצה הריקה.
 **<math>0^0=1</math> זה מקרה פרטי של הסעיף הקודם, ועדיין מתקיים
+**<math>1^a=1</math>
 **<math>a\neq 0 \rightarrow 0^a=0</math> אין אף פונקציה מקבוצה לא ריקה אל קבוצה ריקה, שכן יחס כזה לא יכול להיות שלם.
 ===תכונות האריתמטיקה===
@@ שורה 61: / שורה 74: @@
 נוכיח למשל <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>. היא חח"ע ועל.
@@ שורה 71: / שורה 87: @@
 הוכחה <math>2^b\leq a^b\leq (2^a)^b=2^{ab}=2^b</math>
-'''תרגיל'''
+===תרגיל===
 הוכח כי <math>\aleph_0+\aleph=\aleph</math>
 הוכחה: דרך א- ישירות מהגדרה. נבחר <math>A=[\frac{1}{4},\frac{1}{2}],B=\mathbb{N}</math> אזי
-<math>\aleph=|A|\leq |A\cap B |\leq |\mathbb {R}|=\aleph</math>
+<math>\aleph=|A|\leq |A\cup B |\leq |\mathbb {R}|=\aleph</math>
 דרך ב- מהנוסחא. <math>\aleph_0+\aleph=max\{\aleph_0,\aleph\}=\aleph </math>
-'''תרגיל'''
+===תרגיל===
-הוכח כי <math>\aleph \times \aleph=\aleph </math>
+הוכח כי <math>\aleph \cdot \aleph=\aleph </math>
 הוכחה:  <math>\aleph=|\{f:\mathbb{N}\to \{ 0,1\dots 9 \} \}|=10^{\aleph_0}=2^{\aleph_0}</math>
@@ שורה 88: / שורה 104: @@
 דרך ב- אריתמטיקה-
-<math>\aleph \times \aleph=2^{\aleph_0}\cdot 2^{\aleph_0}=2^{\aleph_0+\aleph_0}=2^{\aleph_0}=\aleph </math>
+<math>\aleph \cdot \aleph=2^{\aleph_0}\cdot 2^{\aleph_0}=2^{\aleph_0+\aleph_0}=2^{\aleph_0}=\aleph </math>
-דרך ג- מהנוסחא- <math>\aleph \times \aleph=max\{\aleph,\aleph\}=\aleph </math>
+דרך ג- מהנוסחא- <math>\aleph \cdot \aleph=max\{\aleph,\aleph\}=\aleph </math>
+===תרגיל===
-'''תרגיל ממבחן תשסח מועד א''' (ד"ר שי סרוסי וד"ר אלי בגנו)
+הוכח כי <math>|\mathbb{R}\backslash \mathbb{Q}|=\aleph</math>
+פתרון:
+כיוון ש <math>\mathbb{R}\backslash \mathbb{Q}</math> מוכל בממשיים עוצמתה לכל היותר אלף. נניח בשלילה כי עוצמתה שווה a קטנה ממש מאלף אזי
+<math>\aleph=|\mathbb{R}|=|\mathbb{R}\backslash \mathbb{Q}|+|\mathbb{Q}|=a+\aleph_0=a<\aleph</math>. סתירה
+=== תרגיל ===
+חשבו את <math>\aleph^{\aleph_0},{\aleph_0}^{\aleph}</math>
+פתרון: <math>\aleph^{\aleph_0}=\aleph,{\aleph_0}^{\aleph}=2^{\aleph}</math>
+הסיקו כי עוצמת קבוצת הפונקציות מהרציונאלים לממשיים היא <math>\aleph</math>.
+===תרגיל===
+תהא <math>A</math> קבוצה אינסופית ו <math>B\subseteq A</math> תת קבוצה.
+הוכח/הפרך
+. <math>|A\backslash B|=|A|\Rightarrow |B|<|A|</math>
+. <math>|A\backslash B|=|A|\Leftarrow |B|<|A|</math>
+פתרון:
+. הפרכה: ניקח את השלמים והטבעיים
+. נכון כי ניתן להציג A כאיחוד זר <math>A=A\backslash B \cup B</math>
+ולכן <math>|A|=|A\backslash B| + |B|</math>. אם <math>|A\backslash B|<|A|</math> נקבל סתירה
+=== תרגיל ===
+. מה עוצמת <math>\mathbb{N}^\mathbb{N}</math>
+פתרון: <math>\aleph_0^{\aleph_0} =2^{\aleph_0} </math>
+. מה עוצמת <math>X=\{f\in \mathbb{N}^\mathbb{N}:f(1)\leq f(2)\}</math>
+פתרון: לכל היותר <math>\mathbb{N}^\mathbb{N}</math> ולכל הפחות <math>\mathbb{N}^\mathbb{N}</math>
+כי לכל <math>g\in \mathbb{N}^{\mathbb{N}\setminus \{1,2\}}</math> נתאים <math>f\in X</math> ע"י <math>f(1)=f(2)=1 </math> ועבור <math>x\neq 1,2</math> נגדיר <math>f(x)=g(x)</math> ולכן <math>|\mathbb{N}^{\mathbb{N}\setminus \{1,2\}}|\leq|X|\leq |\mathbb{N}^\mathbb{N}|</math> ולפי ק.ש.ב יש שיווון
+. מה עוצמת <math>X=\{f\in \mathbb{R}^\mathbb{R}:\forall x\notin \mathbb{Q} f(x)=1\}</math>
+פתרון: X שווה עוצמה ל <math>\mathbb{R}^{\mathbb{Q}}</math> כי <math>g\in\mathbb{R}^{\mathbb{Q}}</math> ממופה ל <math>f\in X</math> המוגדרת <math>f|_{\mathbb{Q}}=g,f|_{\mathbb{R}\setminus\mathbb{Q}}=1</math>
+=== תרגיל ===
+תהי <math>\{A_i\}_{i\in I}</math> משפחה של קבוצות הזרות זו לזו כך שעוצמת  כל אחת מהן ב<math>a</math>. נגדיר <math>\sum_{i\in I} a = |\bigcup_{i\in I}A_i|</math>.
+הוכח כי <math>\sum_{i\in I} a = |I|\cdot a</math>
+פתרון:
+תהא <math>A</math> קבוצה  נוספת  מעוצמה <math>a</math>.
+לכל <math>i\in I</math> קיימת פונקציה חח"ע ועל
+<math>f_i:A\rightarrow A_i</math>.
+כעת נגדיר פונקציה <math>g:I\times A\rightarrow\bigcup_{i\in I}A_i</math> ע"י <math>g(k,x)=f_k(x)</math>. מכיוון שהקבוצות זרות ו<math>f_k</math> חח"ע ברור שg חח"ע. מכיוון ש<math>f_k</math> על גם g על ולכן קיבלנו את המבוקש.
+=== תרגיל ===
+נגדיר <math>F</math> להיות אוסף תתי הקבוצות הסופיות של הטבעיים <math>F=\{X\subseteq \mathbb{N}:|X|<\aleph_0\}</math>. מה עוצמתה?
+פתרון: לכל <math>i\in \mathbb{N}</math> נגדיר <math>F_i=\{X\subseteq \mathbb{N}:|X|=i\}</math> (אוסף תתי הקבוצות מגודל <math>i</math>). אזי <math>|F_i|\leq \aleph_0^i=\aleph_0</math>
+ואז <math>|F|=|\cup_{i\in \mathbb{N}}F_i|\leq \aleph_0\cdot \aleph_0 =\aleph_0</math>
+=== תרגיל (בש.ב.)===
+נגדיר <math>A</math> להיות אוסף תתי הקבוצות האינסופיות של הטבעיים. מה עוצמתה?
+פתרון: מתקיים כי <math>P(\mathbb{N})=A\cup A^c</math> כאשר A היא תתי הקבוצות הסופיות מתרגיל קודם שעוצמת <math>\aleph_0</math>
+ולכן <math>2^{\aleph_0}=\aleph_0+|A^c|=\max\{\aleph_0,|A^c|\}=|A^c|</math>
+=== תרגיל ===
+נגדיר <math>A=\{X\subseteq \mathbb{R}: |X|=\aleph_0 \}</math> ,מה עוצמתה?
+פתרון: לכל הפחות <math>2^{\aleph_0}</math> כי תתי הקבוצות האינסופיות של הטבעיים מעוצמה זאת. בצד שני נגדיר <math>F:\mathbb{R}^{\mathbb{N}}\to P(\mathbb{R})</math> ע"י
+<math>f\mapsto Im(f)</math> טענה: <math>A\subseteq Im(F)</math> הוכחה: תהא <math>X\in A</math> ומהגדרת A, נסיק כי X מעוצמה הטבעיים ולכן קיימת <math>f:\mathbb{N}\to X</math> חח"ע ועל ולכן <math>F(f)=Im(f)=X</math>. מסקנה מכך <math>|A|\leq |Im(F)|\leq |\mathbb{R}^{\mathbb{N}}|=\aleph^{\aleph_0}=\aleph</math>. לפי ק.ש.ב <math>|A|=2^{\aleph_0}=\aleph</math>
+=== תרגיל ===
+נגדיר <math>A=\{X\subseteq \mathbb{R}: |X|=\aleph \}</math> ,מה עוצמתה?
+פתרון: לכל היותר <math>2^\aleph</math> מצד שני <math>F:P((0,1))\to A </math>  המוגדרת <math>B\mapsto B\cup (1,2)</math> חח"ע ולפי ק.ש.ב. סימנו
+===תרגיל ממבחן תשסח מועד א (ד"ר שי סרוסי וד"ר אלי בגנו) ===
 תהי A קבוצה אינסופית. נסמן <math>a=|A|,\;B=P(A),\;F=A\times P(A),\; C=P(A)^A,\; H=B^B</math>
@@ שורה 107: / שורה 203: @@
 ב.<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 קבוצות זרות
+ג. כל יחס שקילות שקבוצת המנה 2 מתאים לחלוקה של <math>\mathbb{N}</math> ל-2 קבוצות זרות.
-לכן <math>\{R:|\mathbb{N}/R|=2\}</math> מתאים לחצי מקבוצות ב <math>P(\mathbb{N})</math>
+ולכן יש התאמה חח"ע ועל <math>\{R:|\mathbb{N}/R|=2\} \leftrightarrow W=\{\{A,A^c\}|A\subseteq \mathbb{N}\}</math> ולכן 2 הקבוצות מאותה עוצמה.
-( <math>P(A)=B\cup B'</math> כאשר <math>|B|=|B'|</math> ולכן <math>|P(A)|=|B|</math> )
-לכן<math>|\{R:|\mathbb{N}/R|=2\}|=|\{P(\mathbb{N}\}|=2^{\aleph_0}</math>
+ט: <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>
@@ שורה 140: / שורה 257: @@
 מוגדרת: לפי ההגדרה של יחס השקילות אכן מתקיים <math>f-g\in \mathbb{Z}^{\mathbb{R}}</math>
+נראה כי ל 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>F(g)=F(h)</math> לכן <math>\forall x\in\mathbb{R} f(x)-g(x)=f(x)-h(x)</math> ולכן h=g.
@@ שורה 152: / שורה 271: @@
 נגדיר F פונקציה השולחת את <math>f\in\mathbb{R}^\mathbb{R}</math> לפונקציה <math>F(f):=f-\lfloor f\rfloor\in [0,1)^\mathbb{R}</math>. נראה ש-F מוגדרת היטב (על קבוצת המנה)וההפעלה שלה על קבוצת המנה תהיה חח"ע ועל.
-מוגדרות: יהיו שתי פונקציות באותה מחלקת שקילות g,f. אזי, <math>F(g)-F(f)=g-\lfloor g\rfloor -f + \lfloor f\rfloor</math>. מכיוון שזהו הפרש של שני מספרים אי שליליים קטנים מאחד, זה שווה למספר אי שלילי קטן מאחד. מכיוון שההפרש בין f ל-g שלם, המספר הזה הוא שלם. המספר השלם האי שלילי היחיד שקטן מאחד הינו אפס
+מוגדרות: יהיו שתי פונקציות באותה מחלקת שקילות g,f. אזי, <math>F(g)-F(f)=g-\lfloor g\rfloor -f + \lfloor f\rfloor</math>. מכיוון שזהו הפרש של שני מספרים אי שליליים קטנים מאחד, זה שווה למספר שבערכו המוחלט קטן מאחד. מכיוון שההפרש בין f ל-g שלם, המספר הזה הוא שלם. המספר השלם האי שלילי היחיד שקטן מאחד הינו אפס
 כלומר <math>F(f)=F(g)</math>. לכן הפונקציה F מוגדרת היטב שכן היא שולחת נציגים שונים של מחלקת שקילות לאותו מקום.
@@ שורה 163: / שורה 282: @@
 סה"כ קיבלנו שעוצמת קבוצת המנה שווה ל<math>\aleph^\aleph</math> וזה שווה ל<math>2^\aleph</math> לפי התכונות לעיל.
-'''תרגיל ממבחן תשע מועד ב''' (ד"ר שי סרוסי וד"ר אפי כהן)
+===תרגיל ממבחן תשע מועד ב (ד"ר שי סרוסי וד"ר אפי כהן)===
 א. תהי A קבוצה אינסופית מעוצמה a.
 :1. נגדיר עבור :
-<math>X=\{(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]\}</math>.
+<math>X=\{(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>.
 כלומר אוסף החלקות הסופיות הלא טרי' הסדורות של A
@@ שורה 193: / שורה 312: @@
 <math>\forall a\in A :\; f_x(a)=k</math> כאשר <math>a\in X_k</math> כלומר שולחת איבר לאינדקס של הקבוצה שהוא נמצא בה בחלוקה.
-נוכיח שהפונקציה מוגדרת, חח"ע ועל.
+נוכיח שהפונקציה מוגדרת וחח"ע.
 מוגדרת: כיוון ש x הוא חלוקה של A אזי האיבר a יופיע ויופיע בדיוק באחת מהקבוצות.
@@ שורה 199: / שורה 318: @@
 חח"ע: נניח <math>(X_1,...,X_n)=x\neq x'=(X'_1,...,X'_m)</math>. אזי קיים <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>
+קל לראות כי הפונקציה חח"ע ולכן <math> |X| \leq (2^{a})^{\aleph_0} = 2^{a\cdot \aleph_0} =2^a</math>
+דרך 3- נציג את X כאיחוד זר <math>X=\cup_{1<n\in \mathbb {N}}Y_n</math> כאשר <math>Y_n</math> זה חלוקות סדורות של A עם n קבוצות. כעת לכל n קיימת פונקציה <math>g:Y_n \to P(A)^n</math>
+המוגדרת <math>g((X_1,...,X_n))=X_1 \times \cdots \times X_n</math> קל לראות שהיא חח"ע ולכן <math>|Y_n|=|A|^n =|A|</math> ולכן <math>|X|\leq \sum_{1<n\in \mathbb {N}}|A|=|A|\cdot \aleph_0 =|A|</math>
 כעת, קל למצוא פונקציה חח"ע מקבוצת החזקה של A ל-X - נשלח כל תת קבוצה לזוג שמכיל אותה ואת המשלים שלה.
@@ שורה 207: / שורה 333: @@
 :2.
-<math>|\mathbb{N}\cup Y|=\aleph_0+2^a=2^a</math>
+<math>|\mathbb{N}\cup X|=\aleph_0+2^a=2^a</math>
-<math>|\mathbb{N}\times Y|=\aleph_0\cdot 2^a=2^a</math>
+<math>|\mathbb{N}\times X|=\aleph_0\cdot 2^a=2^a</math>
 <math>|X|^{|\mathbb{N}|}=(2^a)^{\aleph_0}=2^{a\cdot \aleph_0}=2^a</math>