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

מתוך Math-Wiki
שורה 34: שורה 34:
*<math>a\cdot b := |A\times B|</math>
*<math>a\cdot b := |A\times B|</math>
*<math>a^b := |\{f:B\rightarrow A\}|</math>
*<math>a^b := |\{f:B\rightarrow A\}|</math>
דוגמא: ראינו בתירגול קודם את הזיהוי <math>[0,1)=\{f:\mathbb{N} \to \{0,1,...9\}\}</math>
לכן <math>\aleph=|\mathbb{R}|=|[0,1)|=|\{f:\mathbb{N} \to \{0,1,...9\}\}|=10^{\aleph_0}</math>


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

גרסה מ־15:33, 30 ביולי 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{ 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{ a^0=1 }[/math] שכן יש פונקציה יחידה מהקבוצה הריקה לכל מקום - היחס שהוא הקבוצה הריקה.
  • [math]\displaystyle{ 0^0=1 }[/math] זה מקרה פרטי של הסעיף הקודם, ועדיין מתקיים
  • [math]\displaystyle{ a\neq 0 \rightarrow 0^a=0 }[/math] אין אף פונקציה מקבוצה לא ריקה אל קבוצה ריקה, שכן יחס כזה לא יכול להיות שלם.


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

בהנחת אקסיומת הבחירה:

  • אם a או b מייצגים עוצמה אינסופית אזי [math]\displaystyle{ a+b=max\{a,b\} }[/math]
  • אם a או b מייצגים עוצמה אינוספית ושניהם אינם אפס אזי [math]\displaystyle{ a\cdot b=max\{a,b\} }[/math]
  • אם [math]\displaystyle{ 2\leq a }[/math] ו [math]\displaystyle{ 1\leq b }[/math] ולפחות אחת מבינהם הוא אינסופי אזי [math]\displaystyle{ max\{a,2^b\}\leq a^b \leq max\{2^a,2^b\} }[/math]
    • מסקנה: אם [math]\displaystyle{ 2\leq a \leq b }[/math] אזי [math]\displaystyle{ a^b=2^b }[/math]


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

תהי A קבוצה אינסופית. נסמן [math]\displaystyle{ |A|=a,B=\{X|X\subseteq A\}, C=\{f|f:A\rightarrow P(A)\},F=\{(a,X)|(a\in A) \and (X\subseteq A)\},H=\{f|f:B\rightarrow B\} }[/math]

א. מצא את [math]\displaystyle{ |C| }[/math]
ב. מצא את [math]\displaystyle{ |F\times H| }[/math]
ג. מצא את [math]\displaystyle{ |\{R:|\mathbb{N}/R|=2\}| }[/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.

נביט במחלקת השקילות של f ונראה שיש העתקה S חח"ע ועל ממנה לאוסף הפונקציות מהממשיים לשלמים.

[math]\displaystyle{ S(g):=f-g }[/math]. לפי ההגדרה, [math]\displaystyle{ f-g\in\{h:\mathbb{R}\rightarrow\mathbb{Z}\} }[/math]. נוכיח ש-S חח"ע ועל.

נניח [math]\displaystyle{ S(g)=S(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.

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

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

נניח בשלילה ש-S אינה חח"ע, לכן [math]\displaystyle{ S(f)-S(g)=0 }[/math] עבור נציגים ממחלקות שקילות שונות. אבל אז [math]\displaystyle{ f-g=\lfloor f\rfloor - \lfloor g\rfloor }[/math] ולכן הם נציגים של אותה מחלקת שקילות בסתירה.

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


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

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

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

1. נגדיר עבור [math]\displaystyle{ 2\leq n\in\mathbb{N} }[/math] את הקבוצה הבאה: [math]\displaystyle{ Y=\{(X_1,...,X_n):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]\displaystyle{ |Y|=2^a }[/math]
2. מצא את [math]\displaystyle{ |\mathbb{N}\times Y|,|\mathbb{N}\cup Y| }[/math] וגם את [math]\displaystyle{ |Y|^{|\mathbb{N}|},|\mathbb{N}|^{|Y|} }[/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{ X=\{f:A\rightarrow\mathbb{N}\} }[/math]. נגדיר [math]\displaystyle{ g:Y\rightarrow X }[/math] על ידי [math]\displaystyle{ g(y)(a)=k }[/math] אם [math]\displaystyle{ a\in X_k }[/math] בתוך ה-[math]\displaystyle{ n }[/math]-יה הסדורה y. נוכיח שזו פונקציה מוגדרת היטב וחח"ע.

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

חח"ע: נניח [math]\displaystyle{ y_1\neq y_2 }[/math]. אזי יש איזה שתי תתי קבוצות של A שונות ביניהם, לכן יהיה איזה a באחת מהן שלא בשני שישלח למספר טבעי שונה.

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

לכן [math]\displaystyle{ 2^{|A|} \leq |Y| \leq |X| = \aleph_0^{|A|} }[/math], ולפי התכונות לעיל שני הקצוות שווים. לכן עוצמת Y הינה [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{ |Y|^{|\mathbb{N}|}=(2^a)^{\aleph_0}=2^{a\cdot \aleph_0}=2^a }[/math]

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


ב.

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