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

מתוך Math-Wiki
שורה 56: שורה 56:
*<math>a^cb^c=(ab)^c</math>
*<math>a^cb^c=(ab)^c</math>
*<math>(a^b)^c=a^{bc}</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^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\cup C} \to A^B\times A^C</math> ע"י <math>f \mapsto (f|_B,f|_C)</math>. היא חח"ע ועל.


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


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

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

חזרה למערכי התרגול

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

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

תרגיל. יהיו A,B קבוצות כך ש [math]\displaystyle{ |B|\gt 1 }[/math]. הוכח כי [math]\displaystyle{ |A|\lt |B^A| }[/math].

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

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

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

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


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

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

לפי תרגיל קודם [math]\displaystyle{ |A|\lt |\{0,1\}^A|=|p(A)| }[/math]

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

הגדרה: יהיו שתי קבוצות זרות A,B כך ש [math]\displaystyle{ |A|=a, |B|=b }[/math]. אזי נגדיר פעולות בין עוצמות:

  • [math]\displaystyle{ a+b:=|A\cup B| }[/math]
  • [math]\displaystyle{ a\cdot b := |A\times B| }[/math]
  • [math]\displaystyle{ a^b := |\{f:B\rightarrow A\}| }[/math]

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

הערות:

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

למשל [math]\displaystyle{ 2+1=|\{1,2\}\cup\{3\}|=3 }[/math]

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


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

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

  • [math]\displaystyle{ ab=ba }[/math]
  • [math]\displaystyle{ (ab)c=a(bc) }[/math]
  • [math]\displaystyle{ a^ba^c=a^{b+c} }[/math]
  • [math]\displaystyle{ a^cb^c=(ab)^c }[/math]
  • [math]\displaystyle{ (a^b)^c=a^{bc} }[/math]

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


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


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

  • [math]\displaystyle{ a+b=max\{a,b\} }[/math]
  • אם שניהם אינם אפס אזי [math]\displaystyle{ a\cdot b=max\{a,b\} }[/math]
  • מסקנה: אם [math]\displaystyle{ 2\leq a \leq b }[/math] אזי [math]\displaystyle{ a^b=2^b }[/math]

הוכחה [math]\displaystyle{ 2^b\leq a^b\leq (2^a)^b=2^{ab}=2^b }[/math]

תרגיל הוכח כי [math]\displaystyle{ \aleph_0+\aleph=\aleph }[/math]

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

דרך ב- מהנוסחא. [math]\displaystyle{ \aleph_0+\aleph=max\{\aleph_0,\aleph\}=\aleph }[/math]

תרגיל הוכח כי [math]\displaystyle{ \aleph \times \aleph=\aleph }[/math]

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

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

דרך ב- אריתמטיקה- [math]\displaystyle{ \aleph \times \aleph=2^{\aleph_0}\cdot 2^{\aleph_0}=2^{\aleph_0+\aleph_0}=2^{\aleph_0}=\aleph }[/math]

דרך ג- מהנוסחא- [math]\displaystyle{ \aleph \times \aleph=max\{\aleph,\aleph\}=\aleph }[/math]


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

תהי A קבוצה אינסופית. נסמן [math]\displaystyle{ a=|A|,\;B=P(A),\;F=A\times P(A),\; C=P(A)^A,\; H=B^B }[/math]

א. מצא את [math]\displaystyle{ |C| }[/math]
ב. מצא את [math]\displaystyle{ |F\times H| }[/math]
ג. מצא את [math]\displaystyle{ |\{R:|\mathbb{N}/R|=2\}| }[/math] המוכלת באוסף יחסי השקילות על הטבעיים.


פתרון. א. [math]\displaystyle{ |C|=(2^a)^a=2^{aa}=2^a }[/math]

ב.[math]\displaystyle{ |F\times H|=|F||H|=a2^a(2^a)^{2^a}=2^{a2^a}=2^{2^a} }[/math]

ג. כל יחס שקילות שקבוצת המנה 2 מתאים לחלוקה של [math]\displaystyle{ |\mathbb{N}| }[/math] ל-2 קבוצות זרות לכן [math]\displaystyle{ \{R:|\mathbb{N}/R|=2\} }[/math] מתאים לחצי מקבוצות ב [math]\displaystyle{ P(\mathbb{N}) }[/math] ( [math]\displaystyle{ P(A)=B\cup B' }[/math] כאשר [math]\displaystyle{ |B|=|B'| }[/math] ולכן [math]\displaystyle{ |P(A)|=|B| }[/math] )

לכן[math]\displaystyle{ |\{R:|\mathbb{N}/R|=2\}|=|\{P(\mathbb{N}\}|=2^{\aleph_0} }[/math]


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

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

1. הוכיחו ש S הינו יחס שקילות
2. תהי [math]\displaystyle{ f\in\mathbb{R}^\mathbb{R} }[/math] מצאו את [math]\displaystyle{ |[f]| }[/math]
3. מצאו את [math]\displaystyle{ |\mathbb{R}^\mathbb{R}/S| }[/math]


פתרון:

1.

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

2.

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

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

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

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

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

3.

נזכור בסימון [math]\displaystyle{ \lfloor x\rfloor }[/math] שהוא המספר השלם הגדול ביותר הקטן או שווה לx.

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

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

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

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

סה"כ קיבלנו שעוצמת קבוצת המנה שווה ל[math]\displaystyle{ \aleph^\aleph }[/math] וזה שווה ל[math]\displaystyle{ 2^\aleph }[/math] לפי התכונות לעיל.

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

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

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

[math]\displaystyle{ X=\{(X_1,...,X_n):1\lt 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].

כלומר אוסף החלקות הסופיות הלא טרי' הסדורות של A הוכח [math]\displaystyle{ |X|=2^a }[/math]

2. מצא את [math]\displaystyle{ |\mathbb{N}\times X|,|\mathbb{N}\cup X| }[/math] וגם את [math]\displaystyle{ |X|^{|\mathbb{N}|},|\mathbb{N}|^{|X|} }[/math]


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

חשב את [math]\displaystyle{ \sum_{n\in\mathbb{N}}\aleph }[/math]


פתרון.

א.

1.

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

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

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

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

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

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

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


2.

[math]\displaystyle{ |\mathbb{N}\cup Y|=\aleph_0+2^a=2^a }[/math]

[math]\displaystyle{ |\mathbb{N}\times Y|=\aleph_0\cdot 2^a=2^a }[/math]

[math]\displaystyle{ |X|^{|\mathbb{N}|}=(2^a)^{\aleph_0}=2^{a\cdot \aleph_0}=2^a }[/math]

[math]\displaystyle{ |\mathbb{N}|^{|X|}=(\aleph_0)^{2^a}=2^{2^a} }[/math]


ב.

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