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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(תכונות האריתמטיקה)
(תרגיל (ממבחן))
 
(67 גרסאות ביניים של 6 משתמשים אינן מוצגות)
שורה 2: שורה 2:
  
 
==אריתמטיקה של עוצמות==
 
==אריתמטיקה של עוצמות==
 +
 
'''הגדרה''' יהיו A,B קבוצות אזי <math>A^B:=\{f:B\rightarrow A\}</math>.
 
'''הגדרה''' יהיו A,B קבוצות אזי <math>A^B:=\{f:B\rightarrow A\}</math>.
  
'''תרגיל.''' יהיו A,B קבוצות כך ש <math>|B|>1</math>. הוכח כי <math>|A|<|B^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
 +
 
 +
'''הוכחה.'''  
 +
יש התאמה חח"ע ועל <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>.
  
 
'''פתרון.'''
 
'''פתרון.'''
שורה 19: שורה 41:
 
לפי הבנייה <math>\forall a\in A f\not=f_a</math> כיוון ש <math>f(a)\not=f_a(a)</math>. סתירה לכך ש g על.
 
לפי הבנייה <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 תמיד גדולה מעוצמתה של A
+
 
+
'''הוכחה.'''
+
יש התאמה חח"ע ועל <math>g:P(A)\to \{0,1\}^A</math> ע"י <math>g(B)=f_B=\chi_B</math>
+
 
+
לפי תרגיל קודם <math>|A|<|\{0,1\}^A|=|p(A)|</math>
+
 
+
'''הערה: (למי שלמד תורת הקבוצות)''' מסיבה זו אוסף העוצמות אינו קבוצה אלא מחלקה. שכן אם הוא היה קבוצה, הייתה לו עוצמה
+
  
 
'''הגדרה:'''
 
'''הגדרה:'''
שורה 45: שורה 59:
 
**<math>a^0=1</math> שכן יש פונקציה יחידה מהקבוצה הריקה לכל מקום - היחס שהוא הקבוצה הריקה.
 
**<math>a^0=1</math> שכן יש פונקציה יחידה מהקבוצה הריקה לכל מקום - היחס שהוא הקבוצה הריקה.
 
**<math>0^0=1</math> זה מקרה פרטי של הסעיף הקודם, ועדיין מתקיים
 
**<math>0^0=1</math> זה מקרה פרטי של הסעיף הקודם, ועדיין מתקיים
 +
**<math>1^a=1</math>
 
**<math>a\neq 0 \rightarrow 0^a=0</math> אין אף פונקציה מקבוצה לא ריקה אל קבוצה ריקה, שכן יחס כזה לא יכול להיות שלם.
 
**<math>a\neq 0 \rightarrow 0^a=0</math> אין אף פונקציה מקבוצה לא ריקה אל קבוצה ריקה, שכן יחס כזה לא יכול להיות שלם.
 
  
 
===תכונות האריתמטיקה===
 
===תכונות האריתמטיקה===
שורה 52: שורה 66:
 
*<math>ab=ba</math>
 
*<math>ab=ba</math>
 
*<math>(ab)c=a(bc)</math>
 
*<math>(ab)c=a(bc)</math>
*<math>a^ba^c=a^{b+c}</math>
+
*<math>a^ba^c=a^{b+c}</math>  
 
*<math>a^cb^c=(ab)^c</math>
 
*<math>a^cb^c=(ab)^c</math>
 
*<math>(a^b)^c=a^{bc}</math>
 
*<math>(a^b)^c=a^{bc}</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,b עוצמות כאשר אחד מהם אין סופי
 
בנוסף אם מניחים את אקסיומת הבחירה אזי מתקיים עבור a,b עוצמות כאשר אחד מהם אין סופי
שורה 66: שורה 87:
 
הוכחה <math>2^b\leq a^b\leq (2^a)^b=2^{ab}=2^b</math>
 
הוכחה <math>2^b\leq a^b\leq (2^a)^b=2^{ab}=2^b</math>
  
'''תרגיל'''
+
===תרגיל===
הוכח כי <math>|\mathbb{R}\times \mathbb{R}|=|\mathbb{R}|</math>
+
הוכח כי <math>\aleph_0+\aleph=\aleph</math>
  
פתרון: ראינו <math>|\mathbb{R}|=10^{\aleph_0}=2^{\aleph_0}=</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>|\mathbb{R}\times \mathbb{R}|=2^{\aleph_0}2^{\aleph_0}=2^{\aleph_0+\aleph_0}=2^{\aleph_0}=|\mathbb{R}|</math>
+
  
 +
===תרגיל===
 +
הוכח כי <math>\aleph \cdot \aleph=\aleph </math>
  
'''תרגיל ממבחן תשסח מועד א''' (ד"ר שי סרוסי וד"ר אלי בגנו)
+
הוכחה:  <math>\aleph=|\{f:\mathbb{N}\to \{ 0,1\dots 9 \} \}|=10^{\aleph_0}=2^{\aleph_0}</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>
+
דרך א- ישירות מהגדרה. נבחר <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>
שורה 85: שורה 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>
שורה 108: שורה 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>
שורה 123: שורה 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 מוגדרת היטב שכן היא שולחת נציגים שונים של מחלקת שקילות לאותו מקום.
+
  
נניח בשלילה ש-S אינה חח"ע, לכן <math>S(f)-S(g)=0</math> עבור נציגים ממחלקות שקילות '''שונות'''. אבל אז <math>f-g=\lfloor f\rfloor - \lfloor g\rfloor</math> ולכן הם נציגים של אותה מחלקת שקילות בסתירה.
+
מוגדרות: יהיו שתי פונקציות באותה מחלקת שקילות 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 מוגדרת היטב שכן היא שולחת נציגים שונים של מחלקת שקילות לאותו מקום.
  
ניקח פונקציה כלשהי r מהממשיים לקטע <math>[0,1)</math>. קל לראות ש <math>S[r]=r</math> שכן <math>\lfloor r \rfloor = 0</math>. לכן S הינה על.
+
חח"ע: נניח <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>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>
  
  
שורה 154: שורה 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>, ולפי התכונות לעיל שני הקצוות שווים. לכן עוצמת 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