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

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

עוצמות

הגדרה. יהיו A,B שתי קבוצות. אזי:

• אם קיימת פונקציה חח"ע מA לB אזי העוצמה של B גדולה או שווה לזו של A.
• אם קיימת פונקציה חח"ע ועל מA לB אזי אומרים שלA ולB יש אותה עוצמה

דוגמא. יהיו A וB שתי קבוצות סופיות. אזי אם מספר האיברים בהן שווה עוצמתן שווה, ואם מספר האיברים בA גדול מזה של B אזי עוצמתה של A גדולה יותר.

לכל קבוצה סופית בעלת n איברים, נאמר שעוצמתה הינה n.

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

תרגיל. הוכח שעוצמות הקבוצות הבאות שוות: [math]\displaystyle{ \mathbb{N},\mathbb{Z},\mathbb{Q} }[/math]

הוכחה: נבנה פונקציות חח"ע ועל ונוכיח מספר טענות עזר בדרך.

• נגדיר [math]\displaystyle{ f:\mathbb{N}\rightarrow\mathbb{Z} }[/math] ע"י
  • אם n זוגי אזי [math]\displaystyle{ f(n)=\frac{n}{2} }[/math]
  • אחרת, [math]\displaystyle{ f(n)=-\frac{n-1}{2} }[/math]

קל לוודא שפונקציה זו חח"ע ועל לכן עוצמת השלמים ועוצמת הטבעיים שווה.

טענה. אם [math]\displaystyle{ A\subseteq B }[/math] אזי [math]\displaystyle{ |A|\leq |B| }[/math]. קל לבנות פונקציה מA לB ששולחת כל איבר בA לעצמו, זו פונקציה חח"ע.

טענה. אם A קבוצה וR יחס שקילויות על הקבוצה אזי עוצמת קבוצת המנה קטנה או שווה לעוצמה של A. נוכיח טענה זו בהמשך הקורס באמצעות אקסיומת הבחירה.

טענה. מתקיים ש [math]\displaystyle{ |\mathbb{N}|=|\mathbb{N}\times \mathbb{N}| }[/math].

הוכחה. נביט באוסף הזוגות הסדורים של מספרים טבעיים, ונחלק אותם לקבוצות לפי סכום האיברים בזוג. בקבוצה הראשונה יהיה הזוג (1,1), בקבוצה השנייה יהיו הזוגות (1,2),(2,1), בקבוצה השלישית יהיו הזוגות (1,3),(2,2),(3,1) וכדומה.

נגדיר פונקציה [math]\displaystyle{ f:\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N} }[/math] באופן הבא:

• 1 נשלח לזוג הראשון בקבוצה הראשונה
• 2 נשלח לזוג הראשון בקבוצה השנייה
• 3 נשלח לזוג השני בקבוצה השנייה
• 4 נשלח לזוג הראשון בקבוצה השלישית
• ...

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

כמו כן קל לראות שפונקציה זו חח"ע וגם על.

טענה. מתקיים ש [math]\displaystyle{ |\mathbb{Z}|=|\mathbb{Z}\times \mathbb{Z}| }[/math]. תרגיל בית.

נביט באוסף הזוגות הסדורים בהם האיבר הימני שונה מאפס. קבוצה זו מוכלת באוסף כל הזוגות ולכן עוצמתה קטנה מעוצמת השלמים. נחלק אוסף זה ביחס השקילות [math]\displaystyle{ (a,b)~(x,y) \iff ay=bx }[/math] ונקבל קבוצה מעוצמה אף קטנה יותר. קבוצת המנה שקיבלנו היא כמובן [math]\displaystyle{ \mathbb{Q} }[/math] ולכן קיבלנו ש [math]\displaystyle{ |\mathbb{Q}|\leq |\mathbb{Z}| }[/math].

בכיוון ההפוך, השלמים מוכלים ברציונאליים ולכן עוצמתם קטנה יותר ומכאן שעוצמת הרציונאליים שווה לעוצמת השלמים.

(השתמשנו במשפט קנטור-ברנשטיין: אם A וB קבוצות שעוצמתן קטנות זו מזו אזי עוצמתן שווה.)

עוצמתן של הקבוצות הנ"ל נקראת [math]\displaystyle{ \aleph_0 }[/math]. קבוצות מעוצמה זו נקראות בנות מנייה.

שימו לב שכל קבוצה בת מנייה, ניתן למצוא פונקציה חח"ע ועל מהטבעיים אליה - כלומר, ניתן לסדר אותה בסדרה (ומכאן מגיע השם).

השוואות עוצמות

תרגיל. נביט באוסף כל הסדרות הבינאריות (01110010101011011...). נתאר אוסף זה באופן מדוייק: [math]\displaystyle{ B=\{f:\mathbb{N}\rightarrow \{0,1\}\} }[/math]. השווה בין העוצמה של B לבין אלף אפס.

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

לכן עוצמת B גדולה או שווה לאלף אפס. נוכיח כי היא גדולה ממש.

נניח בשלילה שקיימת פונקציה g חח"ע ועל מהטבעיים אל B. לכן ניתן "לסדר" את כל הסדרות אחת אחרי השנייה:

[math]\displaystyle{ g(1)=0101010110110101001000100101... }[/math]

[math]\displaystyle{ g(2)=1101010001010010100010101010... }[/math]

[math]\displaystyle{ g(3)=0101010101011101010001010111... }[/math]

נבנה סדרה בינארית שקיימת בB אך לא ייתכן שהיא מתקבלת על ידי הפונקציה g (כלומר היא אינה בסדרה, בסתירה).

נגדיר את הפונקציה f שנותנת את הסדרה [math]\displaystyle{ \forall n\in\mathbb{N}:f(n)= \neg g(n)_n }[/math]. כלומר לקחנו סדרה שהאיבר הראשון שלה שונה מהאיבר הראשון של הסדרה הראשונה, האיבר השני שונה מהאיבר השני של הסדרה השנייה וכן הלאה.

בדוגמא לעיל הסדרה תתחיל בשלושת האיברים [math]\displaystyle{ 101 }[/math] ולכן בוודאי לא תהיה אף אחת משלוש הסדרות הראשונות.

באופן כללי, לא ייתכן שסדרה זו נמצאת במקום k כלשהו בסדרת הסדרות, כי האיבר ה-k שלה שונה מהאיבר ה-k של הסדרה ה-k.

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

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

טענה. יהיו C,W קבוצות ויהיו [math]\displaystyle{ X,Y\subseteq W }[/math], [math]\displaystyle{ A,B\subseteq C }[/math] תתי קבוצות כך ש [math]\displaystyle{ A\cap B=X\cap Y=\phi }[/math] וגם [math]\displaystyle{ A\cup B = C }[/math] וגם [math]\displaystyle{ X\cup Y = W }[/math]. אזי אם קיימות פונקציות חח"ע ועל [math]\displaystyle{ g:B\rightarrow Y }[/math],[math]\displaystyle{ f:A\rightarrow X }[/math] מתקיים ש [math]\displaystyle{ |X|=|Y| }[/math]

תרגיל. הוכח שעוצמת הקטע [math]\displaystyle{ [0,1] }[/math] זהה לעוצמת הקטע [math]\displaystyle{ [0,1) }[/math]

פתרון.

אמנם זה נובע מתכונות אחרות אשר נלמדות בהרצאה ובשיעורי הבית, אך בכל זאת נמצא פונקציה חח"ע בין שתי הקבוצות הללו.

נגדיר [math]\displaystyle{ g:[0,1)\rightarrow [0,1] }[/math] על ידי:

• אם [math]\displaystyle{ \nexists n\in\mathbb{N}:x=\frac{1}{n} }[/math] אזי נגדיר [math]\displaystyle{ f(x)=x }[/math]

• אחרת נגדיר [math]\displaystyle{ f(\frac{1}{n})=\frac{1}{n-1} }[/math]

למעשה, כל מספר כמעט נשלח לעצמו פרט לסדרה הבת מנייה

