תרגול 14 תשעח

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש

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

עוצמות

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

  • אם קיימת f:A\to B חח"ע ועל אז אומרים של-A ול-B יש אותה עוצמה. סימון |A|=|B|.
  • אם קיימת f:A\to B חח"ע אז אומרים כי העוצמה של A קטנה או שווה לזו של B. סימון |A|\leq|B|.
  • אם |A|\leq|B| וגם |A|\not=|B| אזי אומרים כי העוצמה של A קטנה ממש מהעוצמה של B. סימון |A|<|B|.

הערה: בעזרת אקסיומת הבחירה מוכיחים כי אם קיימת f:A\to B על אזי |B|\leq |A|.

תרגיל

הוכיחו כי |P(\mathbb{N})|=|P(\mathbb{N})-\{\varnothing\}|.

פתרון

נגדיר פונקציה f:P(\mathbb{N})\to P(\mathbb{N})-\{\varnothing\} ע"י \{n\}\mapsto \{n+1\},\varnothing \mapsto \{1\} וכל B שאינה נקודון ואינה הקבוצה הריקה נשלח לעצמה.

הפיכה כי יש לה הופכית: f^{-1}:P(\mathbb{N})-\{\varnothing\}\to P(\mathbb{N}) ע"י \{1\}\mapsto \varnothing,\{n\geq 2\}\mapsto \{n-1\} וכל B שאינה נקודון נשלחת לעצמה.

תרגיל

הוכיחו כי |A\times A| = |A^{\{1,2\}}|.

פתרון: הפונקציה F:A^{\{1,2\}}\to A\times A המוגדרת f\mapsto (f(1),f(2)) הפיכה.

חח"ע: נניח F(f)=F(g) לכן (f(1),f(2))=(g(1),g(2)), ולכן f(1)=g(1)\land f(2)=g(2) וזו אותה פונקציה.

על: יהי (a,b)\in A\times A, הפונקציה שמוגדרת ע"י 1\mapsto a,2\mapsto b היא מקור.

משפט (קנטור-שרדר-ברנשטיין)

אם |B|\leq|A| וגם |A|\leq|B| אז |B|=|A|.

בהמשך נקצר לק.ש.ב.

תרגיל

הוכיחו: |\mathbb{Q}\cap [0,1]|=\aleph_0.

פתרון

לפי ק.ש.ב. כי הקבוצה מוכלת ברציונליים ומכילה \aleph_0 שברים מהצורה \frac{1}{n}.

תרגיל

הוכיחו כי עוצמת כל הקבוצות הבאות שווה - כל קטעים מהצורה [a,b],(a,b),[a,b),(a,b] כאשר a<b ממשיים.

פתרון

נראה שכולם שווי עוצמה לקטע (0,1).

ראשית נגדיר f:(0,1)\rightarrow (a,b) ע"י f(x)=a+(b-a)x חח"ע ועל. השאר עם ק.ש.ב.

טענה: הקטע (\frac{-\pi}{2},\frac{\pi}{2}) בעל עוצמה שווה ל-\mathbb{R}.

הוכחת הטענה: הפונקציה \tan:(\frac{-\pi}{2},\frac{\pi}{2})\to \mathbb{R} הפיכה בתחום הזה ולכן חח"ע ועל.

תרגיל

תהא A קבוצה. הוכיחו כי |A|\leq |P(A)|.

פתרון: נגדיר את הפונקציה f:A|\to P(A) ע"י a \mapsto \{a\} והיא חח"ע.

תהא A קבוצה. הוכיחו כי |A|\neq |P(A)|.

פתרון: נניח בשלילה כי |A|= |P(A)| אזי קיימת f: A\to P(A) הפיכה, בפרט על. נגדיר X=\{a\in A: a\notin f(a)\}. זוהי תת קבוצה של A ולכן, מכיוון ש-f על, קיים x\in A כך ש-f(x)=X. האם x\in X? אם לא, לפי הגדרת X נקבל כי x\notin f(x)=X, סתירה. אם כן אז x\in X=f(x) אבל לפי הגדרת X מתקיים x\notin f(x) סתירה. מש"ל.