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

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

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

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

תרגיל

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

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

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

תרגיל

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

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

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

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

תרגיל

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

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

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

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

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

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

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

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

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

הערות:

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

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

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

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

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

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

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

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

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

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

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

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

תרגיל

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

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

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

תרגיל

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

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

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

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

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

תרגיל

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

פתרון:

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

תרגיל

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

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

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

תרגיל

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

הוכח/הפרך

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

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

פתרון:

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

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

תרגיל

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

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

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

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

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

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

תרגיל

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

פתרון:

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

תרגיל

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

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

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

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

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

תרגיל

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

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

תרגיל

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

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

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

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

א. מצא את [math]\displaystyle{ |C| }[/math]

ב. מצא את [math]\displaystyle{ |F\times H| }[/math]

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

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

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

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

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

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

תרגיל

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

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

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

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

תרגיל

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

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

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

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

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

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

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

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

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

3. מצאו את [math]\displaystyle{ |\mathbb{R}^\mathbb{R}/S| }[/math]

פתרון:

1.

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

2.

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

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

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

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

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

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

3.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

פתרון.

א.

1.

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

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

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

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

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

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

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

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

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

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

2.

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

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

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

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

ב.

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