[math]\displaystyle{ \frac{1}{2},\frac{1}{3},\frac{1}{4},... }[/math]

הנשלחת לסדרה

[math]\displaystyle{ \frac{1}{1},\frac{1}{2},\frac{1}{3},... }[/math].

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

(קל להוכיח שהפונקציה שתארנו לעיל הינה חח"ע ועל.)

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

הוכחה. קל מאד להראות שכל הקטעים הסופיים מאותה עוצמה, לכן מספיק להוכיח עבור קטע ספציפי. ניקח את הפונקציה [math]\displaystyle{ f(x)=\frac{1}{x} }[/math] בקטע [math]\displaystyle{ (0,1] }[/math] התמונה שלה הינה [math]\displaystyle{ [1,\infty) }[/math]. למעשה סיימנו פה את החלק העיקרי בתרגיל, שכן הפכנו קטע סופי לקטע אינסופי, כל שנותר לעשות הוא להשלים את מה שבנינו לפונקציה מקטע סופי לכל הממשיים.

ניקח פונקציה g השולחת את הקטע [math]\displaystyle{ (\frac{1}{2},1] }[/math] לקטע [math]\displaystyle{ (0,1] }[/math], על ידי [math]\displaystyle{ g(x)=2x-1 }[/math] ומשם נעביר לקטע האינסופי על ידי f. את הקטע [math]\displaystyle{ [0,\frac{1}{2}] }[/math] היא שולחת לקטע [math]\displaystyle{ [0,1] }[/math] על ידי 2x. סה"כ הגענו לחצי הישר [math]\displaystyle{ [0,\infty) }[/math].

באופן דומה נשלח את [math]\displaystyle{ (-1,0) }[/math] לקטע [math]\displaystyle{ (-\infty,0) }[/math] וסה"כ קיבלנו פונקציה חח"ע ועל מקטע סופי לכל ציר הממשיים.

תרגיל. ראינו ש [math]\displaystyle{ |\mathbb{N}|=|\mathbb{N}\times\mathbb{N}| }[/math]. האם אותו דבר נכון גם לגבי הממשיים?

הוכחה.

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

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

תרגיל ממבחן.

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

ב. מצא קבוצות A וB כך ש [math]\displaystyle{ |A|=|B| }[/math] אבל [math]\displaystyle{ |A/B|\neq |B/A| }[/math].

פתרון.

א. לפי הנתון קיימת פונקציה חח"ע ועל f בין A/B לבין B/A. נגדיר פונקציה g מ-A לB.

אם [math]\displaystyle{ (a\in A) \and (a\notin B) }[/math] אזי נגדיר [math]\displaystyle{ g(a)=f(a) }[/math]. אם [math]\displaystyle{ (a\in A) \and (a\in B) }[/math], נגדיר [math]\displaystyle{ g(a)=a }[/math]. נותר להוכיח כי g הינה חח"ע ועל.

על: לכל איבר בB או שהוא בA או שלא. אם לא, אזי מכיוון ש[math]\displaystyle{ f }[/math] על, יהיה לו מקור מתוך האיברים בA שאינם בB. אם הוא כן בA הוא ישלח לעצמו.

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

ב. ניקח את הטבעיים, ואת הטבעיים לאחר שזרקנו מהם את אחד. ברור שנשארנו עם קבוצות שוות עוצמה, אבל ההפרשים בינהם הם [math]\displaystyle{ \{1\},\phi }[/math] ואלו קבוצות מעוצמה שונה.

תרגיל.

נגדיר "שמיניה" בתור זוג עיגולים בגדלים כלשהם המשיקים זה לזה בנקודה כלשהי. יהי אוסף אינסופי כלשהו של שמיניות במישור הזרות זו מזו (כלומר אין שתים עם נקודת חיתוך משותפת)

א. הוכח שעוצמת קבוצה זו הינה אלף אפס

ב. הוכח שקיימת קבוצה של אינסוף עיגולים במרחב ללא חיתוך מעוצמת אלף

פתרון.

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

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

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

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