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

מתוך Math-Wiki
 
(78 גרסאות ביניים של 8 משתמשים אינן מוצגות)
שורה 1: שורה 1:
'''[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור|חזרה למערכי התרגול]]'''
'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''


==אריתמטיקה של עוצמות==
==אריתמטיקה של עוצמות==
'''תרגיל.''' יהיו A,B קבוצות כך ש, עוצמת B גדולה מאחד. הוכח כי העוצמה של אוסף הפונקציות מA לB גדולה מעוצמת A.


'''פתרון.'''
'''הגדרה''' יהיו A,B קבוצות אזי <math>A^B:=\{f:B\rightarrow A\}</math>.
 
===תרגיל===
יהיו A,B,C קבוצות כך ש <math>|A|\leq |B|</math>. הוכיחו כי <math>|A^C|\leq|B^C|</math>.
פתרון: נתון שקיימת <math>f:A\to B</math> חח"ע. נגדיר <math>g:A^C\to B^C</math> ע"י <math>h:C\to A\mapsto f\circ h</math>. מתקיים כי g חח"ע כי f חח"ע ויש לה הפיכה שמאלית.
 
הערה: <math>|A|< |B|</math> '''לא''' גורר <math>|A^C|<|B^C|</math>.
 
 
 
===תרגיל===
הוכח שעוצמת קבוצת החזקה של A תמיד גדולה מעוצמתה של A


קל לבנות פונקציה על מאוסף הפונקציות מA לB אל A. נשלח כל פונקציה באוסף למקור של איבר b מסוים. מכיוון שכל הפונקציות מA לB נמצאות באוסף, בפרט כל הפונקציות ששולחות כל איבר מA ל-b יהיו שם.
'''הוכחה.'''
יש התאמה חח"ע ועל <math>g:P(A)\to \{0,1\}^A</math> ע"י
<math>\forall B\subseteq A : g(B)=f_B=\chi_B</math> 


נניח בשלילה שקיימת התאמה חח"ע ועל בין A לבין אוסף הפונקציות הנ"ל. נסמן ב<math>f_a:A\rightarrow B</math> את הפונקציה המתאימה לאיבר <math>a\in A</math>.
לפי תרגיל קודם <math>|A|<|\{0,1\}^A|=|P(A)|</math>


ידוע לנו שבקבוצה B יש לפחות שני איברים, לכן בהנתן אחד מהם אפשר לבחור את השני. נגדיר פונקציה באופן הבא <math>\forall a\in A : g(a)\neq g_a(a)</math>. לפי ההגדרות פונקציה זו הינה פונקציה מA לB אך אינה מתאימה לאף איבר בA בסתירה.
'''הערה: (למי שלמד תורת הקבוצות)''' מסיבה זו אוסף העוצמות אינו קבוצה אלא מחלקה. שכן אם הוא היה קבוצה, הייתה לו עוצמה


===תרגיל===
יהיו A,B קבוצות כך ש <math>|B|>1</math>. הוכח כי <math>|A|<|B^A|</math>.


'''תרגיל.''' הוכח שעוצמת קבוצת החזקה של A תמיד גדולה מעוצמתה של A
'''פתרון.'''
נבחר 2 איברים שונים <math>b_0,b_1\in B</math> ונגדיר פונקציה חח"ע <math>g:A\to B^A</math> ע"י <math>g(a)=f_a</math> כאשר <math>f_a(a)=b_1</math> ו <math>\forall a'\not=a :f_a(a')=b_0</math>
ולכן <math>|A|\leq|B^A|</math>.


'''הוכחה.''' קל להראות שקיימת העתקה חח"ע ועל בין אוסף הפונקציות <math>f:A\rightarrow \{0,1\}</math> (כל קבוצה חלקית אומרת בעצם על כל איבר של A אם הוא שייך (1) או לא שייך (0). למשל הפונקציה המתאימה לקבוצה הריקה היא פונקצית האפס, והפונקציה המתאימה לקבוצה כולה היא הפונקציה 1).
נניח בשלילה שקיים שיוויון אזי קיימת  התאמה חח"ע ועל <math>g:A\to B^A</math>.
נסמן <math>\forall a\in A:g(a)=f_a</math>.


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


'''הערה:''' מסיבה זו אוסף העוצמות אינו קבוצה אלא מחלקה. שכן אם הוא היה קבוצה, הייתה לו עוצמה
נבחר 2 איברים שונים <math>b_0,b_1\in B</math>ונגדיר פונקציה באופן הבא <math>f:A\rightarrow B</math> ע"י
<math>f(a)=b_0</math> אם <math>f_a(a)=b_1</math>. ו- <math>f(a)=b_1</math> אחרת.
לפי הבנייה <math>\forall a\in A f\not=f_a</math> כיוון ש <math>f(a)\not=f_a(a)</math>. סתירה לכך ש g על.
 
הערה: התרגיל הזה הוא מסקנה מהתרגילים הקודמים כי <math>|\{0,1\}|\leq |B|</math> ולכן <math>|A|<|\{0,1\}^A|\leq |B^A|</math>


'''הגדרה:'''
'''הגדרה:'''
שורה 27: שורה 49:
*<math>a^b := |\{f:B\rightarrow A\}|</math>
*<math>a^b := |\{f:B\rightarrow A\}|</math>


בהרצאה תוכיחו שהגדרות אלה מוגדרות היטב, כלומר העוצמה נשארת זהה ללא תלות בבחירת הקבוצות המייצגות.
דוגמא: ראינו בתירגול קודם את הזיהוי <math>[0,1)=\{f:\mathbb{N} \to \{0,1,...9\}\}</math>
לכן <math>\aleph=|\mathbb{R}|=|[0,1)|=|\{f:\mathbb{N} \to \{0,1,...9\}\}|=10^{\aleph_0}</math>


'''שימו לב:''' מתוך הגדרה זו קל לראות את חוקי החזקות למקרי הקצה:  
הערות:
*<math>a^0=1</math> שכן יש פונקציה יחידה מהקבוצה הריקה לכל מקום - היחס שהוא הקבוצה הריקה.
*ההגדרות לעיל מוגדרות היטב, כלומר העוצמה נשארת זהה ללא תלות בבחירת הקבוצות המייצגות.
*<math>0^0=1</math> זה מקרה פרטי של הסעיף הקודם, ועדיין מתקיים
* בידקו שעבור המקרה הסופי מתקיים מה שמצופה.
*<math>a\neq 0 \rightarrow 0^a=0</math> אין אף פונקציה מקבוצה לא ריקה אל קבוצה ריקה, שכן יחס כזה לא יכול להיות שלם.
למשל <math>2+1=|\{1,2\}\cup\{3\}|=3</math>
*'''שימו לב:''' מתוך הגדרה זו קל לראות את חוקי החזקות למקרי הקצה:  
**<math>a^0=1</math> שכן יש פונקציה יחידה מהקבוצה הריקה לכל מקום - היחס שהוא הקבוצה הריקה.
**<math>0^0=1</math> זה מקרה פרטי של הסעיף הקודם, ועדיין מתקיים
**<math>1^a=1</math>
**<math>a\neq 0 \rightarrow 0^a=0</math> אין אף פונקציה מקבוצה לא ריקה אל קבוצה ריקה, שכן יחס כזה לא יכול להיות שלם.


===תכונות האריתמטיקה===
יהיו a,b,c עוצמות אזי מתקיים
*<math>ab=ba</math>
*<math>(ab)c=a(bc)</math>
*<math>a^ba^c=a^{b+c}</math>
*<math>a^cb^c=(ab)^c</math>
*<math>(a^b)^c=a^{bc}</math>
כלומר מתקיימים חוקי החזקות ה"רגילים"


===תכונות האריתמטיקה===
בהנחת אקסיומת הבחירה:


*אם a או b מייצגים עוצמה אינסופית אזי <math>a+b=max\{a,b\}</math>
נוכיח למשל <math>a^ba^c=a^{b+c}</math> יהיו <math>|A|=a,|B|=b,|C|=c</math> קבוצות זרות
*אם a או b מייצגים עוצמה אינוספית ושניהם אינם אפס אזי <math>a\cdot b=max\{a,b\}</math>
נגדיר פונקציה מ <math>A^{B\cup C} \to A^B\times A^C</math> ע"י <math>f \mapsto (f|_B,f|_C)</math>. היא חח"ע ועל.
*אם <math>2\leq a</math> ו <math>1\leq b</math> ולפחות אחת מבינהם הוא אינסופי אזי <math>max\{a,2^b\}\leq a^b \leq max\{2^a,2^b\}</math>
 
