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

גרסה מ־14:07, 31 ביולי 2013

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

הגדרה יהיו A,B קבוצות אזי $A^B:=\{f:B\rightarrow 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 על.

תרגיל. הוכח שעוצמת קבוצת החזקה של 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 כך ש $|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$ זה מקרה פרטי של הסעיף הקודם, ועדיין מתקיים
- $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 עוצמות כאשר אחד מהם אין סופי

$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\cap B |\leq |\mathbb {R}|=\aleph$

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

תרגיל הוכח כי $\aleph \times \aleph=\aleph$

הוכחה: ראינו כי עיבוד הנוסחה נכשל (שגיאת תחביר): \aleph=|{f:\mathbb{N}\to \{0,1\dots 9\}\}|

דרך א- ישירות מהגדרה. נבחר $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=10^{\aleph_0}|$ ולכן $\aleph \times \aleph=10^{\aleph_0}\cdot 10^{\aleph_0}=10^{\aleph_0+\aleph_0}=10^{\aleph_0}=\aleph$

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

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

תהי 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\}$ מתאים לחצי מקבוצות ב $P(\mathbb{N})$ ( $P(A)=B\cup B'$ כאשר $|B|=|B'|$ ולכן $|P(A)|=|B|$ )

לכן $|\{R:|\mathbb{N}/R|=2\}|=|\{P(\mathbb{N}\}|=2^{\aleph_0}$

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

יהי 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)=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]\}$ .

כלומר אוסף החלקות הסופיות הלא טרי' הסדורות של 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')$

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

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

2.

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

$|\mathbb{N}\times Y|=\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$

@@ שורה 53: / שורה 53: @@
 *<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>. היא חח"ע ועל.
 כלומר מתקיימים חוקי החזקות ה"רגילים"
@@ שורה 68: / שורה 71: @@
 '''תרגיל'''
-הוכח כי <math>|\mathbb{R}\times \mathbb{R}|=|\mathbb{R}|</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_0+\aleph=max\{\aleph_0,\aleph\}=\aleph </math>
+'''תרגיל'''
+הוכח כי <math>\aleph \times \aleph=\aleph </math>
+הוכחה: ראינו כי <math>\aleph=|{f:\mathbb{N}\to \{0,1\dots 9\}\}|</math>
+דרך א- ישירות מהגדרה. נבחר <math>A=\{f:\mathbb{N}\to \{0,1\dots 9\}\},B=A\times A</math> אזי
+נגדיר פונקציה <math>A\to A\times A</math> ע"י <math>f(n)\mapsto (f(2n),f(2n+1))</math> . זו פונקציה חח" ועל.
-פתרון: ראינו <math>|\mathbb{R}|=10^{\aleph_0}=2^{\aleph_0}=</math>
+דרך ב- אריתמטיקה- <math>\aleph=10^{\aleph_0}|</math> ולכן
+<math>\aleph \times \aleph=10^{\aleph_0}\cdot 10^{\aleph_0}=10^{\aleph_0+\aleph_0}=10^{\aleph_0}=\aleph </math>
-לכן
+דרך ג- מהנוסחא- <math>\aleph \times \aleph=max\{\aleph,\aleph\}=\aleph </math>
-<math>|\mathbb{R}\times \mathbb{R}|=2^{\aleph_0}2^{\aleph_0}=2^{\aleph_0+\aleph_0}=2^{\aleph_0}=|\mathbb{R}|</math>
@@ שורה 194: / שורה 209: @@
 <math>|\mathbb{N}\times Y|=\aleph_0\cdot 2^a=2^a</math>
-<math>|Y|^{|\mathbb{N}|}=(2^a)^{\aleph_0}=2^{a\cdot \aleph_0}=2^a</math>
+<math>|X|^{|\mathbb{N}|}=(2^a)^{\aleph_0}=2^{a\cdot \aleph_0}=2^a</math>
-<math>|\mathbb{N}|^{|Y|}=(\aleph_0)^{2^a}=2^{2^a}</math>
+<math>|\mathbb{N}|^{|X|}=(\aleph_0)^{2^a}=2^{2^a}</math>

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

גרסה מ־14:07, 31 ביולי 2013

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

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

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים