גרסה מ־10:28, 9 באוגוסט 2011

עוצמות

הגדרה. יהיו A,B שתי קבוצות. אזי:

אם קיימת פונקציה חח"ע מA לB אזי העוצמה של B גדולה או שווה לזו של A.
אם קיימת פונקציה חח"ע ועל מA לB אזי אומרים שלA ולB יש אותה עוצמה

דוגמא. יהיו A וB שתי קבוצות סופיות. אזי אם מספר האיברים בהן שווה עוצמתן שווה, ואם מספר האיברים בA גדול מזה של B אזי עוצמתה של A גדולה יותר.

לכל קבוצה סופית בעלת n איברים, נאמר שעוצמתה הינה n.

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

תרגיל. הוכח שעוצמות הקבוצות הבאות שוות: $\mathbb{N},\mathbb{Z},\mathbb{Q}$

הוכחה: נבנה פונקציות חח"ע ועל ונוכיח מספר טענות עזר בדרך.

נגדיר ע"י
- אם n זוגי אזי $f(n)=\frac{n}{2}$
- אחרת, $f(n)=-\frac{n-1}{2}$

קל לוודא שפונקציה זו חח"ע ועל לכן עוצמת השלמים ועוצמת הטבעיים שווה.

טענה. אם $A\subseteq B$ אזי $|A|\leq |B|$ . קל לבנות פונקציה מA לB ששולחת כל איבר בA לעצמו, זו פונקציה חח"ע.

טענה. אם A קבוצה וR יחס שקילויות על הקבוצה אזי עוצמת קבוצת המנה קטנה או שווה לעוצמה של A. נוכיח טענה זו בהמשך הקורס באמצעות אקסיומת הבחירה.

טענה. מתקיים ש $|\mathbb{N}|=|\mathbb{N}\times \mathbb{N}|$ .

הוכחה. נביט באוסף הזוגות הסדורים של מספרים טבעיים, ונחלק אותם לקבוצות לפי סכום האיברים בזוג. בקבוצה הראשונה יהיה הזוג (1,1), בקבוצה השנייה יהיו הזוגות (1,2),(2,1), בקבוצה השלישית יהיו הזוגות (1,3),(2,2),(3,1) וכדומה.

נגדיר פונקציה $f:\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}$ באופן הבא:

1 נשלח לזוג הראשון בקבוצה הראשונה
2 נשלח לזוג הראשון בקבוצה השנייה
3 נשלח לזוג השני בקבוצה השנייה
4 נשלח לזוג הראשון בקבוצה השלישית
...

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

כמו כן קל לראות שפונקציה זו חח"ע וגם על.

טענה. מתקיים ש $|\mathbb{Z}|=|\mathbb{Z}\times \mathbb{Z}|$ . תרגיל בית.

נביט באוסף הזוגות הסדורים בהם האיבר הימני שונה מאפס. קבוצה זו מוכלת באוסף כל הזוגות ולכן עוצמתה קטנה מעוצמת השלמים. נחלק אוסף זה ביחס השקילות $(a,b)~(x,y) \iff ay=bx$ ונקבל קבוצה מעוצמה אף קטנה יותר. קבוצת המנה שקיבלנו היא כמובן $\mathbb{Q}$ ולכן קיבלנו ש $|\mathbb{Q}|\leq |\mathbb{Z}|$ .

בכיוון ההפוך, השלמים מוכלים ברציונאליים ולכן עוצמתם קטנה יותר ומכאן שעוצמת הרציונאליים שווה לעוצמת השלמים.

גרסה מ־10:28, 9 באוגוסט 2011 (הצגת מקור) ארז שיינר (שיחה \| תרומות) (←‏עוצמות) → מעבר להשוואת הגרסאות הקודמת		גרסה מ־10:28, 9 באוגוסט 2011 (הצגת מקור) ארז שיינר (שיחה \| תרומות) (←‏עוצמות) מעבר להשוואת הגרסאות הבאה ←
שורה 51:		שורה 51:

	בכיוון ההפוך, השלמים מוכלים ברציונאליים ולכן עוצמתם קטנה יותר ומכאן שעוצמת הרציונאליים שווה לעוצמת השלמים.		בכיוון ההפוך, השלמים מוכלים ברציונאליים ולכן עוצמתם קטנה יותר ומכאן שעוצמת הרציונאליים שווה לעוצמת השלמים.
		+
		+	==השוואות עוצמות==

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

גרסה מ־10:28, 9 באוגוסט 2011

עוצמות

השוואות עוצמות

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים