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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(אריתמטיקה של עוצמות)
(תרגיל (ממבחן))
 
(80 גרסאות ביניים של 8 משתמשים אינן מוצגות)
שורה 1: שורה 1:
'''[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור|חזרה למערכי התרגול]]'''
+
'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
  
 
==אריתמטיקה של עוצמות==
 
==אריתמטיקה של עוצמות==
'''תרגיל.''' יהיו A,B קבוצות כך ש, עוצמת B גדולה מאחד. הוכח כי העוצמה של אוסף הפונקציות מA לB גדולה מעוצמת A.
 
  
'''פתרון.'''
+
'''הגדרה''' יהיו A,B קבוצות אזי <math>A^B:=\{f:B\rightarrow A\}</math>.
  
קל לבנות פונקציה על מאוסף הפונקציות מA לB אל A. נשלח כל פונקציה באוסף למקור של איבר b מסוים. מכיוון שכל הפונקציות מA לB נמצאות באוסף, בפרט כל הפונקציות ששולחות כל איבר מA ל-b יהיו שם.
+
===תרגיל===
 +
יהיו 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 חח"ע ויש לה הפיכה שמאלית.
  
נניח בשלילה שקיימת התאמה חח"ע ועל בין A לבין אוסף הפונקציות הנ"ל. נסמן ב<math>f_a:A\rightarrow B</math> את הפונקציה המתאימה לאיבר <math>a\in A</math>.
+
הערה: <math>|A|< |B|</math> '''לא''' גורר <math>|A^C|<|B^C|</math>.
  
ידוע לנו שבקבוצה B יש לפחות שני איברים, לכן בהנתן אחד מהם אפשר לבחור את השני. נגדיר פונקציה באופן הבא <math>\forall a\in A : g(a)\neq g_a(a)</math>. לפי ההגדרות פונקציה זו הינה פונקציה מA לB אך אינה מתאימה לאף איבר בA בסתירה.
 
  
  
'''תרגיל.''' הוכח שעוצמת קבוצת החזקה של A תמיד גדולה מעוצמתה של A
+
===תרגיל===
 +
הוכח שעוצמת קבוצת החזקה של A תמיד גדולה מעוצמתה של A
 +
 
 +
'''הוכחה.'''
 +
יש התאמה חח"ע ועל <math>g:P(A)\to \{0,1\}^A</math> ע"י
 +
<math>\forall B\subseteq A : g(B)=f_B=\chi_B</math> 
 +
 
 +
לפי תרגיל קודם <math>|A|<|\{0,1\}^A|=|P(A)|</math>
 +
 
 +
'''הערה: (למי שלמד תורת הקבוצות)''' מסיבה זו אוסף העוצמות אינו קבוצה אלא מחלקה. שכן אם הוא היה קבוצה, הייתה לו עוצמה
 +
 
 +
===תרגיל===
 +
יהיו A,B קבוצות כך ש <math>|B|>1</math>. הוכח כי <math>|A|<|B^A|</math>.
 +
 
 +
'''פתרון.'''
 +
נבחר 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>g:A\to B^A</math>.
 +
נסמן <math>\forall a\in A:g(a)=f_a</math>.
  
'''הוכחה.''' קל להראות שקיימת העתקה חח"ע ועל בין אוסף הפונקציות <math>f:A\rightarrow \{0,1\}</math> (כל קבוצה חלקית אומרת בעצם על כל איבר של A אם הוא שייך (1) או לא שייך (0). למשל הפונקציה המתאימה לקבוצה הריקה היא פונקצית האפס, והפונקציה המתאימה לקבוצה כולה היא הפונקציה 1).
+
נראה באופן דומה לתירגול קודם כי g איננה על ע"י שנמצא פונקציה f שאין לה מקור:
  
אוסף הפונקציות עומד בתנאי התרגיל לעיל ולכן עוצמתו גדולה מעוצמת A אבל זהה לעוצמה של קבוצת החזקה, כפי שרצינו.
+
נבחר 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>
  
 
'''הגדרה:'''
 
'''הגדרה:'''
יהיו שתי קבוצות A,B כך ש <math>|A|=a, |B|=b</math>. אזי נגדיר פעולות בין עוצמות:
+
יהיו שתי קבוצות '''זרות''' A,B כך ש <math>|A|=a, |B|=b</math>. אזי נגדיר פעולות בין עוצמות:
 
*<math>a+b:=|A\cup B|</math>
 
*<math>a+b:=|A\cup B|</math>
 
*<math>a\cdot b := |A\times B|</math>
 
*<math>a\cdot b := |A\times B|</math>
 
*<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>
 
*אם a או b מייצגים עוצמה אינוספית ושניהם אינם אפס אזי <math>a\cdot b=max\{a,b\}</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^ba^c=a^{b+c}</math> יהיו <math>|A|=a,|B|=b,|C|=c</math> קבוצות זרות
 +
נגדיר פונקציה מ <math>A^{B\cup C} \to A^B\times A^C</math> ע"י <math>f \mapsto (f|_B,f|_C)</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 קבוצה אינסופית. נסמן <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,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=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 = \phi\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> בתוך הn-יה הסדורה 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>
  
מוגדרת היטב: מכיוון שהקבוצות זרות ואיחודן שווה לA, האיבר a יופיע בדיוק באחת מהן.  
+
דרך 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>
  
חח"ע: נניח <math>y_1\neq y_2</math> אזי יש איזה שתי תתי קבוצות של A שונות ביניהם, לכן יהיה איזה a באחת מהן שלא בשני שישלח למספר טבעי שונה.
+
קל לראות כי הפונקציה חח"ע ולכן <math> |X| \leq (2^{a})^{\aleph_0} = 2^{a\cdot \aleph_0} =2^a</math>
  
כעת, קל למצוא פונקציה חח"ע מקבוצת החזקה של A לY - נשלח כל תת קבוצה לזוג שמכיל אותה ואת המשלים שלה. את הקבוצה הריקה נשלח לשלישיה כלשהי.
+
דרך 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 ל-X - נשלח כל תת קבוצה לזוג שמכיל אותה ואת המשלים שלה.
  
העוצמה של אוסף הפונקציות לעיל הינה <math>|\mathbb{N}|^{|A|}\leq 2^{|A|}</math>, וקבוצת החזקה הינה מעוצמה <math>2^{|A|}</math> ולכן סה"כ עוצמת Y הינה <math>2^a</math>.
+
לכן <math>2^{|A|} \leq |X| \leq |Y| = \aleph_0^{|A|}</math>, ולפי התכונות לעיל שני הקצוות שווים. לכן עוצמת X הינה <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 קבוצות אזי A^B:=\{f:B\rightarrow A\}.

תרגיל

יהיו A,B,C קבוצות כך ש |A|\leq |B|. הוכיחו כי |A^C|\leq|B^C|.

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

הערה: |A|< |B| לא גורר |A^C|<|B^C|.


תרגיל

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

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

לפי תרגיל קודם |A|<|\{0,1\}^A|=|P(A)|

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

תרגיל

יהיו A,B קבוצות כך ש |B|>1. הוכח כי |A|<|B^A|.

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

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

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

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

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

הגדרה: יהיו שתי קבוצות זרות A,B כך ש |A|=a, |B|=b. אזי נגדיר פעולות בין עוצמות:

  • a+b:=|A\cup B|
  • a\cdot b := |A\times B|
  • a^b := |\{f:B\rightarrow A\}|

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

הערות:

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

למשל 2+1=|\{1,2\}\cup\{3\}|=3

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

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

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

  • ab=ba
  • (ab)c=a(bc)
  • a^ba^c=a^{b+c}
  • a^cb^c=(ab)^c
  • (a^b)^c=a^{bc}

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


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

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


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

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

הוכחה 2^b\leq a^b\leq (2^a)^b=2^{ab}=2^b

תרגיל

הוכח כי \aleph_0+\aleph=\aleph

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

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

תרגיל

הוכח כי \aleph \cdot \aleph=\aleph

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

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

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

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

תרגיל

הוכח כי |\mathbb{R}\backslash \mathbb{Q}|=\aleph

פתרון:

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

תרגיל

חשבו את \aleph^{\aleph_0},{\aleph_0}^{\aleph}

פתרון: \aleph^{\aleph_0}=\aleph,{\aleph_0}^{\aleph}=2^{\aleph}

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

תרגיל

תהא A קבוצה אינסופית ו B\subseteq A תת קבוצה.

הוכח/הפרך

1. |A\backslash B|=|A|\Rightarrow |B|<|A|

2. |A\backslash B|=|A|\Leftarrow |B|<|A|

פתרון:

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

2. נכון כי ניתן להציג A כאיחוד זר A=A\backslash B \cup B ולכן |A|=|A\backslash B| + |B|. אם |A\backslash B|<|A| נקבל סתירה

תרגיל

1. מה עוצמת \mathbb{N}^\mathbb{N}

פתרון: \aleph_0^{\aleph_0} =2^{\aleph_0}

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

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

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

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

תרגיל

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

פתרון:

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

תרגיל

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

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

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

נגדיר A להיות אוסף תתי הקבוצות האינסופיות של הטבעיים. מה עוצמתה?

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

תרגיל

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

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

תרגיל

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

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

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

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

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


פתרון. א. |C|=(2^a)^a=2^{aa}=2^a

ב.|F\times H|=|F||H|=a2^a(2^a)^{2^a}=2^{a2^a}=2^{2^a}

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

ט: |W|=2^{\aleph_0}

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

תרגיל

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

הוכיחו כי \sim יח"ש

לכל f\in X, מצאו את העוצמה של [f].

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

תרגיל

תהא X\subseteq P(\mathbb{N}).

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

ניח X מקיימת: כל A,B\in X שונות הן זרות. הוכיחו כי X בת מנייה.

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

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

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

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

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


פתרון:

1.

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

2.

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

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

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

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

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

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

3.

נזכור בסימון \lfloor x\rfloor שהוא המספר השלם הגדול ביותר הקטן או שווה לx.

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

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

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

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

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

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

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

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

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]\}.

כלומר אוסף החלקות הסופיות הלא טרי' הסדורות של A הוכח |X|=2^a

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


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

חשב את \sum_{n\in\mathbb{N}}\aleph


פתרון.

א.

1.

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

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

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

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

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

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

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

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

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

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


2.

|\mathbb{N}\cup X|=\aleph_0+2^a=2^a

|\mathbb{N}\times X|=\aleph_0\cdot 2^a=2^a

|X|^{|\mathbb{N}|}=(2^a)^{\aleph_0}=2^{a\cdot \aleph_0}=2^a

|\mathbb{N}|^{|X|}=(\aleph_0)^{2^a}=2^{2^a}


ב.

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