**מסקנה: אם <math>2\leq a \leq b</math> אזי <math>a^b=2^b</math>
נוכיח למשל <math>(a^b)^c=a^{bc}</math> יהיו <math>|A|=a,|B|=b,|C|=c</math> קבוצות זרות
נגדיר פונקציה מ <math>(A^B)^C \to A^{B\times C} </math> ע"י <math>f \mapsto g(b,c)= f(c)(b)</math>. היא חח"ע ועל.
 
 
בנוסף אם מניחים את אקסיומת הבחירה אזי מתקיים עבור a,b עוצמות כאשר אחד מהם אין סופי
 
* <math>a+b=max\{a,b\}</math>
*אם שניהם אינם אפס אזי <math>a\cdot b=max\{a,b\}</math>
*מסקנה: אם <math>2\leq a \leq b</math> אזי <math>a^b=2^b</math>
 
הוכחה <math>2^b\leq a^b\leq (2^a)^b=2^{ab}=2^b</math>
 
===תרגיל===
הוכח כי <math>\aleph_0+\aleph=\aleph</math>
 
הוכחה: דרך א- ישירות מהגדרה. נבחר <math>A=[\frac{1}{4},\frac{1}{2}],B=\mathbb{N}</math> אזי  
<math>\aleph=|A|\leq |A\cup B |\leq |\mathbb {R}|=\aleph</math>
 
דרך ב- מהנוסחא. <math>\aleph_0+\aleph=max\{\aleph_0,\aleph\}=\aleph </math>
 
===תרגיל===
הוכח כי <math>\aleph \cdot \aleph=\aleph </math>
 
הוכחה:  <math>\aleph=|\{f:\mathbb{N}\to \{ 0,1\dots 9 \} \}|=10^{\aleph_0}=2^{\aleph_0}</math>
 
דרך א- ישירות מהגדרה. נבחר <math>A=\{f:\mathbb{N}\to \{0,1\dots 9\}\},B=A\times A</math> אזי
נגדיר פונקציה <math>A\to A\times A</math> ע"י <math>f(n)\mapsto (f(2n),f(2n+1))</math> . זו פונקציה חח" ועל.
 
דרך ב- אריתמטיקה-
<math>\aleph \cdot \aleph=2^{\aleph_0}\cdot 2^{\aleph_0}=2^{\aleph_0+\aleph_0}=2^{\aleph_0}=\aleph </math>
 
דרך ג- מהנוסחא- <math>\aleph \cdot \aleph=max\{\aleph,\aleph\}=\aleph </math>
 
===תרגיל===
 
הוכח כי <math>|\mathbb{R}\backslash \mathbb{Q}|=\aleph</math>
 
פתרון:
 
כיוון ש <math>\mathbb{R}\backslash \mathbb{Q}</math> מוכל בממשיים עוצמתה לכל היותר אלף. נניח בשלילה כי עוצמתה שווה a קטנה ממש מאלף אזי
<math>\aleph=|\mathbb{R}|=|\mathbb{R}\backslash \mathbb{Q}|+|\mathbb{Q}|=a+\aleph_0=a<\aleph</math>. סתירה
 
=== תרגיל ===
חשבו את <math>\aleph^{\aleph_0},{\aleph_0}^{\aleph}</math>
 
פתרון: <math>\aleph^{\aleph_0}=\aleph,{\aleph_0}^{\aleph}=2^{\aleph}</math>
 
הסיקו כי עוצמת קבוצת הפונקציות מהרציונאלים לממשיים היא <math>\aleph</math>.
 
===תרגיל===
תהא <math>A</math> קבוצה אינסופית ו <math>B\subseteq A</math> תת קבוצה.
 
הוכח/הפרך
 
1. <math>|A\backslash B|=|A|\Rightarrow |B|<|A|</math>
 
2. <math>|A\backslash B|=|A|\Leftarrow |B|<|A|</math>
 
פתרון:
 
1. הפרכה: ניקח את השלמים והטבעיים
 
2. נכון כי ניתן להציג A כאיחוד זר <math>A=A\backslash B \cup B</math>
ולכן <math>|A|=|A\backslash B| + |B|</math>. אם <math>|A\backslash B|<|A|</math> נקבל סתירה
 
=== תרגיל ===
1. מה עוצמת <math>\mathbb{N}^\mathbb{N}</math>
 
פתרון: <math>\aleph_0^{\aleph_0} =2^{\aleph_0} </math>
 
2. מה עוצמת <math>X=\{f\in \mathbb{N}^\mathbb{N}:f(1)\leq f(2)\}</math>
 
פתרון: לכל היותר <math>\mathbb{N}^\mathbb{N}</math> ולכל הפחות <math>\mathbb{N}^\mathbb{N}</math>
כי לכל <math>g\in \mathbb{N}^{\mathbb{N}\setminus \{1,2\}}</math> נתאים <math>f\in X</math> ע"י <math>f(1)=f(2)=1 </math> ועבור <math>x\neq 1,2</math> נגדיר <math>f(x)=g(x)</math> ולכן <math>|\mathbb{N}^{\mathbb{N}\setminus \{1,2\}}|\leq|X|\leq |\mathbb{N}^\mathbb{N}|</math> ולפי ק.ש.ב יש שיווון
 
3. מה עוצמת <math>X=\{f\in \mathbb{R}^\mathbb{R}:\forall x\notin \mathbb{Q} f(x)=1\}</math>
 
פתרון: X שווה עוצמה ל <math>\mathbb{R}^{\mathbb{Q}}</math> כי <math>g\in\mathbb{R}^{\mathbb{Q}}</math> ממופה ל <math>f\in X</math> המוגדרת <math>f|_{\mathbb{Q}}=g,f|_{\mathbb{R}\setminus\mathbb{Q}}=1</math>
 
=== תרגיל ===
תהי <math>\{A_i\}_{i\in I}</math> משפחה של קבוצות הזרות זו לזו כך שעוצמת  כל אחת מהן ב<math>a</math>. נגדיר <math>\sum_{i\in I} a = |\bigcup_{i\in I}A_i|</math>.
הוכח כי <math>\sum_{i\in I} a = |I|\cdot a</math>
 
פתרון:
 
תהא <math>A</math> קבוצה  נוספת  מעוצמה <math>a</math>.
לכל <math>i\in I</math> קיימת פונקציה חח"ע ועל
<math>f_i:A\rightarrow A_i</math>.
כעת נגדיר פונקציה <math>g:I\times A\rightarrow\bigcup_{i\in I}A_i</math> ע"י <math>g(k,x)=f_k(x)</math>. מכיוון שהקבוצות זרות ו<math>f_k</math> חח"ע ברור שg חח"ע. מכיוון ש<math>f_k</math> על גם g על ולכן קיבלנו את המבוקש.
 
=== תרגיל ===
נגדיר <math>F</math> להיות אוסף תתי הקבוצות הסופיות של הטבעיים <math>F=\{X\subseteq \mathbb{N}:|X|<\aleph_0\}</math>. מה עוצמתה?
 
פתרון: לכל <math>i\in \mathbb{N}</math> נגדיר <math>F_i=\{X\subseteq \mathbb{N}:|X|=i\}</math> (אוסף תתי הקבוצות מגודל <math>i</math>). אזי <math>|F_i|\leq \aleph_0^i=\aleph_0</math>
ואז <math>|F|=|\cup_{i\in \mathbb{N}}F_i|\leq \aleph_0\cdot \aleph_0 =\aleph_0</math>
 
=== תרגיל (בש.ב.)===
נגדיר <math>A</math> להיות אוסף תתי הקבוצות האינסופיות של הטבעיים. מה עוצמתה?
 
פתרון: מתקיים כי <math>P(\mathbb{N})=A\cup A^c</math> כאשר A היא תתי הקבוצות הסופיות מתרגיל קודם שעוצמת <math>\aleph_0</math>
ולכן <math>2^{\aleph_0}=\aleph_0+|A^c|=\max\{\aleph_0,|A^c|\}=|A^c|</math>
 
=== תרגיל ===
נגדיר <math>A=\{X\subseteq \mathbb{R}: |X|=\aleph_0 \}</math> ,מה עוצמתה?
 
פתרון: לכל הפחות <math>2^{\aleph_0}</math> כי תתי הקבוצות האינסופיות של הטבעיים מעוצמה זאת. בצד שני נגדיר <math>F:\mathbb{R}^{\mathbb{N}}\to P(\mathbb{R})</math> ע"י
<math>f\mapsto Im(f)</math> טענה: <math>A\subseteq Im(F)</math> הוכחה: תהא <math>X\in A</math> ומהגדרת A, נסיק כי X מעוצמה הטבעיים ולכן קיימת <math>f:\mathbb{N}\to X</math> חח"ע ועל ולכן <math>F(f)=Im(f)=X</math>. מסקנה מכך <math>|A|\leq |Im(F)|\leq |\mathbb{R}^{\mathbb{N}}|=\aleph^{\aleph_0}=\aleph</math>. לפי ק.ש.ב <math>|A|=2^{\aleph_0}=\aleph</math>
 
=== תרגיל ===
 
נגדיר <math>A=\{X\subseteq \mathbb{R}: |X|=\aleph \}</math> ,מה עוצמתה?


פתרון: לכל היותר <math>2^\aleph</math> מצד שני <math>F:P((0,1))\to A </math>  המוגדרת <math>B\mapsto B\cup (1,2)</math> חח"ע ולפי ק.ש.ב. סימנו


'''תרגיל ממבחן תשסח מועד א''' (ד"ר שי סרוסי וד"ר אלי בגנו)
===תרגיל ממבחן תשסח מועד א (ד"ר שי סרוסי וד"ר אלי בגנו) ===


תהי A קבוצה אינסופית. נסמן <math>|A|=a,B=\{X|X\subseteq A\}, C=\{f|f:A\rightarrow P(A)\},F=\{(a,X)|(a\in A) \and (X\subseteq A)\},H=\{f|f:B\rightarrow B\}</math>
תהי A קבוצה אינסופית. נסמן <math>a=|A|,\;B=P(A),\;F=A\times P(A),\; C=P(A)^A,\; H=B^B</math>


:א. מצא את <math>|C|</math>
:א. מצא את <math>|C|</math>
שורה 54: שורה 199:


'''פתרון.'''
'''פתרון.'''
א. <math>|C|=(2^a)^a=2^{aa}=2^a</math>
ב.<math>|F\times H|=|F||H|=a2^a(2^a)^{2^a}=2^{a2^a}=2^{2^a}</math>
ג. כל יחס שקילות שקבוצת המנה 2 מתאים לחלוקה של <math>\mathbb{N}</math> ל-2 קבוצות זרות.
ולכן יש התאמה חח"ע ועל <math>\{R:|\mathbb{N}/R|=2\} \leftrightarrow W=\{\{A,A^c\}|A\subseteq \mathbb{N}\}</math> ולכן 2 הקבוצות מאותה עוצמה.
ט: <math>|W|=2^{\aleph_0}</math>
ה: נסמן <math>|W|=a</math>. בנוסף <math>\bigcup_{\{A,A^c\}\in W}\{A,A^c\}=P(\mathbb{N})</math>
ולכן <math>2^{\aleph_0}=|P(\mathbb{N})|=2a=a</math>.
=== תרגיל ===
נגדיר <math>X=\left\{ 0,1\right\} ^{\mathbb{N}}</math> קבוצת כל הסדרות הבינאריות. נגדיר יחס <math>\sim</math> על <math>X</math> כך <math>f\sim g</math> אמ"מ הקבוצה<math>\left\{ n\in\mathbb{N}\mid f(n)\neq g(n)\right\}</math>  סופית
הוכיחו כי <math>\sim</math> יח"ש
לכל <math>f\in X</math>, מצאו את העוצמה של <math>[f]</math>.
מצאו את העוצמה של קבוצת המנה.
=== תרגיל ===
תהא <math>X\subseteq P(\mathbb{N})</math>.
מצאו <math>X</math> המקיימת: כל <math>A,B\in X</math> שונות הן זרות (כלומר <math>A\cap B=\emptyset</math>).
ניח <math>X</math> מקיימת: כל <math>A,B\in X</math> שונות הן זרות. הוכיחו כי <math>X</math> בת מנייה.


תהא <math>C\subseteq\mathbb{N}</math>. נניח <math>X</math> מקיימת: החיתוך של <math>A,B\in X</math> שונות הוא <math>C</math> (כלומר <math>A\cap B=C</math>). הוכיחו כי <math>X</math> בת מנייה.


נניח <math>X</math> מקיימת: החיתוך של <math>A,B\in X</math> שונות הוא  לכל היותר בן 10 איברים (כלומר <math>\left|A\cap B\right|\leq10</math> ). הוכיחו כי <math>X</math> בת מנייה.רמז: <math>\cup_{B\in I}X_{B}</math> כאשר <math>I=\left\{ B\subseteq\mathbb{N}\mid\left|B\right|=10\right\}</math>  ו <math>X_{B}=\left\{ S\in X\mid B\subseteq S\right\}</math>


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


יהי S יחס על <math>\mathbb{R}^\mathbb{R}</math> (קבוצת כל הפונקציות הממשיות), המוגדר על ידי <math>(f,g)\in S</math> אם"ם לכל <math>x\in\mathbb{R}</math> מתקיים <math>f(x)-g(x)\in\mathbb{Z}</math>
יהי S יחס על <math>\mathbb{R}^\mathbb{R}</math> (קבוצת כל הפונקציות הממשיות), המוגדר על ידי <math>(f,g)\in S</math> אם"ם לכל <math>x\in\mathbb{R}</math> מתקיים <math>f(x)-g(x)\in\mathbb{Z}</math>


:1. הוכיחו שS הינו יחס שקילות
:1. הוכיחו ש S הינו יחס שקילות


:2. תהי <math>f\in\mathbb{R}^\mathbb{R}</math> מצאו את <math>|[f]|</math>
:2. תהי <math>f\in\mathbb{R}^\mathbb{R}</math> מצאו את <math>|[f]|</math>
שורה 77: שורה 251:
2.  
2.  


נביט במחלקת השקילות של f ונראה שיש העתקה S חח"ע ועל ממנה לאוסף הפונקציות מהממשיים לשלמים.
עבור <math>[f]\in \mathbb{R}^\mathbb{R}/S </math>
נגדיר  <math>F:[f] \to \mathbb{Z}^{\mathbb{R}}</math>.
ע"י <math>F(g):=f-g </math> נראה כי היא מוגדרת,חח"ע ועל.


<math>S(g):=f-g</math>. לפי ההגדרה, <math>f-g\in\{h:\mathbb{R}\rightarrow\mathbb{Z}\}</math>. נוכיח ש-S חח"ע ועל.
מוגדרת: לפי ההגדרה של יחס השקילות אכן מתקיים <math>f-g\in \mathbb{Z}^{\mathbb{R}}</math>


נניח <math>S(g)=S(h)</math> לכן <math>\forall x\in\mathbb{R} f(x)-g(x)=f(x)-h(x)</math> ולכן h=g, זה מוכיח חח"ע.
נראה כי ל F קיימת הופכית. נגדיר  <math>G:  \mathbb{Z}^{\mathbb{R}} \to [f]</math>. ע"י  <math>G(h):=f-h </math>. הפונקציה מוגדרת היטב כי <math>f-(f-h)\in \mathbb{Z}^{\mathbb{R}}</math> וקל לוודא שזוהי ההופכית
 
נוכיח על: תהי h פונקציה כלשהי מהממשיים לשלמים, ברור שf-h במחלקת השקילות של f.
חח"ע: נניח <math>F(g)=F(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>
אם כך, העוצמה של מחלקת השקילות זהה לעוצמה של אוסף הפונקציות מהממשיים לשלמים והוא <math>{\aleph_0}^\aleph</math>. לפי התכונות שלמדנו לעיל מתקיים <math>2^\aleph\leq{\aleph_0}^\aleph\leq 2^\aleph</math> ולכן לפי קנטור מתקיים <math>{\aleph_0}^\aleph=2^\aleph</math>
שורה 92: שורה 269:
נזכור בסימון <math>\lfloor x\rfloor</math> שהוא המספר השלם הגדול ביותר הקטן או שווה לx.
נזכור בסימון <math>\lfloor x\rfloor</math> שהוא המספר השלם הגדול ביותר הקטן או שווה לx.


נגדיר S פונקציה השולחת את <math>f\in\mathbb{R}^\mathbb{R}</math> לפונקציה <math>S(f):=f-\lfloor f\rfloor\in [0,1)^\mathbb{R}</math>. נראה ש-S מוגדרת היטב בהתחשב ביחס השקילות שלנו, ובנוסף שהפונקציה השולחת מחלקת שקילות ל-S של נציג כלשהו של המחלקה הינה חח"ע ועל.
נגדיר F פונקציה השולחת את <math>f\in\mathbb{R}^\mathbb{R}</math> לפונקציה <math>F(f):=f-\lfloor f\rfloor\in [0,1)^\mathbb{R}</math>. נראה ש-F מוגדרת היטב (על קבוצת המנה)וההפעלה שלה על קבוצת המנה תהיה חח"ע ועל.


יהיו שתי פונקציות באותה מחלקת שקילות g,f. אזי, <math>S(g)-S(f)=g-\lfloor g\rfloor -f + \lfloor f\rfloor</math>. מכיוון שזהו הפרש של שני מספרים אי שליליים קטנים מאחד, זה שווה למספר אי שלילי קטן מאחד. מכיוון שההפרש בין f ל-g שלם, המספר הזה הוא שלם. המספר השלם האי שלילי היחיד שקטן מאחד הינו אפס. לכן הפונקציה S מוגדרת היטב שכן היא שולחת נציגים שונים של מחלקת שקילות לאותו מקום.
מוגדרות: יהיו שתי פונקציות באותה מחלקת שקילות g,f. אזי, <math>F(g)-F(f)=g-\lfloor g\rfloor -f + \lfloor f\rfloor</math>. מכיוון שזהו הפרש של שני מספרים אי שליליים קטנים מאחד, זה שווה למספר שבערכו המוחלט קטן מאחד. מכיוון שההפרש בין f ל-g שלם, המספר הזה הוא שלם. המספר השלם האי שלילי היחיד שקטן מאחד הינו אפס
כלומר <math>F(f)=F(g)</math>. לכן הפונקציה F מוגדרת היטב שכן היא שולחת נציגים שונים של מחלקת שקילות לאותו מקום.


נניח בשלילה ש-S אינה חח"ע, לכן <math>S(f)-S(g)=0</math> עבור נציגים ממחלקות שקילות '''שונות'''. אבל אז <math>f-g=\lfloor f\rfloor - \lfloor g\rfloor</math> ולכן הם נציגים של אותה מחלקת שקילות בסתירה.
חח"ע: נניח <math>F(f)=F(g)</math> אז <math>f-g=\lfloor f\rfloor - \lfloor g\rfloor</math>  
 
כיוון ש <math>\lfloor f\rfloor - \lfloor g\rfloor\in \mathbb{Z}^\mathbb{R} </math> אזי הם נציגים של אותה מחלקת שקילות כלומר <math>[f]=[g]</math>
ניקח פונקציה כלשהי r מהממשיים לקטע <math>[0,1)</math>. קל לראות ש <math>S[r]=r</math> שכן <math>\lfloor r \rfloor = 0</math>. לכן S הינה על.


על: ניקח פונקציה כלשהי r מהממשיים לקטע <math>[0,1)</math>. קל לראות ש <math>F[r]=r</math> שכן
<math>\lfloor r \rfloor = 0</math>. לכן r ישמש מקור ולכן F הינה על.


סה"כ קיבלנו שעוצמת קבוצת המנה שווה ל<math>\aleph^\aleph</math> וזה שווה ל<math>2^\aleph</math> לפי התכונות לעיל.
סה"כ קיבלנו שעוצמת קבוצת המנה שווה ל<math>\aleph^\aleph</math> וזה שווה ל<math>2^\aleph</math> לפי התכונות לעיל.


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


א. תהי A קבוצה אינסופית מעוצמה a.
א. תהי A קבוצה אינסופית מעוצמה a.


:1. נגדיר עבור <math>2\leq n\in\mathbb{N}</math> את הקבוצה הבאה: <math>Y=\{(X_1,...,X_n):n\in\mathbb{N}\and\Big[\bigcup_i X_i=A\Big] \and \Big[\forall i\neq j: X_i\cap X_j = \emptyset\Big]\}</math>. '''הוכח''' <math>|Y|=2^a</math>
:1. נגדיר עבור :
<math>X=\{(X_1,...,X_n):1<n\in\mathbb{N}\and\Big[\bigcup_i X_i=A\Big] \and \Big[\forall i\neq j: X_i\cap X_j = \emptyset\Big] \and \big[ \forall i X_i \neq \emptyset\big]\}</math>.


:2. מצא את <math>|\mathbb{N}\times Y|,|\mathbb{N}\cup Y|</math> וגם את <math>|Y|^{|\mathbb{N}|},|\mathbb{N}|^{|Y|}</math>
כלומר אוסף החלקות הסופיות הלא טרי' הסדורות של A
'''הוכח''' <math>|X|=2^a</math>
 
:2. מצא את <math>|\mathbb{N}\times X|,|\mathbb{N}\cup X|</math> וגם את <math>|X|^{|\mathbb{N}|},|\mathbb{N}|^{|X|}</math>




שורה 123: שורה 306:
:1.  
:1.  


נביט באוסף הפונקציות <math>X=\{f:A\rightarrow\mathbb{N}\}</math>. נגדיר <math>g:Y\rightarrow X</math> על ידי <math>g(y)(a)=k</math> אם <math>a\in X_k</math> בתוך ה-<math>n</math>-יה הסדורה y. נוכיח שזו פונקציה מוגדרת היטב וחח"ע.  
נביט באוסף הפונקציות <math>Y=\{f:A\rightarrow\mathbb{N}\}</math>. נגדיר <math>g:X\to Y</math>
על ידי לכל <math>x=(X_1,...,X_n)\in X</math>  
 
נשלח אותו ל <math>g(x)=f_x</math> המוגדר
<math>\forall a\in A :\; f_x(a)=k</math> כאשר <math>a\in X_k</math> כלומר שולחת איבר לאינדקס של הקבוצה שהוא נמצא בה בחלוקה.
 
נוכיח שהפונקציה מוגדרת וחח"ע.
 
מוגדרת: כיוון ש x הוא חלוקה של A אזי האיבר a יופיע ויופיע בדיוק באחת מהקבוצות.
 
חח"ע: נניח <math>(X_1,...,X_n)=x\neq x'=(X'_1,...,X'_m)</math>. אזי קיים <math>X_i\not=X'_i</math>, לכן קיים יהיה <math>a\in X_i/X'_i</math> (או להיפך) ואז <math>i=f_x(a)\not= f_{x'}(a)</math>
כלומר <math>g(x)\not=g(x') </math>
 
דרך 2- נגדיר פונקציה <math>g:X\to P(A)^{\mathbb{N}}</math> ע"י <math>g((X_1,...,X_n))(i) = \begin{cases}X_i & \text{if } 1\leq i \leq n \\ \emptyset & \text{if } n<i \end{cases} </math>


מוגדרת היטב: מכיוון שהקבוצות זרות ואיחודן שווה לA, האיבר a יופיע בדיוק באחת מהן.
קל לראות כי הפונקציה חח"ע ולכן <math> |X| \leq (2^{a})^{\aleph_0} = 2^{a\cdot \aleph_0} =2^a</math>


חח"ע: נניח <math>y_1\neq y_2</math>. אזי יש איזה שתי תתי קבוצות של A שונות ביניהם, לכן יהיה איזה a באחת מהן שלא בשני שישלח למספר טבעי שונה.
דרך 3- נציג את X כאיחוד זר <math>X=\cup_{1<n\in \mathbb {N}}Y_n</math> כאשר <math>Y_n</math> זה חלוקות סדורות של A עם n קבוצות. כעת לכל n קיימת פונקציה <math>g:Y_n \to P(A)^n</math>
המוגדרת <math>g((X_1,...,X_n))=X_1 \times \cdots \times X_n</math> קל לראות שהיא חח"ע ולכן <math>|Y_n|=|A|^n =|A|</math> ולכן <math>|X|\leq \sum_{1<n\in \mathbb {N}}|A|=|A|\cdot \aleph_0 =|A|</math>


כעת, קל למצוא פונקציה חח"ע מקבוצת החזקה של A ל-Y - נשלח כל תת קבוצה לזוג שמכיל אותה ואת המשלים שלה.
כעת, קל למצוא פונקציה חח"ע מקבוצת החזקה של A ל-X - נשלח כל תת קבוצה לזוג שמכיל אותה ואת המשלים שלה.


לכן <math>2^{|A|} \leq |Y| \leq |X| = \aleph_0^{|A|}</math>
לכן <math>2^{|A|} \leq |X| \leq |Y| = \aleph_0^{|A|}</math>, ולפי התכונות לעיל שני הקצוות שווים. לכן עוצמת X הינה <math>2^a</math>.
העוצמה של אוסף הפונקציות לעיל הינה <math>|\mathbb{N}|^{|A|}\leq 2^{|A|}</math>, וקבוצת החזקה הינה מעוצמה <math>2^{|A|}</math> ולכן סה"כ עוצמת Y הינה <math>2^a</math>.




:2.  
:2.  


<math>|\mathbb{N}\cup Y|=\aleph_0+2^a=2^a</math>
<math>|\mathbb{N}\cup X|=\aleph_0+2^a=2^a</math>


<math>|\mathbb{N}\times Y|=\aleph_0\cdot 2^a=2^a</math>
<math>|\mathbb{N}\times X|=\aleph_0\cdot 2^a=2^a</math>


<math>|Y|^{|\mathbb{N}|}=(2^a)^{\aleph_0}=2^{a\cdot \aleph_0}=2^a</math>
<math>|X|^{|\mathbb{N}|}=(2^a)^{\aleph_0}=2^{a\cdot \aleph_0}=2^a</math>


<math>|\mathbb{N}|^{|Y|}=(\aleph_0)^{2^a}=2^{2^a}</math>
<math>|\mathbb{N}|^{|X|}=(\aleph_0)^{2^a}=2^{2^a}</math>




ב.
ב.


בעצם אנו רוצים לחשב איחוד בן מנייה של קבוצות מעוצמת <math>\aleph</math>. לכל <math>A_n</math> קיימת פונקציה חח"ע ועל <math>g_n:\mathbb{R}\rightarrow A_n</math>. לכן סה"כ נבנה פונקציה <math>f:\mathbb{N}\times\mathbb{R}\rightarrow\bigcup_{n\in\mathbb{N}}A_n</math> המוגדרת על ידי <math>f(k,x)=g_k(x)</math>. מכיוון שהקבוצות זרות ו<math>g_k</math> חח"ע ברור שf חח"ע. מכיוון ש<math>g_k</math> על גם f על ולכן סה"כ עוצמת הסכום הינה <math>\aleph_0\cdot\aleph=\aleph</math>
בעצם אנו רוצים לחשב איחוד בן מנייה של קבוצות מעוצמת <math>\aleph</math>.  
לכל עותק של <math>\aleph</math> נתאים  <math>A_n</math> ופונקציה חח"ע ועל  
<math>f_n:\mathbb{R}\rightarrow A_n</math>.  
כעת נגדיר פונקציה <math>g:\mathbb{N}\times\mathbb{R}\rightarrow\bigcup_{n\in\mathbb{N}}A_n</math> ע"י <math>g(k,x)=f_k(x)</math>. מכיוון שהקבוצות זרות ו<math>f_k</math> חח"ע ברור שg חח"ע. מכיוון ש<math>f_k</math> על גם g על ולכן סה"כ עוצמת הסכום הינה <math>\aleph_0\cdot\aleph=\aleph</math>

גרסה אחרונה מ־17:46, 5 באוגוסט 2020

חזרה למערכי התרגול

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

הגדרה יהיו A,B קבוצות אזי [math]\displaystyle{ A^B:=\{f:B\rightarrow A\} }[/math].

תרגיל

יהיו A,B,C קבוצות כך ש [math]\displaystyle{ |A|\leq |B| }[/math]. הוכיחו כי [math]\displaystyle{ |A^C|\leq|B^C| }[/math].

פתרון: נתון שקיימת [math]\displaystyle{ f:A\to B }[/math] חח"ע. נגדיר [math]\displaystyle{ g:A^C\to B^C }[/math] ע"י [math]\displaystyle{ h:C\to A\mapsto f\circ h }[/math]. מתקיים כי g חח"ע כי f חח"ע ויש לה הפיכה שמאלית.

הערה: [math]\displaystyle{ |A|\lt |B| }[/math] לא גורר [math]\displaystyle{ |A^C|\lt |B^C| }[/math].


תרגיל

הוכח שעוצמת קבוצת החזקה של A תמיד גדולה מעוצמתה של A

הוכחה. יש התאמה חח"ע ועל [math]\displaystyle{ g:P(A)\to \{0,1\}^A }[/math] ע"י [math]\displaystyle{ \forall B\subseteq A : g(B)=f_B=\chi_B }[/math]

לפי תרגיל קודם [math]\displaystyle{ |A|\lt |\{0,1\}^A|=|P(A)| }[/math]

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

תרגיל

יהיו A,B קבוצות כך ש [math]\displaystyle{ |B|\gt 1 }[/math]. הוכח כי [math]\displaystyle{ |A|\lt |B^A| }[/math].

פתרון. נבחר 2 איברים שונים [math]\displaystyle{ b_0,b_1\in B }[/math] ונגדיר פונקציה חח"ע [math]\displaystyle{ g:A\to B^A }[/math] ע"י [math]\displaystyle{ g(a)=f_a }[/math] כאשר [math]\displaystyle{ f_a(a)=b_1 }[/math] ו [math]\displaystyle{ \forall a'\not=a :f_a(a')=b_0 }[/math] ולכן [math]\displaystyle{ |A|\leq|B^A| }[/math].

נניח בשלילה שקיים שיוויון אזי קיימת התאמה חח"ע ועל [math]\displaystyle{ g:A\to B^A }[/math]. נסמן [math]\displaystyle{ \forall a\in A:g(a)=f_a }[/math].

נראה באופן דומה לתירגול קודם כי g איננה על ע"י שנמצא פונקציה f שאין לה מקור:

נבחר 2 איברים שונים [math]\displaystyle{ b_0,b_1\in B }[/math]ונגדיר פונקציה באופן הבא [math]\displaystyle{ f:A\rightarrow B }[/math] ע"י [math]\displaystyle{ f(a)=b_0 }[/math] אם [math]\displaystyle{ f_a(a)=b_1 }[/math]. ו- [math]\displaystyle{ f(a)=b_1 }[/math] אחרת. לפי הבנייה [math]\displaystyle{ \forall a\in A f\not=f_a }[/math] כיוון ש [math]\displaystyle{ f(a)\not=f_a(a) }[/math]. סתירה לכך ש g על.

הערה: התרגיל הזה הוא מסקנה מהתרגילים הקודמים כי [math]\displaystyle{ |\{0,1\}|\leq |B| }[/math] ולכן [math]\displaystyle{ |A|\lt |\{0,1\}^A|\leq |B^A| }[/math]

הגדרה: יהיו שתי קבוצות זרות A,B כך ש [math]\displaystyle{ |A|=a, |B|=b }[/math]. אזי נגדיר פעולות בין עוצמות:

  • [math]\displaystyle{ a+b:=|A\cup B| }[/math]
  • [math]\displaystyle{ a\cdot b := |A\times B| }[/math]
  • [math]\displaystyle{ a^b := |\{f:B\rightarrow A\}| }[/math]

דוגמא: ראינו בתירגול קודם את הזיהוי [math]\displaystyle{ [0,1)=\{f:\mathbb{N} \to \{0,1,...9\}\} }[/math] לכן [math]\displaystyle{ \aleph=|\mathbb{R}|=|[0,1)|=|\{f:\mathbb{N} \to \{0,1,...9\}\}|=10^{\aleph_0} }[/math]

הערות:

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

למשל [math]\displaystyle{ 2+1=|\{1,2\}\cup\{3\}|=3 }[/math]

  • שימו לב: מתוך הגדרה זו קל לראות את חוקי החזקות למקרי הקצה:
    • [math]\displaystyle{ a^0=1 }[/math] שכן יש פונקציה יחידה מהקבוצה הריקה לכל מקום - היחס שהוא הקבוצה הריקה.
    • [math]\displaystyle{ 0^0=1 }[/math] זה מקרה פרטי של הסעיף הקודם, ועדיין מתקיים
    • [math]\displaystyle{ 1^a=1 }[/math]
    • [math]\displaystyle{ a\neq 0 \rightarrow 0^a=0 }[/math] אין אף פונקציה מקבוצה לא ריקה אל קבוצה ריקה, שכן יחס כזה לא יכול להיות שלם.

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

יהיו a,b,c עוצמות אזי מתקיים

  • [math]\displaystyle{ ab=ba }[/math]
  • [math]\displaystyle{ (ab)c=a(bc) }[/math]
  • [math]\displaystyle{ a^ba^c=a^{b+c} }[/math]
  • [math]\displaystyle{ a^cb^c=(ab)^c }[/math]
  • [math]\displaystyle{ (a^b)^c=a^{bc} }[/math]

כלומר מתקיימים חוקי החזקות ה"רגילים"


נוכיח למשל [math]\displaystyle{ a^ba^c=a^{b+c} }[/math] יהיו [math]\displaystyle{ |A|=a,|B|=b,|C|=c }[/math] קבוצות זרות נגדיר פונקציה מ [math]\displaystyle{ A^{B\cup C} \to A^B\times A^C }[/math] ע"י [math]\displaystyle{ f \mapsto (f|_B,f|_C) }[/math]. היא חח"ע ועל.

נוכיח למשל [math]\displaystyle{ (a^b)^c=a^{bc} }[/math] יהיו [math]\displaystyle{ |A|=a,|B|=b,|C|=c }[/math] קבוצות זרות נגדיר פונקציה מ [math]\displaystyle{ (A^B)^C \to A^{B\times C} }[/math] ע"י [math]\displaystyle{ f \mapsto g(b,c)= f(c)(b) }[/math]. היא חח"ע ועל.


בנוסף אם מניחים את אקסיומת הבחירה אזי מתקיים עבור a,b עוצמות כאשר אחד מהם אין סופי

  • [math]\displaystyle{ a+b=max\{a,b\} }[/math]
  • אם שניהם אינם אפס אזי [math]\displaystyle{ a\cdot b=max\{a,b\} }[/math]
  • מסקנה: אם [math]\displaystyle{ 2\leq a \leq b }[/math] אזי [math]\displaystyle{ a^b=2^b }[/math]

הוכחה [math]\displaystyle{ 2^b\leq a^b\leq (2^a)^b=2^{ab}=2^b }[/math]

תרגיל

הוכח כי [math]\displaystyle{ \aleph_0+\aleph=\aleph }[/math]

הוכחה: דרך א- ישירות מהגדרה. נבחר [math]\displaystyle{ A=[\frac{1}{4},\frac{1}{2}],B=\mathbb{N} }[/math] אזי [math]\displaystyle{ \aleph=|A|\leq |A\cup B |\leq |\mathbb {R}|=\aleph }[/math]

דרך ב- מהנוסחא. [math]\displaystyle{ \aleph_0+\aleph=max\{\aleph_0,\aleph\}=\aleph }[/math]

תרגיל

הוכח כי [math]\displaystyle{ \aleph \cdot \aleph=\aleph }[/math]

הוכחה: [math]\displaystyle{ \aleph=|\{f:\mathbb{N}\to \{ 0,1\dots 9 \} \}|=10^{\aleph_0}=2^{\aleph_0} }[/math]

דרך א- ישירות מהגדרה. נבחר [math]\displaystyle{ A=\{f:\mathbb{N}\to \{0,1\dots 9\}\},B=A\times A }[/math] אזי נגדיר פונקציה [math]\displaystyle{ A\to A\times A }[/math] ע"י [math]\displaystyle{ f(n)\mapsto (f(2n),f(2n+1)) }[/math] . זו פונקציה חח" ועל.

דרך ב- אריתמטיקה- [math]\displaystyle{ \aleph \cdot \aleph=2^{\aleph_0}\cdot 2^{\aleph_0}=2^{\aleph_0+\aleph_0}=2^{\aleph_0}=\aleph }[/math]

דרך ג- מהנוסחא- [math]\displaystyle{ \aleph \cdot \aleph=max\{\aleph,\aleph\}=\aleph }[/math]

תרגיל

הוכח כי [math]\displaystyle{ |\mathbb{R}\backslash \mathbb{Q}|=\aleph }[/math]

פתרון:

כיוון ש [math]\displaystyle{ \mathbb{R}\backslash \mathbb{Q} }[/math] מוכל בממשיים עוצמתה לכל היותר אלף. נניח בשלילה כי עוצמתה שווה a קטנה ממש מאלף אזי [math]\displaystyle{ \aleph=|\mathbb{R}|=|\mathbb{R}\backslash \mathbb{Q}|+|\mathbb{Q}|=a+\aleph_0=a\lt \aleph }[/math]. סתירה

תרגיל

חשבו את [math]\displaystyle{ \aleph^{\aleph_0},{\aleph_0}^{\aleph} }[/math]

פתרון: [math]\displaystyle{ \aleph^{\aleph_0}=\aleph,{\aleph_0}^{\aleph}=2^{\aleph} }[/math]

הסיקו כי עוצמת קבוצת הפונקציות מהרציונאלים לממשיים היא [math]\displaystyle{ \aleph }[/math].

תרגיל

תהא [math]\displaystyle{ A }[/math] קבוצה אינסופית ו [math]\displaystyle{ B\subseteq A }[/math] תת קבוצה.

הוכח/הפרך

1. [math]\displaystyle{ |A\backslash B|=|A|\Rightarrow |B|\lt |A| }[/math]

2. [math]\displaystyle{ |A\backslash B|=|A|\Leftarrow |B|\lt |A| }[/math]

פתרון:

1. הפרכה: ניקח את השלמים והטבעיים

2. נכון כי ניתן להציג A כאיחוד זר [math]\displaystyle{ A=A\backslash B \cup B }[/math] ולכן [math]\displaystyle{ |A|=|A\backslash B| + |B| }[/math]. אם [math]\displaystyle{ |A\backslash B|\lt |A| }[/math] נקבל סתירה

תרגיל

1. מה עוצמת [math]\displaystyle{ \mathbb{N}^\mathbb{N} }[/math]

פתרון: [math]\displaystyle{ \aleph_0^{\aleph_0} =2^{\aleph_0} }[/math]

2. מה עוצמת [math]\displaystyle{ X=\{f\in \mathbb{N}^\mathbb{N}:f(1)\leq f(2)\} }[/math]

פתרון: לכל היותר [math]\displaystyle{ \mathbb{N}^\mathbb{N} }[/math] ולכל הפחות [math]\displaystyle{ \mathbb{N}^\mathbb{N} }[/math] כי לכל [math]\displaystyle{ g\in \mathbb{N}^{\mathbb{N}\setminus \{1,2\}} }[/math] נתאים [math]\displaystyle{ f\in X }[/math] ע"י [math]\displaystyle{ f(1)=f(2)=1 }[/math] ועבור [math]\displaystyle{ x\neq 1,2 }[/math] נגדיר [math]\displaystyle{ f(x)=g(x) }[/math] ולכן [math]\displaystyle{ |\mathbb{N}^{\mathbb{N}\setminus \{1,2\}}|\leq|X|\leq |\mathbb{N}^\mathbb{N}| }[/math] ולפי ק.ש.ב יש שיווון

3. מה עוצמת [math]\displaystyle{ X=\{f\in \mathbb{R}^\mathbb{R}:\forall x\notin \mathbb{Q} f(x)=1\} }[/math]

פתרון: X שווה עוצמה ל [math]\displaystyle{ \mathbb{R}^{\mathbb{Q}} }[/math] כי [math]\displaystyle{ g\in\mathbb{R}^{\mathbb{Q}} }[/math] ממופה ל [math]\displaystyle{ f\in X }[/math] המוגדרת [math]\displaystyle{ f|_{\mathbb{Q}}=g,f|_{\mathbb{R}\setminus\mathbb{Q}}=1 }[/math]

תרגיל

תהי [math]\displaystyle{ \{A_i\}_{i\in I} }[/math] משפחה של קבוצות הזרות זו לזו כך שעוצמת כל אחת מהן ב[math]\displaystyle{ a }[/math]. נגדיר [math]\displaystyle{ \sum_{i\in I} a = |\bigcup_{i\in I}A_i| }[/math]. הוכח כי [math]\displaystyle{ \sum_{i\in I} a = |I|\cdot a }[/math]

פתרון:

תהא [math]\displaystyle{ A }[/math] קבוצה נוספת מעוצמה [math]\displaystyle{ a }[/math]. לכל [math]\displaystyle{ i\in I }[/math] קיימת פונקציה חח"ע ועל [math]\displaystyle{ f_i:A\rightarrow A_i }[/math]. כעת נגדיר פונקציה [math]\displaystyle{ g:I\times A\rightarrow\bigcup_{i\in I}A_i }[/math] ע"י [math]\displaystyle{ g(k,x)=f_k(x) }[/math]. מכיוון שהקבוצות זרות ו[math]\displaystyle{ f_k }[/math] חח"ע ברור שg חח"ע. מכיוון ש[math]\displaystyle{ f_k }[/math] על גם g על ולכן קיבלנו את המבוקש.

תרגיל

נגדיר [math]\displaystyle{ F }[/math] להיות אוסף תתי הקבוצות הסופיות של הטבעיים [math]\displaystyle{ F=\{X\subseteq \mathbb{N}:|X|\lt \aleph_0\} }[/math]. מה עוצמתה?

פתרון: לכל [math]\displaystyle{ i\in \mathbb{N} }[/math] נגדיר [math]\displaystyle{ F_i=\{X\subseteq \mathbb{N}:|X|=i\} }[/math] (אוסף תתי הקבוצות מגודל [math]\displaystyle{ i }[/math]). אזי [math]\displaystyle{ |F_i|\leq \aleph_0^i=\aleph_0 }[/math] ואז [math]\displaystyle{ |F|=|\cup_{i\in \mathbb{N}}F_i|\leq \aleph_0\cdot \aleph_0 =\aleph_0 }[/math]

תרגיל (בש.ב.)

נגדיר [math]\displaystyle{ A }[/math] להיות אוסף תתי הקבוצות האינסופיות של הטבעיים. מה עוצמתה?

פתרון: מתקיים כי [math]\displaystyle{ P(\mathbb{N})=A\cup A^c }[/math] כאשר A היא תתי הקבוצות הסופיות מתרגיל קודם שעוצמת [math]\displaystyle{ \aleph_0 }[/math] ולכן [math]\displaystyle{ 2^{\aleph_0}=\aleph_0+|A^c|=\max\{\aleph_0,|A^c|\}=|A^c| }[/math]

תרגיל

נגדיר [math]\displaystyle{ A=\{X\subseteq \mathbb{R}: |X|=\aleph_0 \} }[/math] ,מה עוצמתה?

פתרון: לכל הפחות [math]\displaystyle{ 2^{\aleph_0} }[/math] כי תתי הקבוצות האינסופיות של הטבעיים מעוצמה זאת. בצד שני נגדיר [math]\displaystyle{ F:\mathbb{R}^{\mathbb{N}}\to P(\mathbb{R}) }[/math] ע"י [math]\displaystyle{ f\mapsto Im(f) }[/math] טענה: [math]\displaystyle{ A\subseteq Im(F) }[/math] הוכחה: תהא [math]\displaystyle{ X\in A }[/math] ומהגדרת A, נסיק כי X מעוצמה הטבעיים ולכן קיימת [math]\displaystyle{ f:\mathbb{N}\to X }[/math] חח"ע ועל ולכן [math]\displaystyle{ F(f)=Im(f)=X }[/math]. מסקנה מכך [math]\displaystyle{ |A|\leq |Im(F)|\leq |\mathbb{R}^{\mathbb{N}}|=\aleph^{\aleph_0}=\aleph }[/math]. לפי ק.ש.ב [math]\displaystyle{ |A|=2^{\aleph_0}=\aleph }[/math]

תרגיל

נגדיר [math]\displaystyle{ A=\{X\subseteq \mathbb{R}: |X|=\aleph \} }[/math] ,מה עוצמתה?

פתרון: לכל היותר [math]\displaystyle{ 2^\aleph }[/math] מצד שני [math]\displaystyle{ F:P((0,1))\to A }[/math] המוגדרת [math]\displaystyle{ B\mapsto B\cup (1,2) }[/math] חח"ע ולפי ק.ש.ב. סימנו

תרגיל ממבחן תשסח מועד א (ד"ר שי סרוסי וד"ר אלי בגנו)

תהי A קבוצה אינסופית. נסמן [math]\displaystyle{ a=|A|,\;B=P(A),\;F=A\times P(A),\; C=P(A)^A,\; H=B^B }[/math]

א. מצא את [math]\displaystyle{ |C| }[/math]
ב. מצא את [math]\displaystyle{ |F\times H| }[/math]
ג. מצא את [math]\displaystyle{ |\{R:|\mathbb{N}/R|=2\}| }[/math] המוכלת באוסף יחסי השקילות על הטבעיים.


פתרון. א. [math]\displaystyle{ |C|=(2^a)^a=2^{aa}=2^a }[/math]

ב.[math]\displaystyle{ |F\times H|=|F||H|=a2^a(2^a)^{2^a}=2^{a2^a}=2^{2^a} }[/math]

ג. כל יחס שקילות שקבוצת המנה 2 מתאים לחלוקה של [math]\displaystyle{ \mathbb{N} }[/math] ל-2 קבוצות זרות. ולכן יש התאמה חח"ע ועל [math]\displaystyle{ \{R:|\mathbb{N}/R|=2\} \leftrightarrow W=\{\{A,A^c\}|A\subseteq \mathbb{N}\} }[/math] ולכן 2 הקבוצות מאותה עוצמה.

ט: [math]\displaystyle{ |W|=2^{\aleph_0} }[/math]

ה: נסמן [math]\displaystyle{ |W|=a }[/math]. בנוסף [math]\displaystyle{ \bigcup_{\{A,A^c\}\in W}\{A,A^c\}=P(\mathbb{N}) }[/math] ולכן [math]\displaystyle{ 2^{\aleph_0}=|P(\mathbb{N})|=2a=a }[/math].

תרגיל

נגדיר [math]\displaystyle{ X=\left\{ 0,1\right\} ^{\mathbb{N}} }[/math] קבוצת כל הסדרות הבינאריות. נגדיר יחס [math]\displaystyle{ \sim }[/math] על [math]\displaystyle{ X }[/math] כך [math]\displaystyle{ f\sim g }[/math] אמ"מ הקבוצה[math]\displaystyle{ \left\{ n\in\mathbb{N}\mid f(n)\neq g(n)\right\} }[/math] סופית

הוכיחו כי [math]\displaystyle{ \sim }[/math] יח"ש

לכל [math]\displaystyle{ f\in X }[/math], מצאו את העוצמה של [math]\displaystyle{ [f] }[/math].

מצאו את העוצמה של קבוצת המנה.

תרגיל

תהא [math]\displaystyle{ X\subseteq P(\mathbb{N}) }[/math].

מצאו [math]\displaystyle{ X }[/math] המקיימת: כל [math]\displaystyle{ A,B\in X }[/math] שונות הן זרות (כלומר [math]\displaystyle{ A\cap B=\emptyset }[/math]).

ניח [math]\displaystyle{ X }[/math] מקיימת: כל [math]\displaystyle{ A,B\in X }[/math] שונות הן זרות. הוכיחו כי [math]\displaystyle{ X }[/math] בת מנייה.

תהא [math]\displaystyle{ C\subseteq\mathbb{N} }[/math]. נניח [math]\displaystyle{ X }[/math] מקיימת: החיתוך של [math]\displaystyle{ A,B\in X }[/math] שונות הוא [math]\displaystyle{ C }[/math] (כלומר [math]\displaystyle{ A\cap B=C }[/math]). הוכיחו כי [math]\displaystyle{ X }[/math] בת מנייה.

נניח [math]\displaystyle{ X }[/math] מקיימת: החיתוך של [math]\displaystyle{ A,B\in X }[/math] שונות הוא לכל היותר בן 10 איברים (כלומר [math]\displaystyle{ \left|A\cap B\right|\leq10 }[/math] ). הוכיחו כי [math]\displaystyle{ X }[/math] בת מנייה.רמז: [math]\displaystyle{ \cup_{B\in I}X_{B} }[/math] כאשר [math]\displaystyle{ I=\left\{ B\subseteq\mathbb{N}\mid\left|B\right|=10\right\} }[/math] ו [math]\displaystyle{ X_{B}=\left\{ S\in X\mid B\subseteq S\right\} }[/math]

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

יהי S יחס על [math]\displaystyle{ \mathbb{R}^\mathbb{R} }[/math] (קבוצת כל הפונקציות הממשיות), המוגדר על ידי [math]\displaystyle{ (f,g)\in S }[/math] אם"ם לכל [math]\displaystyle{ x\in\mathbb{R} }[/math] מתקיים [math]\displaystyle{ f(x)-g(x)\in\mathbb{Z} }[/math]

1. הוכיחו ש S הינו יחס שקילות
2. תהי [math]\displaystyle{ f\in\mathbb{R}^\mathbb{R} }[/math] מצאו את [math]\displaystyle{ |[f]| }[/math]
3. מצאו את [math]\displaystyle{ |\mathbb{R}^\mathbb{R}/S| }[/math]


פתרון:

1.

  • רפלקסיביות: [math]\displaystyle{ \forall x\in\mathbb{R} f(x)-f(x)=0\in\mathbb{Z} }[/math]
  • סימטריות: [math]\displaystyle{ f(x)-g(x)\in\mathbb{Z} }[/math] גורר שגם [math]\displaystyle{ g(x)-f(x)\in\mathbb{Z} }[/math] כי יש נגדי לחיבור
  • טרנזיטיביות: נובעת בקלות מסגירות לחיבור בשלמים: [math]\displaystyle{ f-h=f-g+g-h }[/math]

2.

עבור [math]\displaystyle{ [f]\in \mathbb{R}^\mathbb{R}/S }[/math] נגדיר [math]\displaystyle{ F:[f] \to \mathbb{Z}^{\mathbb{R}} }[/math]. ע"י [math]\displaystyle{ F(g):=f-g }[/math] נראה כי היא מוגדרת,חח"ע ועל.

מוגדרת: לפי ההגדרה של יחס השקילות אכן מתקיים [math]\displaystyle{ f-g\in \mathbb{Z}^{\mathbb{R}} }[/math]

נראה כי ל F קיימת הופכית. נגדיר [math]\displaystyle{ G: \mathbb{Z}^{\mathbb{R}} \to [f] }[/math]. ע"י [math]\displaystyle{ G(h):=f-h }[/math]. הפונקציה מוגדרת היטב כי [math]\displaystyle{ f-(f-h)\in \mathbb{Z}^{\mathbb{R}} }[/math] וקל לוודא שזוהי ההופכית

חח"ע: נניח [math]\displaystyle{ F(g)=F(h) }[/math] לכן [math]\displaystyle{ \forall x\in\mathbb{R} f(x)-g(x)=f(x)-h(x) }[/math] ולכן h=g.

על: תהי h פונקציה כלשהי מהממשיים לשלמים, ברור ש(f-h) במחלקת השקילות של f והיא תהיה המקור.

אם כך, העוצמה של מחלקת השקילות זהה לעוצמה של אוסף הפונקציות מהממשיים לשלמים והוא [math]\displaystyle{ {\aleph_0}^\aleph }[/math]. לפי התכונות שלמדנו לעיל מתקיים [math]\displaystyle{ 2^\aleph\leq{\aleph_0}^\aleph\leq 2^\aleph }[/math] ולכן לפי קנטור מתקיים [math]\displaystyle{ {\aleph_0}^\aleph=2^\aleph }[/math]

3.

נזכור בסימון [math]\displaystyle{ \lfloor x\rfloor }[/math] שהוא המספר השלם הגדול ביותר הקטן או שווה לx.

נגדיר F פונקציה השולחת את [math]\displaystyle{ f\in\mathbb{R}^\mathbb{R} }[/math] לפונקציה [math]\displaystyle{ F(f):=f-\lfloor f\rfloor\in [0,1)^\mathbb{R} }[/math]. נראה ש-F מוגדרת היטב (על קבוצת המנה)וההפעלה שלה על קבוצת המנה תהיה חח"ע ועל.

מוגדרות: יהיו שתי פונקציות באותה מחלקת שקילות g,f. אזי, [math]\displaystyle{ F(g)-F(f)=g-\lfloor g\rfloor -f + \lfloor f\rfloor }[/math]. מכיוון שזהו הפרש של שני מספרים אי שליליים קטנים מאחד, זה שווה למספר שבערכו המוחלט קטן מאחד. מכיוון שההפרש בין f ל-g שלם, המספר הזה הוא שלם. המספר השלם האי שלילי היחיד שקטן מאחד הינו אפס כלומר [math]\displaystyle{ F(f)=F(g) }[/math]. לכן הפונקציה F מוגדרת היטב שכן היא שולחת נציגים שונים של מחלקת שקילות לאותו מקום.

חח"ע: נניח [math]\displaystyle{ F(f)=F(g) }[/math] אז [math]\displaystyle{ f-g=\lfloor f\rfloor - \lfloor g\rfloor }[/math] כיוון ש [math]\displaystyle{ \lfloor f\rfloor - \lfloor g\rfloor\in \mathbb{Z}^\mathbb{R} }[/math] אזי הם נציגים של אותה מחלקת שקילות כלומר [math]\displaystyle{ [f]=[g] }[/math]

על: ניקח פונקציה כלשהי r מהממשיים לקטע [math]\displaystyle{ [0,1) }[/math]. קל לראות ש [math]\displaystyle{ F[r]=r }[/math] שכן [math]\displaystyle{ \lfloor r \rfloor = 0 }[/math]. לכן r ישמש מקור ולכן F הינה על.

סה"כ קיבלנו שעוצמת קבוצת המנה שווה ל[math]\displaystyle{ \aleph^\aleph }[/math] וזה שווה ל[math]\displaystyle{ 2^\aleph }[/math] לפי התכונות לעיל.

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

א. תהי A קבוצה אינסופית מעוצמה a.

1. נגדיר עבור :

[math]\displaystyle{ X=\{(X_1,...,X_n):1\lt n\in\mathbb{N}\and\Big[\bigcup_i X_i=A\Big] \and \Big[\forall i\neq j: X_i\cap X_j = \emptyset\Big] \and \big[ \forall i X_i \neq \emptyset\big]\} }[/math].

כלומר אוסף החלקות הסופיות הלא טרי' הסדורות של A הוכח [math]\displaystyle{ |X|=2^a }[/math]

2. מצא את [math]\displaystyle{ |\mathbb{N}\times X|,|\mathbb{N}\cup X| }[/math] וגם את [math]\displaystyle{ |X|^{|\mathbb{N}|},|\mathbb{N}|^{|X|} }[/math]


ב.תהי [math]\displaystyle{ \{A_i\}_{i\in I} }[/math] משפחה של קבוצות הזרות זו לזו. נסמן את עוצמת כל אחת מהן ב[math]\displaystyle{ a_i }[/math] בהתאמה. נגדיר [math]\displaystyle{ \sum_{i\in I} a_i = |\bigcup_{i\in I}A_i| }[/math].

חשב את [math]\displaystyle{ \sum_{n\in\mathbb{N}}\aleph }[/math]


פתרון.

א.

1.

נביט באוסף הפונקציות [math]\displaystyle{ Y=\{f:A\rightarrow\mathbb{N}\} }[/math]. נגדיר [math]\displaystyle{ g:X\to Y }[/math] על ידי לכל [math]\displaystyle{ x=(X_1,...,X_n)\in X }[/math]

נשלח אותו ל [math]\displaystyle{ g(x)=f_x }[/math] המוגדר [math]\displaystyle{ \forall a\in A :\; f_x(a)=k }[/math] כאשר [math]\displaystyle{ a\in X_k }[/math] כלומר שולחת איבר לאינדקס של הקבוצה שהוא נמצא בה בחלוקה.

נוכיח שהפונקציה מוגדרת וחח"ע.

מוגדרת: כיוון ש x הוא חלוקה של A אזי האיבר a יופיע ויופיע בדיוק באחת מהקבוצות.

חח"ע: נניח [math]\displaystyle{ (X_1,...,X_n)=x\neq x'=(X'_1,...,X'_m) }[/math]. אזי קיים [math]\displaystyle{ X_i\not=X'_i }[/math], לכן קיים יהיה [math]\displaystyle{ a\in X_i/X'_i }[/math] (או להיפך) ואז [math]\displaystyle{ i=f_x(a)\not= f_{x'}(a) }[/math] כלומר [math]\displaystyle{ g(x)\not=g(x') }[/math]

דרך 2- נגדיר פונקציה [math]\displaystyle{ g:X\to P(A)^{\mathbb{N}} }[/math] ע"י [math]\displaystyle{ g((X_1,...,X_n))(i) = \begin{cases}X_i & \text{if } 1\leq i \leq n \\ \emptyset & \text{if } n\lt i \end{cases} }[/math]

קל לראות כי הפונקציה חח"ע ולכן [math]\displaystyle{ |X| \leq (2^{a})^{\aleph_0} = 2^{a\cdot \aleph_0} =2^a }[/math]

דרך 3- נציג את X כאיחוד זר [math]\displaystyle{ X=\cup_{1\lt n\in \mathbb {N}}Y_n }[/math] כאשר [math]\displaystyle{ Y_n }[/math] זה חלוקות סדורות של A עם n קבוצות. כעת לכל n קיימת פונקציה [math]\displaystyle{ g:Y_n \to P(A)^n }[/math] המוגדרת [math]\displaystyle{ g((X_1,...,X_n))=X_1 \times \cdots \times X_n }[/math] קל לראות שהיא חח"ע ולכן [math]\displaystyle{ |Y_n|=|A|^n =|A| }[/math] ולכן [math]\displaystyle{ |X|\leq \sum_{1\lt n\in \mathbb {N}}|A|=|A|\cdot \aleph_0 =|A| }[/math]

כעת, קל למצוא פונקציה חח"ע מקבוצת החזקה של A ל-X - נשלח כל תת קבוצה לזוג שמכיל אותה ואת המשלים שלה.

לכן [math]\displaystyle{ 2^{|A|} \leq |X| \leq |Y| = \aleph_0^{|A|} }[/math], ולפי התכונות לעיל שני הקצוות שווים. לכן עוצמת X הינה [math]\displaystyle{ 2^a }[/math].


2.

[math]\displaystyle{ |\mathbb{N}\cup X|=\aleph_0+2^a=2^a }[/math]

[math]\displaystyle{ |\mathbb{N}\times X|=\aleph_0\cdot 2^a=2^a }[/math]

[math]\displaystyle{ |X|^{|\mathbb{N}|}=(2^a)^{\aleph_0}=2^{a\cdot \aleph_0}=2^a }[/math]

[math]\displaystyle{ |\mathbb{N}|^{|X|}=(\aleph_0)^{2^a}=2^{2^a} }[/math]


ב.

בעצם אנו רוצים לחשב איחוד בן מנייה של קבוצות מעוצמת [math]\displaystyle{ \aleph }[/math]. לכל עותק של [math]\displaystyle{ \aleph }[/math] נתאים [math]\displaystyle{ A_n }[/math] ופונקציה חח"ע ועל [math]\displaystyle{ f_n:\mathbb{R}\rightarrow A_n }[/math]. כעת נגדיר פונקציה [math]\displaystyle{ g:\mathbb{N}\times\mathbb{R}\rightarrow\bigcup_{n\in\mathbb{N}}A_n }[/math] ע"י [math]\displaystyle{ g(k,x)=f_k(x) }[/math]. מכיוון שהקבוצות זרות ו[math]\displaystyle{ f_k }[/math] חח"ע ברור שg חח"ע. מכיוון ש[math]\displaystyle{ f_k }[/math] על גם g על ולכן סה"כ עוצמת הסכום הינה [math]\displaystyle{ \aleph_0\cdot\aleph=\aleph }[/math]