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

גרסה מ־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 \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$

@@ שורה 24: / שורה 24: @@
 '''הוכחה.'''
 יש התאמה חח"ע ועל <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>
-'''הערה:''' מסיבה זו אוסף העוצמות אינו קבוצה אלא מחלקה. שכן אם הוא היה קבוצה, הייתה לו עוצמה
+'''הערה: (למי שלמד תורת הקבוצות)''' מסיבה זו אוסף העוצמות אינו קבוצה אלא מחלקה. שכן אם הוא היה קבוצה, הייתה לו עוצמה
 '''הגדרה:'''

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

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

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

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

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים