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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(אריתמטיקה של עוצמות)
(אריתמטיקה של עוצמות)
שורה 24: שורה 24:
 
'''הוכחה.'''  
 
'''הוכחה.'''  
 
יש התאמה חח"ע ועל <math>g:P(A)\to \{0,1\}^A</math> ע"י <math>g(B)=f_B=\chi_B</math>   
 
יש התאמה חח"ע ועל <math>g:P(A)\to \{0,1\}^A</math> ע"י <math>g(B)=f_B=\chi_B</math>   
קל להראות שקיימת העתקה חח"ע ועל בין אוסף הפונקציות <math>f:A\rightarrow \{0,1\}</math> (כל קבוצה חלקית אומרת בעצם על כל איבר של A אם הוא שייך (1) או לא שייך (0). למשל הפונקציה המתאימה לקבוצה הריקה היא פונקצית האפס, והפונקציה המתאימה לקבוצה כולה היא הפונקציה 1).
 
  
אוסף הפונקציות עומד בתנאי התרגיל לעיל ולכן עוצמתו גדולה מעוצמת A אבל זהה לעוצמה של קבוצת החזקה, כפי שרצינו.
+
לפי תרגיל קודם <math>|A|<|\{0,1\}^A|=|p(A)|</math>
  
'''הערה:''' מסיבה זו אוסף העוצמות אינו קבוצה אלא מחלקה. שכן אם הוא היה קבוצה, הייתה לו עוצמה
+
'''הערה: (למי שלמד תורת הקבוצות)''' מסיבה זו אוסף העוצמות אינו קבוצה אלא מחלקה. שכן אם הוא היה קבוצה, הייתה לו עוצמה
  
 
'''הגדרה:'''
 
'''הגדרה:'''

גרסה מ־15:30, 30 ביולי 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 ע"י 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\}|

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

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

  • 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 = \emptyset\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 - נשלח כל תת קבוצה לזוג שמכיל אותה ואת המשלים שלה.

לכן 2^{|A|} \leq |Y| \leq |X| = \aleph_0^{|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