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

גרסה מ־10:50, 13 באוגוסט 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\}$

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

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

@@ שורה 58: / שורה 58: @@
 *סימטריות: <math>f(x)-g(x)\in\mathbb{Z}</math> גורר שגם <math>g(x)-f(x)\in\mathbb{Z}</math> כי יש נגדי לחיבור
 *טרנזיטיביות: נובעת בקלות מסגירות לחיבור בשלמים: <math>f-h=f-g+g-h</math>
+.
+נביט במחלקת השקילות של f ונראה שיש העתקה S חח"ע ועל ממנה לאוסף הפונקציות מהממשיים לשלמים.
+<math>S(g):=f-g</math>. לפי ההגדרה, <math>f-g\in\{h:\mathbb{R}\rightarrow\mathbb{Z}\}</math>. נוכיח ש-S חח"ע ועל.
+נניח <math>S(g)=S(h)</math> לכן <math>\forall x\in\mathbb{R} f(x)-g(x)=f(x)-h(x)</math> ולכן h=g, זה מוכיח חח"ע.
+נוכיח על: תהי h פונקציה כלשהי מהממשיים לשלמים, ברור שf-h במחלקת השקילות של f.
+אם כך, העוצמה של מחלקת השקילות זהה לעוצמה של אוסף הפונקציות מהממשיים לשלמים והוא <math>{\aleph_0}^\aleph</math>. לפי התכונות שלמדנו לעיל מתקיים <math>2^\aleph\leq{\aleph_0}^\aleph\leq 2^\aleph</math> ולכן לפי קנטור מתקיים <math>{\aleph_0}^\aleph=2^\aleph</math>

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

גרסה מ־10:50, 13 באוגוסט 2011

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

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

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים