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

מתוך Math-Wiki
גרסה מ־08:55, 7 באוקטובר 2011 מאת ארז שיינר (שיחה | תרומות) (אריתמטיקה של עוצמות)

קפיצה אל: ניווט, חיפוש

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

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

תרגיל. יהיו A,B קבוצות כך ש, עוצמת B גדולה מאחד. הוכח כי העוצמה של אוסף הפונקציות מA לB גדולה מעוצמת A.

פתרון.

קל לבנות פונקציה על מאוסף הפונקציות מA לB אל A. נשלח כל פונקציה באוסף למקור של איבר b מסוים. מכיוון שכל הפונקציות מA לB נמצאות באוסף, בפרט כל הפונקציות ששולחות כל איבר מA ל-b יהיו שם.

נניח בשלילה שקיימת התאמה חח"ע ועל בין A לבין אוסף הפונקציות הנ"ל. נסמן בf_a:A\rightarrow B את הפונקציה המתאימה לאיבר a\in A.

ידוע לנו שבקבוצה B יש לפחות שני איברים, לכן בהנתן אחד מהם אפשר לבחור את השני. נגדיר פונקציה באופן הבא \forall a\in A : g(a)\neq g_a(a). לפי ההגדרות פונקציה זו הינה פונקציה מA לB אך אינה מתאימה לאף איבר בA בסתירה.


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

הוכחה. קל להראות שקיימת העתקה חח"ע ועל בין אוסף הפונקציות f:A\rightarrow \{0,1\} (כל קבוצה חלקית אומרת בעצם על כל איבר של A אם הוא שייך (1) או לא שייך (0). למשל הפונקציה המתאימה לקבוצה הריקה היא פונקצית האפס, והפונקציה המתאימה לקבוצה כולה היא הפונקציה 1).

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

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

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

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

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

שימו לב: מתוך הגדרה זו קל לראות את חוקי החזקות למקרי הקצה:

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


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

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

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


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

תהי A קבוצה אינסופית. נסמן |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\}

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


פתרון.


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

יהי 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 ונראה שיש העתקה S חח"ע ועל ממנה לאוסף הפונקציות מהממשיים לשלמים.

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

נניח S(g)=S(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.

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

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

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

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


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

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

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

1. נגדיר עבור 2\leq n\in\mathbb{N} את הקבוצה הבאה: 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 = \phi\Big]\}. הוכח |Y|=2^a
2. מצא את |\mathbb{N}\times Y|,|\mathbb{N}\cup Y| וגם את |Y|^{|\mathbb{N}|},|\mathbb{N}|^{|Y|}


ב.תהי \{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.

נביט באוסף הפונקציות X=\{f:A\rightarrow\mathbb{N}\}. נגדיר g:Y\rightarrow X על ידי g(y)(a)=k אם a\in X_k בתוך הn-יה הסדורה y. נוכיח שזו פונקציה מוגדרת היטב, חח"ע ועל.

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

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

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


העוצמה של אוסף הפונקציות לעיל הינה |\mathbb{N}|^{|A|}\leq 2^{|A|}, וקבוצת החזקה הינה מעוצמה 2^{|A|} ולכן סה"כ עוצמת Y הינה 2^a.


2.

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

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

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

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


ב.

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