שינויים

===תרגיל===יהיו 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>.

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

*<math>a^ba^c=a^{b+c}</math>

*אם a או b מייצגים עוצמה אינסופית אזי <math>a+b=max\{a,b\}</math>*אם a או b מייצגים עוצמה אינוספית ושניהם שניהם אינם אפס אזי <math>a\cdot b=max\{a,b\}</math>*מסקנה: אם <math>2\leq a\leq b</math> ו אזי <math>1a^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\{a\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^b{\aleph_0}</math> דרך א- ישירות מהגדרה. נבחר <math>A=\leq 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^b {\leq maxaleph_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^b{\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 a 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 b|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^bi=\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^b{\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> ,מה עוצמתה?

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

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

'''ט: <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> ===תרגיל ממבחן תשע מועד א''' (ד"ר שי סרוסי וד"ר אפי כהן)===

:1. הוכיחו שS ש 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{RZ}\rightarrow^{\mathbb{ZR}\}</math>. נוכיח ש-S חח"ע ועל.

נראה כי ל 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>SF(g)=SF(h)</math> לכן <math>\forall x\in\mathbb{R} f(x)-g(x)=f(x)-h(x)</math> ולכן h=g, זה מוכיח חח"ע. נוכיח על: תהי h פונקציה כלשהי מהממשיים לשלמים, ברור שf-h במחלקת השקילות של f.

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

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

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

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

:1. נגדיר עבור <math>2\leq n\in\mathbb{N}</math> את הקבוצה הבאה: <math>YX=\{(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>. '''הוכח''' <math>|Y|=2^a</math>

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

נביט באוסף הפונקציות <math>XY=\{f:A\rightarrow\mathbb{N}\}</math>. נגדיר <math>g:Y\rightarrow X\to Y</math> על ידי לכל <math>x=(X_1,...,X_n)\in X</math>  נשלח אותו ל <math>g(yx)=f_x</math> המוגדר<math>\forall a\in A :\; f_x(a)=k</math> אם כאשר <math>a\in X_k</math> בתוך ה-כלומר שולחת איבר לאינדקס של הקבוצה שהוא נמצא בה בחלוקה. נוכיח שהפונקציה מוגדרת וחח"ע.  מוגדרת: כיוון ש x הוא חלוקה של A אזי האיבר a יופיע ויופיע בדיוק באחת מהקבוצות.  חח"ע: נניח <math>n(X_1,...,X_n)=x\neq x'=(X'_1,...,X'_m)</math>-יה הסדורה y. נוכיח שזו אזי קיים <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, האיבר קל לראות כי הפונקציה חח"ע ולכן <math> |X| \leq (2^{a יופיע בדיוק באחת מהן. })^{\aleph_0} = 2^{a\cdot \aleph_0} =2^a</math>

חח"ע: נניח דרך 3- נציג את X כאיחוד זר <math>y_1X=\neq y_2cup_{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, לכן יהיה איזה a באחת מהן שלא בשני שישלח למספר טבעי שונה...,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 X - נשלח כל תת קבוצה לזוג שמכיל אותה ואת המשלים שלה.

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

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

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

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

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

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