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

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

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

תרגיל. יהיו A,B קבוצות כך ש, עוצמת B גדולה מאחד. הוכח כי העוצמה של אוסף הפונקציות מA לB גדולה מעוצמת A.

פתרון.

קל לבנות פונקציה על מאוסף הפונקציות מA לB אל A. נשלח כל פונקציה באוסף למקור של איבר b מסוים. מכיוון שכל הפונקציות מA לB נמצאות באוסף, בפרט כל הפונקציות ששולחות כל איבר מA ל-b יהיו שם.

נניח בשלילה שקיימת התאמה חח"ע ועל בין A לבין אוסף הפונקציות הנ"ל. נסמן ב$f_a:A\rightarrow B$ את הפונקציה המתאימה לאיבר $a\in A$.

ידוע לנו שבקבוצה B יש לפחות שני איברים, לכן בהנתן אחד מהם אפשר לבחור את השני. נגדיר פונקציה באופן הבא $\forall a\in A : g(a)\neq g_a(a)$. לפי ההגדרות פונקציה זו הינה פונקציה מA לB אך אינה מתאימה לאף איבר בA בסתירה.

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

הוכחה. קל להראות שקיימת העתקה חח"ע ועל בין אוסף הפונקציות $f:A\rightarrow \{0,1\}$ (כל קבוצה חלקית אומרת בעצם על כל איבר של A אם הוא שייך (1) או לא שייך (0). למשל הפונקציה המתאימה לקבוצה הריקה היא פונקצית האפס, והפונקציה המתאימה לקבוצה כולה היא הפונקציה 1).

אוסף הפונקציות עומד בתנאי התרגיל לעיל ולכן עוצמתו גדולה מעוצמת A אבל זהה לעוצמה של קבוצת החזקה, כפי שרצינו.

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

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

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

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

שימו לב: מתוך הגדרה זו קל לראות את חוקי החזקות למקרי הקצה:

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

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

בהנחת אקסיומת הבחירה:

• אם a או b מייצגים עוצמה אינסופית אזי $a+b=max\{a,b\}$
• אם a או b מייצגים עוצמה אינוספית ושניהם אינם אפס אזי $a\cdot b=max\{a,b\}$
• אם $2\leq a$ ו $1\leq b$ ולפחות אחת מבינהם הוא אינסופי אזי $max\{a,2^b\}\leq a^b \leq max\{2^a,2^b\}$
  • מסקנה: אם $2\leq a \leq b$ אזי $a^b=2^b$

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

תהי A קבוצה אינסופית. נסמן $|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\}$

א. מצא את $|C|$

ב. מצא את $|F\times H|$

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

פתרון.

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

יהי 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 ונראה שיש העתקה S חח"ע ועל ממנה לאוסף הפונקציות מהממשיים לשלמים.

$S(g):=f-g$. לפי ההגדרה, $f-g\in\{h:\mathbb{R}\rightarrow\mathbb{Z}\}$. נוכיח ש-S חח"ע ועל.

נניח $S(g)=S(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.

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

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

נניח בשלילה ש-S אינה חח"ע, לכן $S(f)-S(g)=0$ עבור נציגים ממחלקות שקילות שונות. אבל אז $f-g=\lfloor f\rfloor - \lfloor g\rfloor$ ולכן הם נציגים של אותה מחלקת שקילות בסתירה.

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

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

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

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

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

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

ב.תהי $\{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.

נביט באוסף הפונקציות $X=\{f:A\rightarrow\mathbb{N}\}$. נגדיר $g:Y\rightarrow X$ על ידי $g(y)(a)=k$ אם $a\in X_k$ בתוך הn-יה הסדורה y. נוכיח שזו פונקציה מוגדרת היטב, חח"ע ועל.

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

חח"ע: נניח $y_1\neq y_2$ אזי יש איזה שתי תתי קבוצות של A שונות ביניהם, לכן יהיה איזה a באחת מהן שלא בשני שישלח למספר טבעי שונה.

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

העוצמה של אוסף הפונקציות לעיל הינה $|\mathbb{N}|^{|A|}\leq 2^{|A|}$, וקבוצת החזקה הינה מעוצמה $2^{|A|}$ ולכן סה"כ עוצמת Y הינה $2^a$.

2.

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

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

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

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

ב.

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