תרגול 14 תשעח: הבדלים בין גרסאות בדף
(יצירת דף עם התוכן "=== תרגיל === הוכיחו כי <math>|P(\mathbb{N})|=|P(\mathbb{N})-\{\emptyset\}|</math> ==== פתרון ==== נגדיר פונקציה <math>f:P(\mathbb...") |
(←תרגיל) |
||
| (2 גרסאות ביניים של 2 משתמשים אינן מוצגות) | |||
| שורה 1: | שורה 1: | ||
חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]]. | |||
=עוצמות= | |||
'''הגדרה.''' יהיו <math>A,B</math> שתי קבוצות. אזי: | |||
*אם קיימת <math>f:A\to B </math> חח"ע ועל אז אומרים של-<math>A</math> ול-<math>B</math> '''יש אותה עוצמה'''. סימון <math>|A|=|B|</math>. | |||
*אם קיימת <math>f:A\to B </math> חח"ע אז אומרים כי העוצמה של <math>A</math> קטנה או שווה לזו של <math>B</math>. סימון <math>|A|\leq|B|</math>. | |||
* אם <math>|A|\leq|B|</math> וגם <math>|A|\not=|B|</math> אזי אומרים כי העוצמה של <math>A</math> קטנה ממש מהעוצמה של <math>B</math>. סימון <math>|A|<|B|</math>. | |||
הערה: בעזרת אקסיומת הבחירה מוכיחים כי אם קיימת <math>f:A\to B </math> על אזי <math>|B|\leq |A|</math>. | |||
=== תרגיל === | === תרגיל === | ||
הוכיחו כי <math>|P(\mathbb{N})|=|P(\mathbb{N})-\{\ | הוכיחו כי <math>|P(\mathbb{N})|=|P(\mathbb{N})-\{\varnothing\}|</math>. | ||
==== פתרון ==== | ==== פתרון ==== | ||
נגדיר פונקציה <math>f:P(\mathbb{N})\to P(\mathbb{N})-\{\ | נגדיר פונקציה <math>f:P(\mathbb{N})\to P(\mathbb{N})-\{\varnothing\} </math> ע"י <math>\{n\}\mapsto \{n+1\},\varnothing \mapsto \{1\}</math> וכל <math>B</math> שאינה נקודון ואינה הקבוצה הריקה נשלח לעצמה. | ||
הפיכה כי יש לה הופכית: <math>f^{-1}:P(\mathbb{N})-\{\varnothing\}\to P(\mathbb{N})</math> ע"י <math>\{1\}\mapsto \varnothing,\{n\geq 2\}\mapsto \{n-1\}</math> וכל <math>B</math> שאינה נקודון נשלחת לעצמה. | |||
===תרגיל === | ===תרגיל === | ||
הוכיחו כי <math>|A\times A| = |A^{\{1,2\}}|</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>F:A^{\{1,2\}}\to A\times A</math> המוגדרת <math>f\mapsto (f(1),f(2))</math> הפיכה. | ||
=== | חח"ע: נניח <math>F(f)=F(g)</math> לכן <math>(f(1),f(2))=(g(1),g(2))</math>, ולכן <math>f(1)=g(1)\land f(2)=g(2)</math> וזו אותה פונקציה. | ||
על: יהי <math>(a,b)\in A\times A</math>, הפונקציה שמוגדרת ע"י <math>1\mapsto a,2\mapsto b</math> היא מקור. | |||
אם <math>|B|\leq|A|</math> וגם <math>|A|\leq|B|</math> אז <math>|B|=|A|</math> | ===משפט (קנטור-שרדר-ברנשטיין)=== | ||
אם <math>|B|\leq|A|</math> וגם <math>|A|\leq|B|</math> אז <math>|B|=|A|</math>. | |||
בהמשך נקצר לק.ש.ב. | |||
===תרגיל=== | ===תרגיל=== | ||
הוכיחו: <math>|\mathbb{Q}\cap [0,1]|=\aleph_0</math> | הוכיחו: <math>|\mathbb{Q}\cap [0,1]|=\aleph_0</math>. | ||
====פתרון==== | ====פתרון==== | ||
לפי ק.ש.ב. כי | לפי ק.ש.ב. כי הקבוצה מוכלת ברציונליים ומכילה <math>\aleph_0</math> שברים מהצורה <math>\frac{1}{n}</math>. | ||
===תרגיל=== | ===תרגיל=== | ||
הוכיחו כי עוצמת כל הקבוצות הבאות שווה - כל קטעים מהצורה <math>[a,b],(a,b),[a,b),(a,b]</math> כאשר <math>a<b</math> ממשיים. | |||
====פתרון==== | ====פתרון==== | ||
| שורה 29: | שורה 47: | ||
נראה שכולם שווי עוצמה לקטע <math>(0,1)</math>. | נראה שכולם שווי עוצמה לקטע <math>(0,1)</math>. | ||
ראשית נגדיר <math>f:(0,1)\rightarrow (a,b)</math> ע"י | ראשית נגדיר <math>f:(0,1)\rightarrow (a,b)</math> ע"י <math>f(x)=a+(b-a)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> הפיכה בתחום הזה ולכן חח"ע ועל. | |||
===תרגיל === | ===תרגיל === | ||
תהא A קבוצה. | תהא <math>A</math> קבוצה. הוכיחו כי <math>|A|\leq |P(A)|</math>. | ||
פתרון: נגדיר את הפונקציה <math>f:A|\to P(A)</math> ע"י <math>a \mapsto \{a\}</math> | פתרון: נגדיר את הפונקציה <math>f:A|\to P(A)</math> ע"י <math>a \mapsto \{a\}</math> והיא חח"ע. | ||
תהא A קבוצה. | תהא <math>A</math> קבוצה. הוכיחו כי <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)= | פתרון: נניח בשלילה כי <math>|A|= |P(A)|</math> אזי קיימת <math>f: A\to P(A)</math> הפיכה, בפרט על. נגדיר <math>X=\{a\in A: a\notin f(a)\}</math>. זוהי תת קבוצה של <math>A</math> ולכן, מכיוון ש-<math>f</math> על, קיים <math>x\in A</math> כך ש-<math>f(x)=X</math>. האם <math>x\in X</math>? אם לא, לפי הגדרת <math>X</math> נקבל כי <math>x\notin f(x)=X</math>, סתירה. אם כן אז <math>x\in X=f(x)</math> אבל לפי הגדרת <math>X</math> מתקיים <math>x\notin f(x)</math> סתירה. מש"ל. | ||
גרסה אחרונה מ־08:18, 21 בינואר 2018
חזרה לדף מערכי התרגול.
עוצמות
הגדרה. יהיו [math]\displaystyle{ A,B }[/math] שתי קבוצות. אזי:
- אם קיימת [math]\displaystyle{ f:A\to B }[/math] חח"ע ועל אז אומרים של-[math]\displaystyle{ A }[/math] ול-[math]\displaystyle{ B }[/math] יש אותה עוצמה. סימון [math]\displaystyle{ |A|=|B| }[/math].
- אם קיימת [math]\displaystyle{ f:A\to B }[/math] חח"ע אז אומרים כי העוצמה של [math]\displaystyle{ A }[/math] קטנה או שווה לזו של [math]\displaystyle{ B }[/math]. סימון [math]\displaystyle{ |A|\leq|B| }[/math].
- אם [math]\displaystyle{ |A|\leq|B| }[/math] וגם [math]\displaystyle{ |A|\not=|B| }[/math] אזי אומרים כי העוצמה של [math]\displaystyle{ A }[/math] קטנה ממש מהעוצמה של [math]\displaystyle{ B }[/math]. סימון [math]\displaystyle{ |A|\lt |B| }[/math].
הערה: בעזרת אקסיומת הבחירה מוכיחים כי אם קיימת [math]\displaystyle{ f:A\to B }[/math] על אזי [math]\displaystyle{ |B|\leq |A| }[/math].
תרגיל
הוכיחו כי [math]\displaystyle{ |P(\mathbb{N})|=|P(\mathbb{N})-\{\varnothing\}| }[/math].
פתרון
נגדיר פונקציה [math]\displaystyle{ f:P(\mathbb{N})\to P(\mathbb{N})-\{\varnothing\} }[/math] ע"י [math]\displaystyle{ \{n\}\mapsto \{n+1\},\varnothing \mapsto \{1\} }[/math] וכל [math]\displaystyle{ B }[/math] שאינה נקודון ואינה הקבוצה הריקה נשלח לעצמה.
הפיכה כי יש לה הופכית: [math]\displaystyle{ f^{-1}:P(\mathbb{N})-\{\varnothing\}\to P(\mathbb{N}) }[/math] ע"י [math]\displaystyle{ \{1\}\mapsto \varnothing,\{n\geq 2\}\mapsto \{n-1\} }[/math] וכל [math]\displaystyle{ B }[/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{ F(f)=F(g) }[/math] לכן [math]\displaystyle{ (f(1),f(2))=(g(1),g(2)) }[/math], ולכן [math]\displaystyle{ f(1)=g(1)\land f(2)=g(2) }[/math] וזו אותה פונקציה.
על: יהי [math]\displaystyle{ (a,b)\in A\times A }[/math], הפונקציה שמוגדרת ע"י [math]\displaystyle{ 1\mapsto a,2\mapsto b }[/math] היא מקור.
משפט (קנטור-שרדר-ברנשטיין)
אם [math]\displaystyle{ |B|\leq|A| }[/math] וגם [math]\displaystyle{ |A|\leq|B| }[/math] אז [math]\displaystyle{ |B|=|A| }[/math].
בהמשך נקצר לק.ש.ב.
תרגיל
הוכיחו: [math]\displaystyle{ |\mathbb{Q}\cap [0,1]|=\aleph_0 }[/math].
פתרון
לפי ק.ש.ב. כי הקבוצה מוכלת ברציונליים ומכילה [math]\displaystyle{ \aleph_0 }[/math] שברים מהצורה [math]\displaystyle{ \frac{1}{n} }[/math].
תרגיל
הוכיחו כי עוצמת כל הקבוצות הבאות שווה - כל קטעים מהצורה [math]\displaystyle{ [a,b],(a,b),[a,b),(a,b] }[/math] כאשר [math]\displaystyle{ a\lt b }[/math] ממשיים.
פתרון
נראה שכולם שווי עוצמה לקטע [math]\displaystyle{ (0,1) }[/math].
ראשית נגדיר [math]\displaystyle{ f:(0,1)\rightarrow (a,b) }[/math] ע"י [math]\displaystyle{ f(x)=a+(b-a)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{ A }[/math] קבוצה. הוכיחו כי [math]\displaystyle{ |A|\leq |P(A)| }[/math].
פתרון: נגדיר את הפונקציה [math]\displaystyle{ f:A|\to P(A) }[/math] ע"י [math]\displaystyle{ a \mapsto \{a\} }[/math] והיא חח"ע.
תהא [math]\displaystyle{ A }[/math] קבוצה. הוכיחו כי [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]. זוהי תת קבוצה של [math]\displaystyle{ A }[/math] ולכן, מכיוון ש-[math]\displaystyle{ f }[/math] על, קיים [math]\displaystyle{ x\in A }[/math] כך ש-[math]\displaystyle{ f(x)=X }[/math]. האם [math]\displaystyle{ x\in X }[/math]? אם לא, לפי הגדרת [math]\displaystyle{ X }[/math] נקבל כי [math]\displaystyle{ x\notin f(x)=X }[/math], סתירה. אם כן אז [math]\displaystyle{ x\in X=f(x) }[/math] אבל לפי הגדרת [math]\displaystyle{ X }[/math] מתקיים [math]\displaystyle{ x\notin f(x) }[/math] סתירה. מש"ל.