88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 6: הבדלים בין גרסאות בדף
אחיה בר-און (שיחה | תרומות) (←עוצמות) |
1593237070 (שיחה | תרומות) אין תקציר עריכה |
||
| (76 גרסאות ביניים של 8 משתמשים אינן מוצגות) | |||
| שורה 9: | שורה 9: | ||
הערה: בעזרת אקסיומת הבחירה מוכיחים כי אם קיימת <math>f:A\to B </math> על אזי <math>|B|\leq|A|</math> | הערה: בעזרת אקסיומת הבחירה מוכיחים כי אם קיימת <math>f:A\to B </math> על אזי <math>|B|\leq|A|</math> | ||
(בעזרת התרגיל מתירגול קודם כי ניתן לצמצם את התחום של f כך שתהא חח"ע) | |||
'''דוגמא.''' יהיו A וB שתי קבוצות סופיות. אזי אם מספר האיברים בהן שווה עוצמתן שווה, ואם מספר האיברים בA גדול מזה של B אזי עוצמתה של A גדולה יותר. | '''דוגמא.''' יהיו A וB שתי קבוצות סופיות. אזי אם מספר האיברים בהן שווה עוצמתן שווה, ואם מספר האיברים בA גדול מזה של B אזי עוצמתה של A גדולה יותר. | ||
לכל קבוצה סופית בעלת n איברים, נאמר שעוצמתה הינה n. למשל <math>|\{1,2,3\}|=|\{1,5,100\}|</math> | |||
'''טענה.''' אם <math>A\subseteq B</math> אזי <math>|A|\leq |B|</math>. | '''טענה.''' אם <math>A\subseteq B</math> אזי <math>|A|\leq |B|</math>. | ||
הוכחה: נגדיר <math>f:A\to B </math> פונקצית ההכלה השולחת כל איבר לעצמו. פונקציה זו חח"ע ולכן <math>|A|\leq|B|</math> | הוכחה: נגדיר <math>f:A\to B </math> פונקצית ההכלה השולחת כל איבר לעצמו. פונקציה זו חח"ע ולכן <math>|A|\leq|B|</math> | ||
===תרגיל=== | |||
הוכח כי עוצמת <math>\mathbb{N}</math> שווה ל -<math>\mathbb{N}\cup\{0\}</math> | |||
הוכחה: נגדיר <math>f:\mathbb{N}\to \mathbb{N}\cup\{0\} </math> ע"י <math>f(n)=n-1 </math>. | |||
<math>f</math> חח"ע ועל כי יש לה הופכית <math>g(n)=n+1\;\;\;\;\;g:\mathbb{N}\cup\{0\} \to \mathbb{N}</math> | |||
=== תרגיל === | |||
הוכיחו כי <math>|P(\mathbb{N})|=|P(\mathbb{N})-\{\emptyset\}|</math> | |||
פתרון: נגדיר פונקציה <math>f:P(\mathbb{N})\to P(\mathbb{N})-\{\emptyset\} </math> ע"י <math>\{n\}\mapsto \{n+1\},\emptyset \mapsto \{1\}</math> וכל B שאינה נקודות ואינה קבוצה ריקה נשלחת לעצמה. | |||
=== תרגיל === | |||
נסמן <math>A=\{\{n\}\mid n\in \mathbb{N}\}</math> קבוצת הנקודונים הטבעיים. הוכיחו כי <math>|P(\mathbb{N})|=|P(\mathbb{N})-A|</math> | |||
פתרון: נגדיר פונקציה <math>f:P(\mathbb{N})-A\to P(\mathbb{N}) </math> ע"י | |||
<math>\{2n,4n\}\mapsto \{n,2n\},\{2n-1,2(2n-1)\}\mapsto \{n\}</math> וכל B שאינה מהצורה <math>\{k,2k\}</math> נשלחת לעצמה. | |||
=== תרגיל === | |||
תהא <math>A</math> קבוצה . הוכיחו כי <math>|A^{\mathbb{N}}\times A^{\mathbb{N}}|=|A^{\mathbb{N}}|</math> | |||
'''הערה | פתרון: נגדיר פונקציה <math>F:A^{\mathbb{N}}\times A^{\mathbb{N}}\to A^{\mathbb{N}} </math> ע"י | ||
אם נסתכל על קבוצה של קבוצות ניתן להגדיר עליה יחס "עוצמות שוות" והוא יהיה יחס רפלקסיבי, סימטרי וטרנזיטיבי. | <math>(f,g)\mapsto \{(2n,f(n)),(2n-1,g(n))\mid n\in \mathbb{N}\}</math> | ||
'''טענה.''' אם A קבוצה וR יחס שקילויות על הקבוצה אזי עוצמת קבוצת המנה קטנה או שווה לעוצמה של A. | |||
הוכחה: נגדיר <math>f:A\to A/R </math> ע"י <math>f(a)=[a]_R</math>. הפונקציה על ולכן <math> |A/R|\leq |A| </math> | |||
'''טענה''' אם <math>|A|=|A'|,\;\; |B|=|B'|</math> אזי <math>|A\times B|=|A'\times B'|</math> | |||
הוכחה: קיימות פונקציות חח"ע ועל <math>f_1:A\to A'.\;\;f_2:B\to B'</math> | |||
נגדיר פונקציה <math>f:A\times B \to A'\times B'</math> ע"י <math>(a,b)\mapsto (f_1(a),f_2(b))</math> | |||
כיוון ש <math>f_1,f_2</math> חח"ע ועל גם <math>f</math> כזאת. | |||
למשל <math>|\mathbb{N} \times \{1,2,3\}|=|(\mathbb{N}\cup\{0\}) \times \{1,5,100\}|</math> | |||
'''הערה''' | |||
אם נסתכל על קבוצה של קבוצות ניתן להגדיר עליה יחס "עוצמות שוות" והוא יהיה יחס רפלקסיבי, סימטרי וטרנזיטיבי. עם זאת, לא ניתן להגדיר יחס זה על כל הקבוצות כולם בשל הסיבה שלא קיימת קבוצת כל הקבוצות. | |||
נראה שימוש בתכונות אלו בתרגילים הבאים. | נראה שימוש בתכונות אלו בתרגילים הבאים. | ||
'' | === תרגיל === | ||
תהא <math>(A,\leq)</math> קבוצה סדורה קווית לא סופית. נגיד שתת קבוצה <math>X</math> של <math>A</math> היא תת קבוצה יורדת אם מתקיים | |||
<math>\forall a\in A\forall x\in X \,(a<x) \to (a\in X)</math> (כאשר הסימון <math>a<x</math> פירושו ש <math>a\leq x</math> וגם <math>a\neq x</math> | |||
נסמן ב <math>D</math> את קבוצת כל תתי הקבוצות היורדות של <math>A</math> האם <math>|A|=|D|</math> ? | |||
פתרון: אמרו לי שכן. למה? כי נגדיר פונקציה <math>f:A\to D</math> המוגדרת ע"י <math>f(x)=\{a\in A\mid a<x\}</math> והיא חח"ע ועל. | |||
#מצאו את הטעות בהוכחה. | |||
# האם ואיך אפשר לתקן את הפתרון המוצע? | |||
===תרגיל === | |||
תהא A קבוצה. הוכח כי <math>|A|\leq |P(A)|</math> | |||
פתרון: נגדיר את הפונקציה <math>f:A|\to P(A)</math> ע"י <math>a \mapsto \{a\}</math> היא חח"ע. | |||
תהא A קבוצה. הוכח כי <math>|A|\neq |P(A)|</math> | |||
פתרון: נניח בשלילה כי <math>|A|= |P(A)|</math> אזי קיימת <math>f: A\to P(A)</math> הפיכה, בפרט על. נגדיר <math>X=\{a\in A: a\notin f(a)\}</math>. זוהי תת קבוצה של A ולכן, מכיוון ש f על, קיים <math>x\in A</math> כך ש <math>f(x)=X</math>. האם <math>x\in X</math>? אם לא, לפי הגדרת X נקבל כי <math>x\notin f(x)=x</math> סתירה. אם כן אז <math>x\in X=f(x)</math> אבל לפי הגדרת X מתקיים <math>x\notin f(x)</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 שוות עוצמה | |||
פתרון: | |||
נגדיר פונצקיה <math>F:A\to B</math> ע"י <math>f\mapsto (f(1),f(2),f(3))</math>. הוכיחו/השתכנעו/נסביר <math>F</math> חח"ע ועל | |||
===תרגיל === | |||
הוכיחו כי <math>|A\times A| = |A^{\{1,2\}}|</math> | |||
פתרון: הפונקציה <math>F:A^{\{1,2\}}\to A\times A</math> המוגדרת <math>f\mapsto (f(1),f(2))</math> הפיכה. | |||
=== תרגיל === | |||
הוכיחו כי אם <math>|A|=|B|</math> אזי <math>|P(A)|=|P(B)|</math> | |||
פתרון: מניחים כי קיימת <math>f:A\to B</math> הפיכה. נגדיר <math>g:P(A)\to P(B)</math> ע"י <math>A'\mapsto f[A']</math> הפיכה. | |||
האם הכיוון ההפוך נכון? אם ידוע <math>|P(A)|=|P(B)|</math> האם ניתן להסיק כי <math>|A|=|B|</math>? | |||
=== תרגיל חשוב! === | |||
תהא <math>X,Y</math> קבוצות. הוכיחו כי <math>P(Y)^{X}</math> שקולת עוצמה ל <math>P(X\times Y)</math> | |||
תשובה: יש לקחת <math>F(f)=\{(x,y)|y \in f(x)\}</math> | |||
=== תרגיל === | |||
נגדיר <math>A=\{f\in \mathbb{N}^{\mathbb{N}}\mid \forall n\in \mathbb{N}: \,f(n)<f(n+1)\}</math> הוכיחו כי אם <math>|A|=|\mathbb{N}^{\mathbb{N}}|</math> | |||
פתרון: נגדיר פונקציה <math>F:A\to \mathbb{N}^{\mathbb{N}}</math> ע"י | |||
<math>F(f)(n)=\begin{cases} f(n)-f(n-1) & \text{if }n>1\\ | |||
f(1) & \text{if }n=1 | |||
\end{cases}</math> | |||
נוכיח כי F חח"ע ועל. | |||
חח"ע: נניח <math>F(f_1)=F(f_2)</math> אזי <math>f_1(1)=F(f_1)(1)=F(f_2)(1)=f_2(1)</math> ואז מהשיוויון | |||
<math>f_1(2)-f_1(1)=F(f_1)(2)=F(f_2)(2)=f_2(2)-f_2(1)</math> נקבל כי <math>f_1(2)=f_2(2)</math> כעת נניח כי <math>f_1(n)=f_2(n)</math> ונוכיח שיוויון בקלט <math>n+1</math>. אכן מהשיוויון <math>f_1(n+1)-f_1(n)=F(f_1)(n+1)=F(f_2)(n+1)=f_2(n+1)-f_2(n)</math> נצמצם את ההנחה כי <math>f_1(n)=f_2(n)</math> ונקבל כי <math>f_1(n+1)=f_2(n+1)</math> | |||
על: תהא <math>g\in \mathbb{N}\to \mathbb{N}</math> נמצא לה מקור. נגדיר <math>f(n)=\sum_{k=1}^ng(k)</math> ואז | |||
<math>F(f)(n)=\begin{cases} f(n)-f(n-1)=g(n) & \text{if }n>1\\ | |||
f(1)=g(1) & \text{if }n=1 | |||
\end{cases}</math> | |||
ולכן <math>F(f)=g</math> | |||
שאלה: מה היה קורה אם היינו מגדירים את A בעזרת קטן שווה ולא קטן ממש? כלומר | |||
נגדיר <math>A=\{f\in \mathbb{N}^{\mathbb{N}}\mid \forall n\in \mathbb{N}: \,f(n)\leq f(n+1)\}</math> האם <math>|A|=|\mathbb{N}^{\mathbb{N}}|</math> ? | |||
== עוצמת הטבעיים == | |||
===תרגיל.=== | |||
הוכח שעוצמות הקבוצות הבאות שוות: <math>\mathbb{N},\mathbb{Z},\mathbb{Q}</math> | הוכח שעוצמות הקבוצות הבאות שוות: <math>\mathbb{N},\mathbb{Z},\mathbb{Q}</math> | ||
| שורה 39: | שורה 144: | ||
===טענה.=== | |||
מתקיים ש <math>|\mathbb{N}|=|\mathbb{N}\times \mathbb{N}|</math>. | |||
'''הוכחה.''' | '''הוכחה.''' | ||
| שורה 55: | שורה 159: | ||
קל לראות שפונקציה זו מוגדרת היטב. לכל מספר טבעי פשוט עוקבים אחרי התהליך הזה ורואים לאיזה זוג הוא נשלח. כמו כן, לכל זוג ניתן לעבור על התהליך עד שיגיע המספר שישלח אליו. | קל לראות שפונקציה זו מוגדרת היטב. לכל מספר טבעי פשוט עוקבים אחרי התהליך הזה ורואים לאיזה זוג הוא נשלח. כמו כן, לכל זוג ניתן לעבור על התהליך עד שיגיע המספר שישלח אליו. | ||
[[קובץ:NutualSquareEqNutural.jpeg]] | |||
כמו כן קל לראות שפונקציה זו חח"ע וגם על. | כמו כן קל לראות שפונקציה זו חח"ע וגם על. | ||
''' | === <math>\aleph_0 \cdot \aleph_0=\aleph_0</math> === | ||
'''הגדרה''' | |||
* העוצמה של הטבעיים מסומנת <math>\aleph_0</math> | |||
* קבוצה A המקיימת <math>|A|\leq \aleph_0 </math> נקראת '''בת מנייה''' (מקור השם כי ניתן למנות/ למספר את האיברים בה ע"י התאמה חח"ע ועל מהטבעיים במקרה האין סופי או במקרה הסופי פשוט למספר עד n ) | |||
טענה <math>B=\{2n-1 | n\in \mathbb{N}\}</math> קבוצת האי זוגיים היא בת מנייה | |||
הוכחה : נגדיר פונצקיה <math>f:\mathbb{N}\to B </math> ע"י <math>n\mapsto 2n-1</math> | |||
טענה <math>C=\mathbb{N}\cup\{0\}</math> קבוצת הטבעיים עם <math>0</math> בת מנייה | |||
הוכחה : נגדיר פונצקיה <math>f:\mathbb{N}\to C </math> ע"י <math>n\mapsto n-1</math> | |||
טענה <math>\aleph_0 \cdot \aleph_0=\aleph_0</math> | |||
הוכחה: נגדיר <math>f:B\times C\to \mathbb{N}</math> ע"י <math>(x,k)\mapsto x\cdot 2^k</math> | |||
טענה: f חח"ע | |||
הוכחה נניח <math>f(x_1,k_1)=f(x_2,k_2)</math> אזי <math>x_1 \cdot 2^{k_1} =x_2 \cdot 2^{k_2}</math> | |||
בה"כ <math>k_1\leq k_2</math> ונחלק את שני האגפים ב <math>2^{k_1}</math> | |||
נקבל כי<math>x_1 =x_2 \cdot 2^{k_2-k_1}</math>. כעת צד שמאל לא מתחלק ב 2 (כי <math>x_1</math> אי זוגי) ולכן גם אגף ימין לא מתחלק ב -2. הדבר יכול לקרות רק אם <math>k_2-k_1=0</math> או במילים אחרות <math>k_1=k_2</math>. כעת קיבלנו גם כי <math>x_1=x_2</math> ולכן בס"ה <math>(x_1,k_1)=(x_2,k_2)</math>. | |||
טענה: f על | |||
הוכחה: יהא n טבעי. יהיה <math>k\in C</math> כך ש <math>2^k</math> מחלק את n ואילו <math>2^{k+1}</math> אינו מחלק את n. כלומר החזקה הגדולה ביותר של 2 בפירוק של n למכפלת ראשונים זרים. | |||
מהגדרת k נובע כי <math>\frac{n}{2^k}</math> אי זוגי (כי אחרת הוא זוגי ואז 2 מחלק את המספר ואז <math>2^{k+1}</math> מחלק את n. סתירה). | |||
לפי הגדרת f רואים כי <math>(\frac{n}{2^k},k)</math> מקור ל n. וסיימנו. | |||
==== תרגיל ==== | |||
הוכיחו כי לכל <math>0<n</math> טבעי מתקיים כי <math>\mathbb{N}^n=\mathbb{N}\times\mathbb{N}\times \cdots \times \mathbb{N} </math> מעוצמה <math>\aleph_0</math> | |||
פתרון: באינדוקציה. בסיס: ברור. צעד: <math>|\mathbb{N}^{n+1}=|\mathbb{N}^n\times \mathbb{N}|=|\mathbb{N}\times \mathbb{N}|=|\mathbb{N}|</math> | |||
==משפט קנטור- שרדר-ברנשטיין== | |||
אם <math>|B|\leq|A|</math> וגם <math>|A|\leq|B|</math> אז <math>|B|=|A|</math> | |||
===תרגיל=== | |||
<math>|\mathbb{Q}|=\aleph_0</math>. | |||
====פתרון==== | |||
'''טענה.''' מתקיים ש <math>|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Z}\times \mathbb{Z}|</math>. | |||
הוכחה: כיוון ש <math>|\mathbb{N}|=|\mathbb{Z}|</math> אזי לפי תרגיל ממקודם | |||
<math>|\mathbb{N}|=|\mathbb{N}\times \mathbb{N}|=|\mathbb{Z}\times \mathbb{Z}|</math> | |||
כעת, נזכר ש <math> \mathbb{Q}</math> הם קבוצת מנה של <math>\mathbb{Z} \times \mathbb{N}</math> | |||
ולכן | |||
<math>|\mathbb{N}|\leq |\mathbb{Q}|\leq |\mathbb{Z} \times \mathbb{N}|\leq |\mathbb{Z}\times \mathbb{Z}|=|\mathbb{N}| </math> | |||
לפי קנטור ברנשטיין נקבל ש <math>|\mathbb{Q}|= |\mathbb{N}|=\aleph_0</math>. | |||
===תרגיל=== | |||
חשבו את עוצמת <math>A=\mathbb{Q}\cap [0,1]</math>. | |||
====פתרון==== | |||
מצד אחד <math>A\subseteq \mathbb{Q}</math> ולכן <math>|A|\leq \aleph_0</math>. | |||
מצד שני, נגדיר <math>B=\{\frac{1}{n}:n\in \mathbb{N}\}\subseteq A</math>, קל לראות ש- <math>|A|\geq |B|=\aleph_0</math>. | |||
לפי ק.ש.ב. סיימנו. | |||
<math> | ===תרגיל=== | ||
נסמן <math>A=\{1,2,3,4\}</math>. | |||
<math> | א. חשבו את עוצמת <math>\{f\in \mathbb{N}^A:f\text{ is 1-1}\}</math>. | ||
<math> | ב. חשבו את עוצמת <math>\{f\in \mathbb{N}^A:f\text{ is not 1-1}\}</math>. | ||
===תרגיל=== | |||
נסמן ב-<math>S</math> את קבוצת יחסי השקילות על הטבעיים <math>S=\{R\subseteq \mathbb{N}\times \mathbb{N}:R\text{ is an equivalence relation}\}</math>. | |||
א. הראו ש- <math>|S|\leq |P(\mathbb{N})|</math>. | |||
ב. נסמן <math>A=\mathbb{N}\smallsetminus \{1,2\}</math>, ונסמן ב-<math>T</math> את אוסף החלוקות של הטבעיים <math>T=\{\mathcal{F}:\mathcal {F} \text{ is a partition of }\mathbb{N}\}</math>. נגדיר <math>f:P(A)\to T</math> ע"י: <math>f(X)=\{X\cup \{1\},(A\smallsetminus X)\cup \{2\}</math>. הוכיחו שהיא חח"ע. | |||
ג. הוכיחו <math>|S|=|P(\mathbb{N})|</math>. | |||
===תרגיל=== | |||
תהיינה <math>A,B,C,D</math> קבוצות כך ש- <math>|A|=|C|,|B|=|D|</math>. הוכיחו: <math>|A^B|=|C^D|</math> | |||
====פתרון==== | |||
קיימות פונקציות הפיכות <math>f:A\to C,g:B\to D</math>. נגדיר פונקציה <math>\varphi :A^B\to C^D</math> ע"י: <math>\varphi(h)=\{(g(b),f(h(b))\in D\times C:b\in B\}</math>. כלומר, שלחנו פונקציה לקבוצות זוגות סדורים, והיחס המתקבל הוא, מסתבר, פונקציה (דורש הוכחה כמובן). אפשר להסתכל על זה גם באופן הבא: בהינתן פונקציה<math>h:B\to A</math> נשלח אותה לפוננקציה <math>h':D\to C</math> המוגדרת <math>h'(d)=f\circ h\circ g^{-1}(d)</math>. ניתן לראות שהיא חח"ע ועל. | |||
== עוצמת הממשיים== | |||
'''תרגיל''' | |||
הוכח כי עוצמת כל הקבוצות הבאות שווה - כל קטעים מהצורה <math>[a,b],(a,b),[a,b),(a,b]</math> כאשר <math>a<b</math> ואפשר כי <math>a=-\infty , b=\infty</math> | |||
הוכחה: | |||
קל לראות כי כל הקטעים הסופיים מהצורה <math>[a,b]</math>. בעלי אותה עוצמה ע"י הפונקציה | |||
[[קובץ:EqveOfTowIntervals.jpeg]] | |||
''' | '''הערה''': אפשר לעבור מכאן לק.ש.ב. ולא צריך את כל הפונקציות. | ||
באותו אופן כל הקטעים הסופיים מהצורה <math>(a,b)</math> או <math>(a,b]</math> או <math>[a,b)</math> בעלי אותה עוצמה (כל הקטעים מאותו "סוג") | |||
נגדיר <math> | נמשיך- ט: הקטע <math>[0,1]</math> בעל עוצמה שווה ל <math>[0,1)</math>. | ||
ה: נגדיר <math>f:[0,1)\rightarrow [0,1]</math> על ידי: | |||
*אם <math>\nexists n\in\mathbb{N}:x=\frac{1}{n}</math> אזי נגדיר <math>f(x)=x</math> | *אם <math>\nexists n\in\mathbb{N}:x=\frac{1}{n}</math> אזי נגדיר <math>f(x)=x</math> | ||
| שורה 124: | שורה 284: | ||
<math>\frac{1}{1},\frac{1}{2},\frac{1}{3},...</math>. | <math>\frac{1}{1},\frac{1}{2},\frac{1}{3},...</math>. | ||
זה פונקציה חח"ע ועל. | |||
הערה: אותה פונקציה מוכיחה כי הקטע <math>(0,1]</math> בעל עוצמה שווה ל <math>(0,1)</math>. | |||
ט: הקטע <math>(-1,0]</math> בעל עוצמה שווה ל <math>[0,1)</math>. | |||
( | ה: ע"י הפונקציה <math>f(x)=-x</math> | ||
ט: הקטע <math>(\frac{-\pi}{2},\frac{\pi}{2})</math> בעל עוצמה שווה ל <math>\mathbb{R}</math>. | |||
ה: הפונקציה <math>tan:(\frac{-\pi}{2},\frac{\pi}{2})\to \mathbb{R}</math> הפיכה בתחום הזה ולכן חח"ע ועל. | |||
לסיום נעיר כי כל קרן (קטע עם צד אחד אין סופי) ג"כ בעלת אותה עוצמה כי היא מכילה איזה שהוא קטע ומוכלת בממשיים ולכן עפ"י קנטור ברנשטיין בעלת אותה עוצמה. | |||
'''הגדרה''': העוצמה של הממשיים מסומנת <math>\aleph</math>. | |||
=== תרגיל === | |||
הוכיחו כי <math>(0,1)\cup (3,4)</math> שווה עוצמה לממשיים | |||
פתרון: הוא מוכל בממשיים ומכיל את <math>(0,1)</math> | |||
=== עוצמת הטבעיים קטנה ממש מעוצמת הממשיים === | |||
לשם הוכחת הטענה נשתמש בקבוצה המספרים <math>[0,1)</math> בכתיב עשרוני כלומר כל <math>x\in[0,1)</math> | |||
הוא מהצורה <math>x=0.a_1a_2a_3...</math> כאשר <math>\forall i : a_i\in \{0,1\dots 9\}</math> | |||
לשם נוחות התרגיל נזהה את x עם פונקציה <math>f:\mathbb{N}\to \{0,1\dots 9\}</math> המוגדרת <math>f(i)=a_i</math> | |||
ט: <math>\aleph_0\leq\aleph</math> | |||
ה: נגדיר פונקציה <math>g=\mathbb{N}\to [0,1)=\{f:\mathbb{N}\to \{0,1\dots 9\}\} </math> | |||
ע"י <math>\forall n\in \mathbb{N}:g(n)=e_n(m)=\delta_{n,m}</math> למשל 17 נשלח לפונקציה ששווה 0 בכל מקום פרט ל-17 ששם היא שווה 1 | |||
קל לראות כי g חח"ע. | |||
נניח | כעת נניח בשלילה כי <math>\aleph_0=\aleph</math> אזי יש פונקציה חח"ע ועל | ||
<math>g=\mathbb{N}\to [0,1)=\{f:\mathbb{N}\to \{0,1\dots 9\}\} </math> | |||
נסמן <math>g(n)=f_n</math>. | |||
נראה כי g אינה על ע"י שנבנה פונקציה f שאין לה מקור: | |||
נגדיר <math>f(n)=1</math> אם <math>f_n(n)=0</math> ו <math>f(n)=0</math> אחרת. | |||
כעת לכל n <math>f_n\not=f</math> כי <math>f_n(n)\not=f(n)</math> עפ"י הגדרת f. סתירה לכל ש g על. | |||
הערה: הזיהוי <math> [0,1)=\{f:\mathbb{N}\to \{0,1\dots 9\}\} </math> אינו מדויק כי <math>0.01=0.00999...</math> | |||
ולכן צריך להשלח לאותה פונקציה. נשאיר כתרגיל את דיוק ההוכחה. | |||
''' | == == | ||
'''טענה.''' יהיו C,W קבוצות ויהיו <math>X,Y\subseteq W</math>, <math>A,B\subseteq C</math> תתי קבוצות כך ש <math>A\cap B=X\cap Y=\phi</math> וגם <math>A\cup B = C</math> וגם <math>X\cup Y = W</math>. אזי אם קיימות פונקציות חח"ע ועל <math>g:B\rightarrow Y</math>,<math>f:A\rightarrow X</math> מתקיים ש <math>|C|=|W|</math> | |||
הוכחה: | |||
לפי נתון קיימות 2 פונקציות חח"ע ועל <math>f_1:A\to X,\;\;f_2:B\to Y</math> | |||
נגדיר <math>f:C\to W</math> ע"י <math>f|_A=f_1,\;\;f|_B=f_2</math>. בידקו שאכן f חח"ע ועל. | |||
''' | '''תרגיל ממבחן.''' | ||
א. | א.(ב XI) יהיו A,B קבוצות כך ש <math>|A/B|=|B/A|</math>. הוכח ש <math>|A|=|B|</math>. | ||
ב. מצא קבוצות A וB כך ש <math>|A|=|B|</math> אבל <math>|A/B|\neq |B/A|</math>. | |||
'''פתרון.''' | |||
א. מתקיים <math>A=(A\cap B)\cup A/B, \;\; B=(A\cap B)\cup B/A</math> לפי נתון <math>|A/B|=|B/A|</math>. | |||
כיוון ש <math>|A\cap B|=|A\cap B|</math> לפי תרגיל קודם סימנו. | |||
ב. ניקח את הטבעיים, ואת הטבעיים לאחר שזרקנו מהם את אחד. ברור שנשארנו עם קבוצות שוות עוצמה, אבל ההפרשים בינהם הם <math>\{1\},\phi</math> ואלו קבוצות מעוצמה שונה. | ב. ניקח את הטבעיים, ואת הטבעיים לאחר שזרקנו מהם את אחד. ברור שנשארנו עם קבוצות שוות עוצמה, אבל ההפרשים בינהם הם <math>\{1\},\phi</math> ואלו קבוצות מעוצמה שונה. | ||
== '''תרגילי העשרה''' (לא מומלץ להעביר בתירגול) == | |||
'''תרגיל.''' | '''תרגיל.''' | ||
נגדיר "שמיניה" בתור זוג | נגדיר "שמיניה" בתור זוג מעגלים בגדלים כלשהם המשיקים זה לזה בנקודה כלשהי. יהי אוסף אינסופי כלשהו של שמיניות במישור הזרות זו מזו (כלומר אין שתים עם נקודת חיתוך משותפת) | ||
א. הוכח שעוצמת קבוצה זו הינה אלף אפס | א. הוכח שעוצמת קבוצה זו הינה אלף אפס | ||
ב. הוכח שקיימת קבוצה של אינסוף | ב. הוכח שקיימת קבוצה של אינסוף מעגלים במרחב ללא חיתוך מעוצמת אלף | ||
'''פתרון.''' | '''פתרון.''' | ||
א. בהנתן שמיניה מסוימת באוסף, נבחר נקודה רציונאלית אחת | א. בהנתן שמיניה מסוימת באוסף, נבחר נקודה רציונאלית אחת ממעגל אחד, ואחת מהמעגל השני. זה נותן לנו פונקציה מהאוסף אל הזוגות הסדורים של מספרים רציונאליים. | ||
כעת, נוכיח כי פונקציה זו הינה חח"ע. נניח בשלילה כי לשתי שמיניות שונות יש נקודות משותפים בשני | כעת, נוכיח כי פונקציה זו הינה חח"ע. נניח בשלילה כי לשתי שמיניות שונות יש נקודות משותפים בשני המעגלים. אם כן, המעגל של האחת נמצא במעגל של האחרת ולכן גם נקודת ההשקה נמצאת בתוך המעגל האחד. מכיוון שהמעגל השני מכיל נקודה משותפת עם המעגל השני של השמיניה השנייה, חייב להיות חיתוך בינהם בסתירה (ציור פה יקל ממש על ההבנה שלכם...). | ||
לכן עוצמת האוסף קטנה מעוצמת הזוגות הסדורים של הרציונאליים, ולמדנו שזוגות סדורים של קבוצה בת מנייה היא קבוצה בת מנייה. לכן עוצמת האוסף קטנה מבת מנייה אבל מכיוון שהיא אינסופית היא גדולה מבת מנייה ולכן בת מנייה כדרוש. | לכן עוצמת האוסף קטנה מעוצמת הזוגות הסדורים של הרציונאליים, ולמדנו שזוגות סדורים של קבוצה בת מנייה היא קבוצה בת מנייה. לכן עוצמת האוסף קטנה מבת מנייה אבל מכיוון שהיא אינסופית היא גדולה מבת מנייה ולכן בת מנייה כדרוש. | ||
ב. ניקח את אוסף | ב. ניקח את אוסף המעגלים עם מרכז בראשית ורדיוס ממשי חיובי. אין בינהם חיתוך, והכמות שלהם זהה לחצי ציר הממשיים והוא כמובן מעוצמת אלף. | ||
גרסה אחרונה מ־07:53, 2 באוגוסט 2021
עוצמות
הגדרה. יהיו A,B שתי קבוצות. אזי:
- אם קיימת [math]\displaystyle{ f:A\to B }[/math] חח"ע ועל אז אומרים של A ולB יש אותה עוצמה (סימון [math]\displaystyle{ |A|=|B| }[/math])
- אם קיימת [math]\displaystyle{ f:A\to B }[/math] חח"ע אז אומרים כי העוצמה של A קטנה או שווה לזו של B. (סימון [math]\displaystyle{ |A|\leq|B| }[/math])
- אם [math]\displaystyle{ |A|\leq|B| }[/math] וגם [math]\displaystyle{ |A|\not=|B| }[/math] אזי אומרים כי העוצמה של A קטנה ממש מהעצמה של B (סימון [math]\displaystyle{ |A|\lt |B| }[/math])
הערה: בעזרת אקסיומת הבחירה מוכיחים כי אם קיימת [math]\displaystyle{ f:A\to B }[/math] על אזי [math]\displaystyle{ |B|\leq|A| }[/math] (בעזרת התרגיל מתירגול קודם כי ניתן לצמצם את התחום של f כך שתהא חח"ע)
דוגמא. יהיו A וB שתי קבוצות סופיות. אזי אם מספר האיברים בהן שווה עוצמתן שווה, ואם מספר האיברים בA גדול מזה של B אזי עוצמתה של A גדולה יותר.
לכל קבוצה סופית בעלת n איברים, נאמר שעוצמתה הינה n. למשל [math]\displaystyle{ |\{1,2,3\}|=|\{1,5,100\}| }[/math]
טענה. אם [math]\displaystyle{ A\subseteq B }[/math] אזי [math]\displaystyle{ |A|\leq |B| }[/math].
הוכחה: נגדיר [math]\displaystyle{ f:A\to B }[/math] פונקצית ההכלה השולחת כל איבר לעצמו. פונקציה זו חח"ע ולכן [math]\displaystyle{ |A|\leq|B| }[/math]
תרגיל
הוכח כי עוצמת [math]\displaystyle{ \mathbb{N} }[/math] שווה ל -[math]\displaystyle{ \mathbb{N}\cup\{0\} }[/math]
הוכחה: נגדיר [math]\displaystyle{ f:\mathbb{N}\to \mathbb{N}\cup\{0\} }[/math] ע"י [math]\displaystyle{ f(n)=n-1 }[/math]. [math]\displaystyle{ f }[/math] חח"ע ועל כי יש לה הופכית [math]\displaystyle{ g(n)=n+1\;\;\;\;\;g:\mathbb{N}\cup\{0\} \to \mathbb{N} }[/math]
תרגיל
הוכיחו כי [math]\displaystyle{ |P(\mathbb{N})|=|P(\mathbb{N})-\{\emptyset\}| }[/math]
פתרון: נגדיר פונקציה [math]\displaystyle{ f:P(\mathbb{N})\to P(\mathbb{N})-\{\emptyset\} }[/math] ע"י [math]\displaystyle{ \{n\}\mapsto \{n+1\},\emptyset \mapsto \{1\} }[/math] וכל B שאינה נקודות ואינה קבוצה ריקה נשלחת לעצמה.
תרגיל
נסמן [math]\displaystyle{ A=\{\{n\}\mid n\in \mathbb{N}\} }[/math] קבוצת הנקודונים הטבעיים. הוכיחו כי [math]\displaystyle{ |P(\mathbb{N})|=|P(\mathbb{N})-A| }[/math]
פתרון: נגדיר פונקציה [math]\displaystyle{ f:P(\mathbb{N})-A\to P(\mathbb{N}) }[/math] ע"י [math]\displaystyle{ \{2n,4n\}\mapsto \{n,2n\},\{2n-1,2(2n-1)\}\mapsto \{n\} }[/math] וכל B שאינה מהצורה [math]\displaystyle{ \{k,2k\} }[/math] נשלחת לעצמה.
תרגיל
תהא [math]\displaystyle{ A }[/math] קבוצה . הוכיחו כי [math]\displaystyle{ |A^{\mathbb{N}}\times A^{\mathbb{N}}|=|A^{\mathbb{N}}| }[/math]
פתרון: נגדיר פונקציה [math]\displaystyle{ F:A^{\mathbb{N}}\times A^{\mathbb{N}}\to A^{\mathbb{N}} }[/math] ע"י [math]\displaystyle{ (f,g)\mapsto \{(2n,f(n)),(2n-1,g(n))\mid n\in \mathbb{N}\} }[/math]
טענה. אם A קבוצה וR יחס שקילויות על הקבוצה אזי עוצמת קבוצת המנה קטנה או שווה לעוצמה של A.
הוכחה: נגדיר [math]\displaystyle{ f:A\to A/R }[/math] ע"י [math]\displaystyle{ f(a)=[a]_R }[/math]. הפונקציה על ולכן [math]\displaystyle{ |A/R|\leq |A| }[/math]
טענה אם [math]\displaystyle{ |A|=|A'|,\;\; |B|=|B'| }[/math] אזי [math]\displaystyle{ |A\times B|=|A'\times B'| }[/math]
הוכחה: קיימות פונקציות חח"ע ועל [math]\displaystyle{ f_1:A\to A'.\;\;f_2:B\to B' }[/math]
נגדיר פונקציה [math]\displaystyle{ f:A\times B \to A'\times B' }[/math] ע"י [math]\displaystyle{ (a,b)\mapsto (f_1(a),f_2(b)) }[/math] כיוון ש [math]\displaystyle{ f_1,f_2 }[/math] חח"ע ועל גם [math]\displaystyle{ f }[/math] כזאת.
למשל [math]\displaystyle{ |\mathbb{N} \times \{1,2,3\}|=|(\mathbb{N}\cup\{0\}) \times \{1,5,100\}| }[/math]
הערה אם נסתכל על קבוצה של קבוצות ניתן להגדיר עליה יחס "עוצמות שוות" והוא יהיה יחס רפלקסיבי, סימטרי וטרנזיטיבי. עם זאת, לא ניתן להגדיר יחס זה על כל הקבוצות כולם בשל הסיבה שלא קיימת קבוצת כל הקבוצות. נראה שימוש בתכונות אלו בתרגילים הבאים.
תרגיל
תהא [math]\displaystyle{ (A,\leq) }[/math] קבוצה סדורה קווית לא סופית. נגיד שתת קבוצה [math]\displaystyle{ X }[/math] של [math]\displaystyle{ A }[/math] היא תת קבוצה יורדת אם מתקיים [math]\displaystyle{ \forall a\in A\forall x\in X \,(a\lt x) \to (a\in X) }[/math] (כאשר הסימון [math]\displaystyle{ a\lt x }[/math] פירושו ש [math]\displaystyle{ a\leq x }[/math] וגם [math]\displaystyle{ a\neq x }[/math]
נסמן ב [math]\displaystyle{ D }[/math] את קבוצת כל תתי הקבוצות היורדות של [math]\displaystyle{ A }[/math] האם [math]\displaystyle{ |A|=|D| }[/math] ?
פתרון: אמרו לי שכן. למה? כי נגדיר פונקציה [math]\displaystyle{ f:A\to D }[/math] המוגדרת ע"י [math]\displaystyle{ f(x)=\{a\in A\mid a\lt x\} }[/math] והיא חח"ע ועל.
- מצאו את הטעות בהוכחה.
- האם ואיך אפשר לתקן את הפתרון המוצע?
תרגיל
תהא A קבוצה. הוכח כי [math]\displaystyle{ |A|\leq |P(A)| }[/math]
פתרון: נגדיר את הפונקציה [math]\displaystyle{ f:A|\to P(A) }[/math] ע"י [math]\displaystyle{ a \mapsto \{a\} }[/math] היא חח"ע.
תהא A קבוצה. הוכח כי [math]\displaystyle{ |A|\neq |P(A)| }[/math]
פתרון: נניח בשלילה כי [math]\displaystyle{ |A|= |P(A)| }[/math] אזי קיימת [math]\displaystyle{ f: A\to P(A) }[/math] הפיכה, בפרט על. נגדיר [math]\displaystyle{ X=\{a\in A: a\notin f(a)\} }[/math]. זוהי תת קבוצה של A ולכן, מכיוון ש f על, קיים [math]\displaystyle{ x\in A }[/math] כך ש [math]\displaystyle{ f(x)=X }[/math]. האם [math]\displaystyle{ x\in X }[/math]? אם לא, לפי הגדרת X נקבל כי [math]\displaystyle{ x\notin f(x)=x }[/math] סתירה. אם כן אז [math]\displaystyle{ x\in X=f(x) }[/math] אבל לפי הגדרת X מתקיים [math]\displaystyle{ x\notin f(x) }[/math] סתירה. משל
תרגיל
נגדיר [math]\displaystyle{ 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 שוות עוצמה
פתרון:
נגדיר פונצקיה [math]\displaystyle{ F:A\to B }[/math] ע"י [math]\displaystyle{ f\mapsto (f(1),f(2),f(3)) }[/math]. הוכיחו/השתכנעו/נסביר [math]\displaystyle{ F }[/math] חח"ע ועל
תרגיל
הוכיחו כי [math]\displaystyle{ |A\times A| = |A^{\{1,2\}}| }[/math]
פתרון: הפונקציה [math]\displaystyle{ F:A^{\{1,2\}}\to A\times A }[/math] המוגדרת [math]\displaystyle{ f\mapsto (f(1),f(2)) }[/math] הפיכה.
תרגיל
הוכיחו כי אם [math]\displaystyle{ |A|=|B| }[/math] אזי [math]\displaystyle{ |P(A)|=|P(B)| }[/math]
פתרון: מניחים כי קיימת [math]\displaystyle{ f:A\to B }[/math] הפיכה. נגדיר [math]\displaystyle{ g:P(A)\to P(B) }[/math] ע"י [math]\displaystyle{ A'\mapsto f[A'] }[/math] הפיכה.
האם הכיוון ההפוך נכון? אם ידוע [math]\displaystyle{ |P(A)|=|P(B)| }[/math] האם ניתן להסיק כי [math]\displaystyle{ |A|=|B| }[/math]?
תרגיל חשוב!
תהא [math]\displaystyle{ X,Y }[/math] קבוצות. הוכיחו כי [math]\displaystyle{ P(Y)^{X} }[/math] שקולת עוצמה ל [math]\displaystyle{ P(X\times Y) }[/math] תשובה: יש לקחת [math]\displaystyle{ F(f)=\{(x,y)|y \in f(x)\} }[/math]
תרגיל
נגדיר [math]\displaystyle{ A=\{f\in \mathbb{N}^{\mathbb{N}}\mid \forall n\in \mathbb{N}: \,f(n)\lt f(n+1)\} }[/math] הוכיחו כי אם [math]\displaystyle{ |A|=|\mathbb{N}^{\mathbb{N}}| }[/math]
פתרון: נגדיר פונקציה [math]\displaystyle{ F:A\to \mathbb{N}^{\mathbb{N}} }[/math] ע"י [math]\displaystyle{ F(f)(n)=\begin{cases} f(n)-f(n-1) & \text{if }n\gt 1\\ f(1) & \text{if }n=1 \end{cases} }[/math]
נוכיח כי F חח"ע ועל.
חח"ע: נניח [math]\displaystyle{ F(f_1)=F(f_2) }[/math] אזי [math]\displaystyle{ f_1(1)=F(f_1)(1)=F(f_2)(1)=f_2(1) }[/math] ואז מהשיוויון [math]\displaystyle{ f_1(2)-f_1(1)=F(f_1)(2)=F(f_2)(2)=f_2(2)-f_2(1) }[/math] נקבל כי [math]\displaystyle{ f_1(2)=f_2(2) }[/math] כעת נניח כי [math]\displaystyle{ f_1(n)=f_2(n) }[/math] ונוכיח שיוויון בקלט [math]\displaystyle{ n+1 }[/math]. אכן מהשיוויון [math]\displaystyle{ f_1(n+1)-f_1(n)=F(f_1)(n+1)=F(f_2)(n+1)=f_2(n+1)-f_2(n) }[/math] נצמצם את ההנחה כי [math]\displaystyle{ f_1(n)=f_2(n) }[/math] ונקבל כי [math]\displaystyle{ f_1(n+1)=f_2(n+1) }[/math]
על: תהא [math]\displaystyle{ g\in \mathbb{N}\to \mathbb{N} }[/math] נמצא לה מקור. נגדיר [math]\displaystyle{ f(n)=\sum_{k=1}^ng(k) }[/math] ואז [math]\displaystyle{ F(f)(n)=\begin{cases} f(n)-f(n-1)=g(n) & \text{if }n\gt 1\\ f(1)=g(1) & \text{if }n=1 \end{cases} }[/math]
ולכן [math]\displaystyle{ F(f)=g }[/math]
שאלה: מה היה קורה אם היינו מגדירים את A בעזרת קטן שווה ולא קטן ממש? כלומר
נגדיר [math]\displaystyle{ A=\{f\in \mathbb{N}^{\mathbb{N}}\mid \forall n\in \mathbb{N}: \,f(n)\leq f(n+1)\} }[/math] האם [math]\displaystyle{ |A|=|\mathbb{N}^{\mathbb{N}}| }[/math] ?
עוצמת הטבעיים
תרגיל.
הוכח שעוצמות הקבוצות הבאות שוות: [math]\displaystyle{ \mathbb{N},\mathbb{Z},\mathbb{Q} }[/math]
הוכחה: נבנה פונקציות חח"ע ועל ונוכיח מספר טענות עזר בדרך.
- נגדיר [math]\displaystyle{ f:\mathbb{N}\rightarrow\mathbb{Z} }[/math] ע"י
- אם n זוגי אזי [math]\displaystyle{ f(n)=\frac{n}{2} }[/math]
- אחרת, [math]\displaystyle{ f(n)=-\frac{n-1}{2} }[/math]
קל לוודא שפונקציה זו חח"ע ועל לכן עוצמת השלמים ועוצמת הטבעיים שווה.
טענה.
מתקיים ש [math]\displaystyle{ |\mathbb{N}|=|\mathbb{N}\times \mathbb{N}| }[/math].
הוכחה. נביט באוסף הזוגות הסדורים של מספרים טבעיים, ונחלק אותם לקבוצות לפי סכום האיברים בזוג. בקבוצה הראשונה יהיה הזוג (1,1), בקבוצה השנייה יהיו הזוגות (1,2),(2,1), בקבוצה השלישית יהיו הזוגות (1,3),(2,2),(3,1) וכדומה.
נגדיר פונקציה [math]\displaystyle{ f:\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N} }[/math] באופן הבא:
- 1 נשלח לזוג הראשון בקבוצה הראשונה
- 2 נשלח לזוג הראשון בקבוצה השנייה
- 3 נשלח לזוג השני בקבוצה השנייה
- 4 נשלח לזוג הראשון בקבוצה השלישית
- ...
קל לראות שפונקציה זו מוגדרת היטב. לכל מספר טבעי פשוט עוקבים אחרי התהליך הזה ורואים לאיזה זוג הוא נשלח. כמו כן, לכל זוג ניתן לעבור על התהליך עד שיגיע המספר שישלח אליו.
כמו כן קל לראות שפונקציה זו חח"ע וגם על.
[math]\displaystyle{ \aleph_0 \cdot \aleph_0=\aleph_0 }[/math]
הגדרה
- העוצמה של הטבעיים מסומנת [math]\displaystyle{ \aleph_0 }[/math]
- קבוצה A המקיימת [math]\displaystyle{ |A|\leq \aleph_0 }[/math] נקראת בת מנייה (מקור השם כי ניתן למנות/ למספר את האיברים בה ע"י התאמה חח"ע ועל מהטבעיים במקרה האין סופי או במקרה הסופי פשוט למספר עד n )
טענה [math]\displaystyle{ B=\{2n-1 | n\in \mathbb{N}\} }[/math] קבוצת האי זוגיים היא בת מנייה
הוכחה : נגדיר פונצקיה [math]\displaystyle{ f:\mathbb{N}\to B }[/math] ע"י [math]\displaystyle{ n\mapsto 2n-1 }[/math]
טענה [math]\displaystyle{ C=\mathbb{N}\cup\{0\} }[/math] קבוצת הטבעיים עם [math]\displaystyle{ 0 }[/math] בת מנייה
הוכחה : נגדיר פונצקיה [math]\displaystyle{ f:\mathbb{N}\to C }[/math] ע"י [math]\displaystyle{ n\mapsto n-1 }[/math]
טענה [math]\displaystyle{ \aleph_0 \cdot \aleph_0=\aleph_0 }[/math]
הוכחה: נגדיר [math]\displaystyle{ f:B\times C\to \mathbb{N} }[/math] ע"י [math]\displaystyle{ (x,k)\mapsto x\cdot 2^k }[/math]
טענה: f חח"ע
הוכחה נניח [math]\displaystyle{ f(x_1,k_1)=f(x_2,k_2) }[/math] אזי [math]\displaystyle{ x_1 \cdot 2^{k_1} =x_2 \cdot 2^{k_2} }[/math]
בה"כ [math]\displaystyle{ k_1\leq k_2 }[/math] ונחלק את שני האגפים ב [math]\displaystyle{ 2^{k_1} }[/math]
נקבל כי[math]\displaystyle{ x_1 =x_2 \cdot 2^{k_2-k_1} }[/math]. כעת צד שמאל לא מתחלק ב 2 (כי [math]\displaystyle{ x_1 }[/math] אי זוגי) ולכן גם אגף ימין לא מתחלק ב -2. הדבר יכול לקרות רק אם [math]\displaystyle{ k_2-k_1=0 }[/math] או במילים אחרות [math]\displaystyle{ k_1=k_2 }[/math]. כעת קיבלנו גם כי [math]\displaystyle{ x_1=x_2 }[/math] ולכן בס"ה [math]\displaystyle{ (x_1,k_1)=(x_2,k_2) }[/math].
טענה: f על
הוכחה: יהא n טבעי. יהיה [math]\displaystyle{ k\in C }[/math] כך ש [math]\displaystyle{ 2^k }[/math] מחלק את n ואילו [math]\displaystyle{ 2^{k+1} }[/math] אינו מחלק את n. כלומר החזקה הגדולה ביותר של 2 בפירוק של n למכפלת ראשונים זרים.
מהגדרת k נובע כי [math]\displaystyle{ \frac{n}{2^k} }[/math] אי זוגי (כי אחרת הוא זוגי ואז 2 מחלק את המספר ואז [math]\displaystyle{ 2^{k+1} }[/math] מחלק את n. סתירה).
לפי הגדרת f רואים כי [math]\displaystyle{ (\frac{n}{2^k},k) }[/math] מקור ל n. וסיימנו.
תרגיל
הוכיחו כי לכל [math]\displaystyle{ 0\lt n }[/math] טבעי מתקיים כי [math]\displaystyle{ \mathbb{N}^n=\mathbb{N}\times\mathbb{N}\times \cdots \times \mathbb{N} }[/math] מעוצמה [math]\displaystyle{ \aleph_0 }[/math]
פתרון: באינדוקציה. בסיס: ברור. צעד: [math]\displaystyle{ |\mathbb{N}^{n+1}=|\mathbb{N}^n\times \mathbb{N}|=|\mathbb{N}\times \mathbb{N}|=|\mathbb{N}| }[/math]
משפט קנטור- שרדר-ברנשטיין
אם [math]\displaystyle{ |B|\leq|A| }[/math] וגם [math]\displaystyle{ |A|\leq|B| }[/math] אז [math]\displaystyle{ |B|=|A| }[/math]
תרגיל
[math]\displaystyle{ |\mathbb{Q}|=\aleph_0 }[/math].
פתרון
טענה. מתקיים ש [math]\displaystyle{ |\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Z}\times \mathbb{Z}| }[/math].
הוכחה: כיוון ש [math]\displaystyle{ |\mathbb{N}|=|\mathbb{Z}| }[/math] אזי לפי תרגיל ממקודם [math]\displaystyle{ |\mathbb{N}|=|\mathbb{N}\times \mathbb{N}|=|\mathbb{Z}\times \mathbb{Z}| }[/math]
כעת, נזכר ש [math]\displaystyle{ \mathbb{Q} }[/math] הם קבוצת מנה של [math]\displaystyle{ \mathbb{Z} \times \mathbb{N} }[/math] ולכן
[math]\displaystyle{ |\mathbb{N}|\leq |\mathbb{Q}|\leq |\mathbb{Z} \times \mathbb{N}|\leq |\mathbb{Z}\times \mathbb{Z}|=|\mathbb{N}| }[/math]
לפי קנטור ברנשטיין נקבל ש [math]\displaystyle{ |\mathbb{Q}|= |\mathbb{N}|=\aleph_0 }[/math].
תרגיל
חשבו את עוצמת [math]\displaystyle{ A=\mathbb{Q}\cap [0,1] }[/math].
פתרון
מצד אחד [math]\displaystyle{ A\subseteq \mathbb{Q} }[/math] ולכן [math]\displaystyle{ |A|\leq \aleph_0 }[/math].
מצד שני, נגדיר [math]\displaystyle{ B=\{\frac{1}{n}:n\in \mathbb{N}\}\subseteq A }[/math], קל לראות ש- [math]\displaystyle{ |A|\geq |B|=\aleph_0 }[/math].
לפי ק.ש.ב. סיימנו.
תרגיל
נסמן [math]\displaystyle{ A=\{1,2,3,4\} }[/math].
א. חשבו את עוצמת [math]\displaystyle{ \{f\in \mathbb{N}^A:f\text{ is 1-1}\} }[/math].
ב. חשבו את עוצמת [math]\displaystyle{ \{f\in \mathbb{N}^A:f\text{ is not 1-1}\} }[/math].
תרגיל
נסמן ב-[math]\displaystyle{ S }[/math] את קבוצת יחסי השקילות על הטבעיים [math]\displaystyle{ S=\{R\subseteq \mathbb{N}\times \mathbb{N}:R\text{ is an equivalence relation}\} }[/math].
א. הראו ש- [math]\displaystyle{ |S|\leq |P(\mathbb{N})| }[/math].
ב. נסמן [math]\displaystyle{ A=\mathbb{N}\smallsetminus \{1,2\} }[/math], ונסמן ב-[math]\displaystyle{ T }[/math] את אוסף החלוקות של הטבעיים [math]\displaystyle{ T=\{\mathcal{F}:\mathcal {F} \text{ is a partition of }\mathbb{N}\} }[/math]. נגדיר [math]\displaystyle{ f:P(A)\to T }[/math] ע"י: [math]\displaystyle{ f(X)=\{X\cup \{1\},(A\smallsetminus X)\cup \{2\} }[/math]. הוכיחו שהיא חח"ע.
ג. הוכיחו [math]\displaystyle{ |S|=|P(\mathbb{N})| }[/math].
תרגיל
תהיינה [math]\displaystyle{ A,B,C,D }[/math] קבוצות כך ש- [math]\displaystyle{ |A|=|C|,|B|=|D| }[/math]. הוכיחו: [math]\displaystyle{ |A^B|=|C^D| }[/math]
פתרון
קיימות פונקציות הפיכות [math]\displaystyle{ f:A\to C,g:B\to D }[/math]. נגדיר פונקציה [math]\displaystyle{ \varphi :A^B\to C^D }[/math] ע"י: [math]\displaystyle{ \varphi(h)=\{(g(b),f(h(b))\in D\times C:b\in B\} }[/math]. כלומר, שלחנו פונקציה לקבוצות זוגות סדורים, והיחס המתקבל הוא, מסתבר, פונקציה (דורש הוכחה כמובן). אפשר להסתכל על זה גם באופן הבא: בהינתן פונקציה[math]\displaystyle{ h:B\to A }[/math] נשלח אותה לפוננקציה [math]\displaystyle{ h':D\to C }[/math] המוגדרת [math]\displaystyle{ h'(d)=f\circ h\circ g^{-1}(d) }[/math]. ניתן לראות שהיא חח"ע ועל.
עוצמת הממשיים
תרגיל
הוכח כי עוצמת כל הקבוצות הבאות שווה - כל קטעים מהצורה [math]\displaystyle{ [a,b],(a,b),[a,b),(a,b] }[/math] כאשר [math]\displaystyle{ a\lt b }[/math] ואפשר כי [math]\displaystyle{ a=-\infty , b=\infty }[/math]
הוכחה: קל לראות כי כל הקטעים הסופיים מהצורה [math]\displaystyle{ [a,b] }[/math]. בעלי אותה עוצמה ע"י הפונקציה
הערה: אפשר לעבור מכאן לק.ש.ב. ולא צריך את כל הפונקציות.
באותו אופן כל הקטעים הסופיים מהצורה [math]\displaystyle{ (a,b) }[/math] או [math]\displaystyle{ (a,b] }[/math] או [math]\displaystyle{ [a,b) }[/math] בעלי אותה עוצמה (כל הקטעים מאותו "סוג")
נמשיך- ט: הקטע [math]\displaystyle{ [0,1] }[/math] בעל עוצמה שווה ל [math]\displaystyle{ [0,1) }[/math]. ה: נגדיר [math]\displaystyle{ f:[0,1)\rightarrow [0,1] }[/math] על ידי:
- אם [math]\displaystyle{ \nexists n\in\mathbb{N}:x=\frac{1}{n} }[/math] אזי נגדיר [math]\displaystyle{ f(x)=x }[/math]
- אחרת נגדיר [math]\displaystyle{ f(\frac{1}{n})=\frac{1}{n-1} }[/math]
למעשה, כל מספר כמעט נשלח לעצמו פרט לסדרה הבת מנייה
[math]\displaystyle{ \frac{1}{2},\frac{1}{3},\frac{1}{4},... }[/math]
הנשלחת לסדרה
[math]\displaystyle{ \frac{1}{1},\frac{1}{2},\frac{1}{3},... }[/math].
זה פונקציה חח"ע ועל.
הערה: אותה פונקציה מוכיחה כי הקטע [math]\displaystyle{ (0,1] }[/math] בעל עוצמה שווה ל [math]\displaystyle{ (0,1) }[/math].
ט: הקטע [math]\displaystyle{ (-1,0] }[/math] בעל עוצמה שווה ל [math]\displaystyle{ [0,1) }[/math].
ה: ע"י הפונקציה [math]\displaystyle{ f(x)=-x }[/math]
ט: הקטע [math]\displaystyle{ (\frac{-\pi}{2},\frac{\pi}{2}) }[/math] בעל עוצמה שווה ל [math]\displaystyle{ \mathbb{R} }[/math].
ה: הפונקציה [math]\displaystyle{ tan:(\frac{-\pi}{2},\frac{\pi}{2})\to \mathbb{R} }[/math] הפיכה בתחום הזה ולכן חח"ע ועל.
לסיום נעיר כי כל קרן (קטע עם צד אחד אין סופי) ג"כ בעלת אותה עוצמה כי היא מכילה איזה שהוא קטע ומוכלת בממשיים ולכן עפ"י קנטור ברנשטיין בעלת אותה עוצמה.
הגדרה: העוצמה של הממשיים מסומנת [math]\displaystyle{ \aleph }[/math].
תרגיל
הוכיחו כי [math]\displaystyle{ (0,1)\cup (3,4) }[/math] שווה עוצמה לממשיים
פתרון: הוא מוכל בממשיים ומכיל את [math]\displaystyle{ (0,1) }[/math]
עוצמת הטבעיים קטנה ממש מעוצמת הממשיים
לשם הוכחת הטענה נשתמש בקבוצה המספרים [math]\displaystyle{ [0,1) }[/math] בכתיב עשרוני כלומר כל [math]\displaystyle{ x\in[0,1) }[/math] הוא מהצורה [math]\displaystyle{ x=0.a_1a_2a_3... }[/math] כאשר [math]\displaystyle{ \forall i : a_i\in \{0,1\dots 9\} }[/math] לשם נוחות התרגיל נזהה את x עם פונקציה [math]\displaystyle{ f:\mathbb{N}\to \{0,1\dots 9\} }[/math] המוגדרת [math]\displaystyle{ f(i)=a_i }[/math]
ט: [math]\displaystyle{ \aleph_0\leq\aleph }[/math]
ה: נגדיר פונקציה [math]\displaystyle{ g=\mathbb{N}\to [0,1)=\{f:\mathbb{N}\to \{0,1\dots 9\}\} }[/math]
ע"י [math]\displaystyle{ \forall n\in \mathbb{N}:g(n)=e_n(m)=\delta_{n,m} }[/math] למשל 17 נשלח לפונקציה ששווה 0 בכל מקום פרט ל-17 ששם היא שווה 1
קל לראות כי g חח"ע.
כעת נניח בשלילה כי [math]\displaystyle{ \aleph_0=\aleph }[/math] אזי יש פונקציה חח"ע ועל [math]\displaystyle{ g=\mathbb{N}\to [0,1)=\{f:\mathbb{N}\to \{0,1\dots 9\}\} }[/math] נסמן [math]\displaystyle{ g(n)=f_n }[/math]. נראה כי g אינה על ע"י שנבנה פונקציה f שאין לה מקור:
נגדיר [math]\displaystyle{ f(n)=1 }[/math] אם [math]\displaystyle{ f_n(n)=0 }[/math] ו [math]\displaystyle{ f(n)=0 }[/math] אחרת. כעת לכל n [math]\displaystyle{ f_n\not=f }[/math] כי [math]\displaystyle{ f_n(n)\not=f(n) }[/math] עפ"י הגדרת f. סתירה לכל ש g על.
הערה: הזיהוי [math]\displaystyle{ [0,1)=\{f:\mathbb{N}\to \{0,1\dots 9\}\} }[/math] אינו מדויק כי [math]\displaystyle{ 0.01=0.00999... }[/math] ולכן צריך להשלח לאותה פונקציה. נשאיר כתרגיל את דיוק ההוכחה.
טענה. יהיו C,W קבוצות ויהיו [math]\displaystyle{ X,Y\subseteq W }[/math], [math]\displaystyle{ A,B\subseteq C }[/math] תתי קבוצות כך ש [math]\displaystyle{ A\cap B=X\cap Y=\phi }[/math] וגם [math]\displaystyle{ A\cup B = C }[/math] וגם [math]\displaystyle{ X\cup Y = W }[/math]. אזי אם קיימות פונקציות חח"ע ועל [math]\displaystyle{ g:B\rightarrow Y }[/math],[math]\displaystyle{ f:A\rightarrow X }[/math] מתקיים ש [math]\displaystyle{ |C|=|W| }[/math]
הוכחה:
לפי נתון קיימות 2 פונקציות חח"ע ועל [math]\displaystyle{ f_1:A\to X,\;\;f_2:B\to Y }[/math]
נגדיר [math]\displaystyle{ f:C\to W }[/math] ע"י [math]\displaystyle{ f|_A=f_1,\;\;f|_B=f_2 }[/math]. בידקו שאכן f חח"ע ועל.
תרגיל ממבחן.
א.(ב XI) יהיו A,B קבוצות כך ש [math]\displaystyle{ |A/B|=|B/A| }[/math]. הוכח ש [math]\displaystyle{ |A|=|B| }[/math].
ב. מצא קבוצות A וB כך ש [math]\displaystyle{ |A|=|B| }[/math] אבל [math]\displaystyle{ |A/B|\neq |B/A| }[/math].
פתרון.
א. מתקיים [math]\displaystyle{ A=(A\cap B)\cup A/B, \;\; B=(A\cap B)\cup B/A }[/math] לפי נתון [math]\displaystyle{ |A/B|=|B/A| }[/math]. כיוון ש [math]\displaystyle{ |A\cap B|=|A\cap B| }[/math] לפי תרגיל קודם סימנו.
ב. ניקח את הטבעיים, ואת הטבעיים לאחר שזרקנו מהם את אחד. ברור שנשארנו עם קבוצות שוות עוצמה, אבל ההפרשים בינהם הם [math]\displaystyle{ \{1\},\phi }[/math] ואלו קבוצות מעוצמה שונה.
תרגילי העשרה (לא מומלץ להעביר בתירגול)
תרגיל.
נגדיר "שמיניה" בתור זוג מעגלים בגדלים כלשהם המשיקים זה לזה בנקודה כלשהי. יהי אוסף אינסופי כלשהו של שמיניות במישור הזרות זו מזו (כלומר אין שתים עם נקודת חיתוך משותפת)
א. הוכח שעוצמת קבוצה זו הינה אלף אפס
ב. הוכח שקיימת קבוצה של אינסוף מעגלים במרחב ללא חיתוך מעוצמת אלף
פתרון.
א. בהנתן שמיניה מסוימת באוסף, נבחר נקודה רציונאלית אחת ממעגל אחד, ואחת מהמעגל השני. זה נותן לנו פונקציה מהאוסף אל הזוגות הסדורים של מספרים רציונאליים.
כעת, נוכיח כי פונקציה זו הינה חח"ע. נניח בשלילה כי לשתי שמיניות שונות יש נקודות משותפים בשני המעגלים. אם כן, המעגל של האחת נמצא במעגל של האחרת ולכן גם נקודת ההשקה נמצאת בתוך המעגל האחד. מכיוון שהמעגל השני מכיל נקודה משותפת עם המעגל השני של השמיניה השנייה, חייב להיות חיתוך בינהם בסתירה (ציור פה יקל ממש על ההבנה שלכם...).
לכן עוצמת האוסף קטנה מעוצמת הזוגות הסדורים של הרציונאליים, ולמדנו שזוגות סדורים של קבוצה בת מנייה היא קבוצה בת מנייה. לכן עוצמת האוסף קטנה מבת מנייה אבל מכיוון שהיא אינסופית היא גדולה מבת מנייה ולכן בת מנייה כדרוש.
ב. ניקח את אוסף המעגלים עם מרכז בראשית ורדיוס ממשי חיובי. אין בינהם חיתוך, והכמות שלהם זהה לחצי ציר הממשיים והוא כמובן מעוצמת אלף.