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

תוכן עניינים

1 עוצמות

עוצמות

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

אם קיימת $f:A\to B$ חח"ע ועל אז אומרים של A ולB יש אותה עוצמה (סימון $|A|=|B|$ )
אם קיימת $f:A\to B$ חח"ע אז אומרים כי העוצמה של A קטנה או שווה לזו של B. (סימון $|A|\leq|B|$ )
אם $|A|\leq|B|$ וגם $|A|\not=|B|$ אזי אומרים כי העוצמה של A קטנה ממש מהעצמה של B (סימון $|A|<|B|$ )

הערה: בעזרת אקסיומת הבחירה מוכיחים כי אם קיימת $f:A\to B$ על אזי $|B|\leq|A|$ (בעזרת התרגיל מתירגול קודם כי ניתן לצמצם את התחום של f כך שתהא חח"ע)

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

לכל קבוצה סופית בעלת n איברים, נאמר שעוצמתה הינה n. למשל $|\{1,2,3\}|=|\{1,5,100\}|$

טענה. אם $A\subseteq B$ אזי $|A|\leq |B|$ .

הוכחה: נגדיר $f:A\to B$ פונקצית ההכלה השולחת כל איבר לעצמו. פונקציה זו חח"ע ולכן $|A|\leq|B|$

תרגיל הוכח כי עוצמת $\mathbb{N}$ שווה ל - $\mathbb{N}\cup\{0\}$

הוכחה: נגדיר $f:\mathbb{N}\to \mathbb{N}\cup\{0\}$ ע"י $f(n)=n-1$ . $f$ חח"ע ועל כי יש לה הופכית $g(n)=n+1\;\;\;\;\;g:\mathbb{N}\cup\{0\} \to \mathbb{N}$

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

הוכחה: נגדיר $f:A\to A/R$ ע"י $f(a)=[a]_R$ . הפונקציה על ולכן $|A/R|\leq |A|$

טענה אם $|A|=|A'|,\;\; |B|=|B'|$ אזי $|A\times B|=|A'\times B'|$

הוכחה: קיימות פונקציות חח"ע ועל $f_1:A\to A'.\;\;f_2:B\to B'$

נגדיר פונקציה $f:A\times B \to A'\times B'$ ע"י $(a,b)\mapsto (f_1(a),f_2(b))$ כיוון ש $f_1,f_2$ חח"ע ועל גם $f$ כזאת.

למשל $|\mathbb{N} \times \{1,2,3\}|=|(\mathbb{N}\cup\{0\}) \times \{1,5,100\}|$

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

תרגיל

תהא A קבוצה. הוכח כי $|A|\leq |P(A)|$

פתרון: נגדיר את הפונקציה $f:A|\to P(A)$ ע"י $a \mapsto \{a\}$ היא חח"ע.

תרגיל

נגדיר $A=\{f: \{1,2,3\}\to \{1,2,3,4,5\} : f \text{ is a function}\}, B=\{(x,y,z): 1\leq x,y,z \leq 5\}$

הוכח כי A ו B שוות עוצמה

פתרון:

עוצמת הטבעיים

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

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

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

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

טענה. מתקיים ש $|\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 נשלח לזוג הראשון בקבוצה השלישית
...

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

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

משפט (קנטור- שרדר-ברנשטיין) אם $|B|\leq|A|$ וגם $|A|\leq|B|$ אז $|B|=|A|$

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

הוכחה: כיוון ש $|\mathbb{N}|=|\mathbb{Z}|$ אזי לפי תרגיל ממקודם $|\mathbb{N}|=|\mathbb{N}\times \mathbb{N}|=|\mathbb{Z}\times \mathbb{Z}|$

נזכר ש $\mathbb{Q}$ הם קבוצת מנה של $\mathbb{Z} \times \mathbb{N}$ ולכן

$|\mathbb{N}|\leq |\mathbb{Q}|\leq |\mathbb{Z} \times \mathbb{N}|\leq |\mathbb{Z}\times \mathbb{Z}|=|\mathbb{N}|$

לפי קנטור ברנשטיין נקבל ש $|\mathbb{Q}|= |\mathbb{N}|$

הגדרה

העוצמה של הטבעיים מסומנת $\aleph_0$
קבוצה A המקיימת $|A|\leq \aleph_0$ נקראת בת מנייה (מקור השם כי ניתן למנות/ למספר את האיברים בה ע"י התאמה חח"ע ועל מהטבעיים במקרה האין סופי או במקרה הסופי פשוט למספר עד n )

עוצמת הממשיים

תרגיל

הוכח כי עוצמת כל הקבוצות הבאות שווה - כל קטעים מהצורה $[a,b],(a,b),[a,b),(a,b]$ כאשר $a<b$ ואפשר כי $a=-\infty , b=\infty$

הוכחה: קל לראות כי כל הקטעים הסופיים מהצורה $[a,b]$ . בעלי אותה עוצמה ע"י הפונקציה

באותו אופן כל הקטעים הסופיים מהצורה $(a,b)$ או $(a,b]$ או $[a,b)$ בעלי אותה עוצמה (כל הקטעים מאותו "סוג")

נמשיך- ט: הקטע $[0,1]$ בעל עוצמה שווה ל $[0,1)$ . ה: נגדיר $f:[0,1)\rightarrow [0,1]$ על ידי:

אם $\nexists n\in\mathbb{N}:x=\frac{1}{n}$ אזי נגדיר $f(x)=x$

אחרת נגדיר $f(\frac{1}{n})=\frac{1}{n-1}$

למעשה, כל מספר כמעט נשלח לעצמו פרט לסדרה הבת מנייה

$\frac{1}{2},\frac{1}{3},\frac{1}{4},...$

הנשלחת לסדרה

$\frac{1}{1},\frac{1}{2},\frac{1}{3},...$ .

זה פונקציה חח"ע ועל.

הערה: אותה פונקציה מוכיחה כי הקטע $(0,1]$ בעל עוצמה שווה ל $(0,1)$ .

ט: הקטע $(-1,0]$ בעל עוצמה שווה ל $[0,1)$ .

ה: ע"י הפונקציה $f(x)=-x$

ט: הקטע $(\frac{-\pi}{2},\frac{\pi}{2})$ בעל עוצמה שווה ל $\mathbb{R}$ .

ה: הפונקציה $tan:(\frac{-\pi}{2},\frac{\pi}{2})\to \mathbb{R}$ הפיכה בתחום הזה ולכן חח"ע ועל.

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

הגדרה: העוצמה של הממשיים מסומנת $\aleph$ .

עוצמת הטבעיים קטנה ממש מעוצמת הממשיים

לשם הוכחת הטענה נשתמש בקבוצה המספרים $[0,1)$ בכתיב עשרוני כלומר כל $x\in[0,1)$ הוא מהצורה $x=0.a_1a_2a_3...$ כאשר $\forall i : a_i\in \{0,1\dots 9\}$ לשם נוחות התרגיל נזהה את x עם פונקציה $f:\mathbb{N}\to \{0,1\dots 9\}$ המוגדרת $f(i)=a_i$

ט: $\aleph_0\leq\aleph$

ה: נגדיר פונקציה $g=\mathbb{N}\to [0,1)=\{f:\mathbb{N}\to \{0,1\dots 9\}\}$

ע"י $\forall n\in \mathbb{N}:g(n)=e_n(m)=\delta_{n,m}$ למשל 17 נשלח לפונקציה ששווה 0 בכל מקום פרט ל-17 ששם היא שווה 1

קל לראות כי g חח"ע.

כעת נניח בשלילה כי $\aleph_0=\aleph$ אזי יש פונקציה חח"ע ועל $g=\mathbb{N}\to [0,1)=\{f:\mathbb{N}\to \{0,1\dots 9\}\}$ נסמן $g(n)=f_n$ . נראה כי g אינה על ע"י שנבנה פונקציה f שאין לה מקור:

נגדיר $f(n)=1$ אם $f_n(n)=0$ ו $f(n)=0$ אחרת. כעת לכל n $f_n\not=f$ כי $f_n(n)\not=f(n)$ עפ"י הגדרת f. סתירה לכל ש g על.

הערה: הזיהוי $[0,1)=\{f:\mathbb{N}\to \{0,1\dots 9\}\}$ אינו מדויק כי $0.01=0.00999...$ ולכן צריך להשלח לאותה פונקציה. נשאיר כתרגיל את דיוק ההוכחה.

טענה. יהיו C,W קבוצות ויהיו $X,Y\subseteq W$ , $A,B\subseteq C$ תתי קבוצות כך ש $A\cap B=X\cap Y=\phi$ וגם $A\cup B = C$ וגם $X\cup Y = W$ . אזי אם קיימות פונקציות חח"ע ועל $g:B\rightarrow Y$ , $f:A\rightarrow X$ מתקיים ש $|C|=|W|$

הוכחה:

לפי נתון קיימות 2 פונקציות חח"ע ועל $f_1:A\to X,\;\;f_2:B\to Y$

נגדיר $f:C\to W$ ע"י $f|_A=f_1,\;\;f|_B=f_2$ . בידקו שאכן f חח"ע ועל.

תרגיל ממבחן.

א. יהיו A,B קבוצות כך ש $|A/B|=|B/A|$ . הוכח ש $|A|=|B|$ .

ב. מצא קבוצות A וB כך ש $|A|=|B|$ אבל $|A/B|\neq |B/A|$ .

פתרון.

א. מתקיים $A=(A\cap B)\cup A/B, \;\; B=(A\cap B)\cup B/A$ לפי נתון $|A/B|=|B/A|$ . כיוון ש $|A\cap B|=|A\cap B|$ לפי תרגיל קודם סימנו.

ב. ניקח את הטבעיים, ואת הטבעיים לאחר שזרקנו מהם את אחד. ברור שנשארנו עם קבוצות שוות עוצמה, אבל ההפרשים בינהם הם $\{1\},\phi$ ואלו קבוצות מעוצמה שונה.

תרגילי העשרה (לא מומלץ להעביר בתירגול)

תרגיל.

נגדיר "שמיניה" בתור זוג עיגולים בגדלים כלשהם המשיקים זה לזה בנקודה כלשהי. יהי אוסף אינסופי כלשהו של שמיניות במישור הזרות זו מזו (כלומר אין שתים עם נקודת חיתוך משותפת)

א. הוכח שעוצמת קבוצה זו הינה אלף אפס

ב. הוכח שקיימת קבוצה של אינסוף עיגולים במרחב ללא חיתוך מעוצמת אלף

פתרון.

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

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

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

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

@@ שורה 41: / שורה 41: @@
 אם נסתכל על קבוצה של קבוצות ניתן להגדיר עליה יחס "עוצמות שוות" והוא יהיה יחס רפלקסיבי, סימטרי וטרנזיטיבי. עם זאת, לא ניתן להגדיר יחס זה על כל הקבוצות כולם בשל הסיבה שלא קיימת קבוצת כל הקבוצות.
 נראה שימוש בתכונות אלו בתרגילים הבאים.
+===תרגיל ===
+תהא A קבוצה. הוכח כי <math>|A|\leq |P(A)|</math>
+פתרון: נגדיר את הפונקציה <math>f:A|\to P(A)</math> ע"י <math>a \mapsto \{a\}</math> היא חח"ע.
+===תרגיל ===
+נגדיר <math>A=\{f: \{1,2,3\}\to \{1,2,3,4,5\} : f \text{ is a function}\}, B=\{(x,y,z): 1\leq x,y,z \leq 5\}</math>
+הוכח כי A ו B שוות עוצמה
+פתרון:
 == עוצמת הטבעיים ==
 '''תרגיל.'''

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

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

תוכן עניינים

עוצמות

תרגיל

תרגיל

עוצמת הטבעיים

עוצמת הממשיים

עוצמת הטבעיים קטנה ממש מעוצמת הממשיים

תרגילי העשרה (לא מומלץ להעביר בתירגול)

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים