תרגול 9 מדמח קיץ תשעז - היסטוריית גרסאות

אריאל: /* תרגיל */

2017-09-05T08:06:18Z

תרגיל

→ הגרסה הקודמת		גרסה מ־08:06, 5 בספטמבר 2017
שורה 174:		שורה 174:
	נגדיר <math>A=\{X\subseteq \mathbb{R}: \|X\|=\aleph_0 \}</math> ,מה עוצמתה?		נגדיר <math>A=\{X\subseteq \mathbb{R}: \|X\|=\aleph_0 \}</math> ,מה עוצמתה?

	פתרון: לכל הפחות <math>2^{\aleph_0}</math> כי תתי הקבוצות האינסופיות של הטבעיים מעוצמה זאת. בצד שני נגדיר <math>F:\mathbb{R}^{\mathbb{N}}\to A</math> המוגדרת <math>f\mapsto Imf</math> היא על כי לכל <math>X\in A</math> קיימת <math>f:\mathbb{N}\to X</math> הפיכה, בפרט על והיא תשמש כמקור. לפי ק.ש.ב <math>\|A\|=2^{\aleph_0}</math>		פתרון: לכל הפחות <math>2^{\aleph_0}</math> כי תתי הקבוצות האינסופיות של הטבעיים מעוצמה זאת. בצד שני נגדיר <math>F:\mathbb{R}^{\mathbb{N}}\to A</math> המוגדרת <math>f\mapsto Imf</math> (אם התמונה סופית נגדיר שנשלח לטבעיים). היא על כי לכל <math>X\in A</math> קיימת <math>f:\mathbb{N}\to X</math> הפיכה, בפרט על והיא תשמש כמקור. לפי ק.ש.ב <math>\|A\|=2^{\aleph_0}</math>.

	=== תרגיל ===		=== תרגיל ===

אריאל: /* תרגיל */

2017-09-03T13:03:37Z

תרגיל

→ הגרסה הקודמת		גרסה מ־13:03, 3 בספטמבר 2017
שורה 166:		שורה 166:

	=== תרגיל ===		=== תרגיל ===
	נגדיר <math>A</math> להיות ~~כלי קבוצות~~ האינסופיות של הטבעיים. מה עוצמתה?		נגדיר <math>B</math> להיות אוסף תתי הקבוצות האינסופיות של הטבעיים. מה עוצמתה?

	פתרון: מתקיים כי <math>P(\mathbb{N})=A\cup A^c</math> כאשר A היא תתי הקבוצות הסופיות מתרגיל קודם ~~שעוצמת~~ <math>\aleph_0</math>		פתרון: מתקיים כי <math>B=A^c\land 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>2^{\aleph_0}=\|P(\mathbb{N})\|=\|A\cup A^c\|=\aleph_0+\|A^c\|=\max\{\aleph_0,\|A^c\|\}=\|A^c\|</math>

	=== תרגיל ===		=== תרגיל ===

אריאל: /* תרגיל */

2017-09-03T12:59:52Z

תרגיל

→ הגרסה הקודמת		גרסה מ־12:59, 3 בספטמבר 2017
שורה 159:		שורה 159:

	=== תרגיל ===		=== תרגיל ===
	נגדיר <math>A</math> להיות ~~כלי קבוצות סופיות~~ של הטבעיים. מה עוצמתה?		נגדיר <math>A</math> להיות אוסף תתי הקבוצות הסופיות של הטבעיים. מה עוצמתה?

	פתרון: נגדיר <math>~~A_i~~</math> להיות תת הקבוצות ~~מגדול~~ <math>i</math>. אזי <math>\|~~A_i~~\|\leq \aleph_0^i=\aleph_0</math>		פתרון: נגדיר <math>A_n</math> להיות אוסף תתי הקבוצות מגודל <math>n</math>. אזי <math>\|A_n\|\leq \aleph_0^n=\aleph_0</math> כי ניתן לשלוח כל תת קבוצה ל- <math>n</math>-יה סדורה מהקטן לגדול, וראיתם בהרצאה ש <math>\|\mathbb{N}^n\|=\aleph_0</math>.
	~~ואז~~ <math>\|A\|=\|\cup_{i=0}^{\infty}\|\leq \aleph_0\cdot \aleph_0 =\aleph_0</math>
			כעת, <math>\|A\|=\|\cup_{n=0}^{\infty}A_n\|\leq \aleph_0\cdot \aleph_0 =\aleph_0</math>

	=== תרגיל ===		=== תרגיל ===

אריאל: /* תרגיל */

2017-09-03T12:53:34Z

תרגיל

→ הגרסה הקודמת		גרסה מ־12:53, 3 בספטמבר 2017
שורה 134:		שורה 134:
	1. מה עוצמת <math>\mathbb{N}^\mathbb{N}</math>		1. מה עוצמת <math>\mathbb{N}^\mathbb{N}</math>

	פתרון: <math>\aleph_0^{\aleph_0} =2^\aleph_0 </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>		2. מה עוצמת <math>X=\{f\in \mathbb{N}^\mathbb{N}:f(1)\leq f(2)\}</math>

אריאל: /* תרגיל */

2017-09-03T12:51:51Z

תרגיל

→ הגרסה הקודמת		גרסה מ־12:51, 3 בספטמבר 2017
שורה 146:		שורה 146:

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

	פתרון:		פתרון:

	תהא <math>A</math> קבוצה נוספת מעוצמה <math>a</math>.		תהא <math>A</math> קבוצה נוספת מעוצמה <math>\alpha</math>.
	לכל <math>i\in I</math> קיימת פונקציה ~~חח"ע ועל~~		לכל <math>i\in I</math> קיימת פונקציה על
	<math>f_i:A\rightarrow A_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>g:I\times A\rightarrow\bigcup_{i\in I}A_i</math> ע"י <math>g(k,x)=f_k(x)</math>.

			נראה שזו פונקציה על: יהי <math>a\in \bigcup_{i\in I}A_i</math> לכן קיים <math>i\in I</math> כך ש- <math>a\in A_i</math>. הפונקציה <math>f_i:A\rightarrow A_i</math> על, ולכן יש <math>x\in A</math> כך ש- <math>f_i(x)=a</math>. ולכן <math>g(i,x)=f_i(x)=a</math>, ומצאנו את המקור.

	=== תרגיל ===		=== תרגיל ===

אריאל: /* תרגיל */

2017-08-30T09:25:43Z

תרגיל

→ הגרסה הקודמת		גרסה מ־09:25, 30 באוגוסט 2017
שורה 31:		שורה 31:

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

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

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

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

אריאל: /* תרגיל */

2017-08-30T08:50:56Z

תרגיל

→ הגרסה הקודמת		גרסה מ־08:50, 30 באוגוסט 2017
שורה 15:		שורה 15:

	===תרגיל===		===תרגיל===
	הוכח שעוצמת קבוצת ~~החזקה של~~ A תמיד גדולה מעוצמתה של A		הוכח שעוצמת קבוצת הפונקציות מ- A ל- <math>\{ 0,1\}</math> תמיד גדולה מעוצמתה של A

	'''הוכחה.'''		'''הוכחה.'''

אריאל: /* תרגיל */

2017-08-30T08:47:55Z

תרגיל

→ הגרסה הקודמת		גרסה מ־08:47, 30 באוגוסט 2017
שורה 22:		שורה 22:

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

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

	===תרגיל===		===תרגיל===

אריאל: /* תרגיל */

2017-08-30T08:47:18Z

תרגיל

→ הגרסה הקודמת		גרסה מ־08:47, 30 באוגוסט 2017
שורה 21:		שורה 21:
	<math>\forall B\subseteq A : g(B)=f_B=\chi_B</math>		<math>\forall B\subseteq A : g(B)=f_B=\chi_B</math>

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

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

אריאל: יצירת דף עם התוכן "'''חזרה למערכי התרגול''' ==אריתמטיקה של עוצמות== '''הגדרה''' יהיו..."

2017-08-30T08:43:04Z

יצירת דף עם התוכן "'''חזרה למערכי התרגול''' ==אריתמטיקה של עוצמות== '''הגדרה''' יהיו..."

דף חדש

'''[[מערכי תרגול מדמח קיץ תשעז|חזרה למערכי התרגול]]'''

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

'''הגדרה''' יהיו 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

'''הוכחה.'''
יש התאמה חח"ע ועל <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>.

נראה באופן דומה לתירגול קודם כי 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>

'''הגדרה:'''
יהיו שתי קבוצות '''זרות''' A,B כך ש <math>|A|=a, |B|=b</math>. אזי נגדיר פעולות בין עוצמות:
*<math>a+b:=|A\cup B|</math>
*<math>a\cdot b := |A\times B|</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>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>
כלומר מתקיימים חוקי החזקות ה"רגילים"

נוכיח למשל <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 עוצמות כאשר אחד מהם אין סופי

* <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>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>A</math> להיות כלי קבוצות סופיות של הטבעיים. מה עוצמתה?

פתרון: נגדיר <math>A_i</math> להיות תת הקבוצות מגדול <math>i</math>. אזי <math>|A_i|\leq \aleph_0^i=\aleph_0</math>
ואז <math>|A|=|\cup_{i=0}^{\infty}|\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 A</math> המוגדרת <math>f\mapsto Imf</math> היא על כי לכל <math>X\in A</math> קיימת <math>f:\mathbb{N}\to X</math> הפיכה, בפרט על והיא תשמש כמקור. לפי ק.ש.ב <math>|A|=2^{\aleph_0}</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>|F\times H|</math>
:ג. מצא את <math>|\{R:|\mathbb{N}/R|=2\}|</math> המוכלת באוסף יחסי השקילות על הטבעיים.

'''פתרון.'''
א. <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>.

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

יהי 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 הינו יחס שקילות

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

:3. מצאו את <math>|\mathbb{R}^\mathbb{R}/S|</math>

'''פתרון:'''

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

2.

עבור <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>f-g\in \mathbb{Z}^{\mathbb{R}}</math>

נראה כי ל 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> וקל לוודא שזוהי ההופכית

חח"ע: נניח <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>

3.

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

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

חח"ע: נניח <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> לפי התכונות לעיל.

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

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

: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>.

כלומר אוסף החלקות הסופיות הלא טרי' הסדורות של 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>

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

חשב את <math>\sum_{n\in\mathbb{N}}\aleph</math>

'''פתרון.'''

א.

:1.

נביט באוסף הפונקציות <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>

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

דרך 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>2^{|A|} \leq |X| \leq |Y| = \aleph_0^{|A|}</math>, ולפי התכונות לעיל שני הקצוות שווים. לכן עוצמת X הינה <math>2^a</math>.

:2.

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

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

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

<math>|\mathbb{N}|^{|X|}=(\aleph_0)^{2^a}=2^{2^a}</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>