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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(תכונות האריתמטיקה)
(תכונות האריתמטיקה)
שורה 65: שורה 65:
  
 
הוכחה <math>2^b\leq a^b\leq (2^a)^b=2^{ab}=2^b</math>
 
הוכחה <math>2^b\leq a^b\leq (2^a)^b=2^{ab}=2^b</math>
 +
 +
'''תרגיל'''
 +
הוכח כי <math>|\mathbb{R}\times \mathbb{R}|=|\mathbb{R}|</math>
 +
 +
פתרון: ראינו <math>|\mathbb{R}|=10^{\aleph_0}=2^{\aleph_0}=</math>
 +
 +
לכן
 +
<math>|\mathbb{R}\times \mathbb{R}|=2^{\aleph_0}2^{\aleph_0}=2^{\aleph_0+\aleph_0}=2^{\aleph_0}=|\mathbb{R}|</math>
  
  

גרסה מ־15:50, 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\}|

דוגמא: ראינו בתירגול קודם את הזיהוי [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,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

תרגיל הוכח כי |\mathbb{R}\times \mathbb{R}|=|\mathbb{R}|

פתרון: ראינו |\mathbb{R}|=10^{\aleph_0}=2^{\aleph_0}=

לכן

|\mathbb{R}\times \mathbb{R}|=2^{\aleph_0}2^{\aleph_0}=2^{\aleph_0+\aleph_0}=2^{\aleph_0}=|\mathbb{R}|


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

תהי 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