חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].
=עוצמות=
'''הגדרה.''' יהיו <math>A,B</math> שתי קבוצות. אזי:
*אם קיימת <math>f:A\to B </math> חח"ע ועל אז אומרים של-<math>A</math> ול-<math>B</math> '''יש אותה עוצמה'''. סימון <math>|A|=|B|</math>.
*אם קיימת <math>f:A\to B </math> חח"ע אז אומרים כי העוצמה של <math>A</math> קטנה או שווה לזו של <math>B</math>. סימון <math>|A|\leq|B|</math>.
* אם <math>|A|\leq|B|</math> וגם <math>|A|\not=|B|</math> אזי אומרים כי העוצמה של <math>A</math> קטנה ממש מהעוצמה של <math>B</math>. סימון <math>|A|<|B|</math>.
הערה: בעזרת אקסיומת הבחירה מוכיחים כי אם קיימת <math>f:A\to B </math> על אזי <math>|B|\leq |A|</math>.
=== תרגיל ===
הוכיחו כי <math>|P(\mathbb{N})|=|P(\mathbb{N})-\{\emptysetvarnothing\}|</math>.
==== פתרון ====
נגדיר פונקציה <math>f:P(\mathbb{N})\to P(\mathbb{N})-\{\emptysetvarnothing\} </math> ע"י <math>\{n\}\mapsto \{n+1\},\emptyset varnothing \mapsto \{1\}</math> וכל <math>B </math> שאינה נקודון ואינה קבוצה ריקה נשלחת הקבוצה הריקה נשלח לעצמה.
===תרגיל ===
הוכיחו כי <math>|A\times A| = |A^{\{1,2\}}|</math>.
פתרון: הפונקציה <math>F:A^{\{1,2\}}\to A\times A</math> המוגדרת <math>f\mapsto (f(1),f(2))</math> הפיכה.
===משפט (קנטור- שרדר-ברנשטיין)===
אם <math>|B|\leq|A|</math> וגם <math>|A|\leq|B|</math> אז <math>|B|=|A|</math>. בהמשך נקצר לק.ש.ב.
===תרגיל===
הוכיחו: <math>|\mathbb{Q}\cap [0,1]|=\aleph_0</math>.
====פתרון====
לפי ק.ש.ב. כי מוכל ברציונאליים ומכיל הקבוצה מוכלת ברציונליים ומכילה <math>\aleph_0</math> שברים מהצורה <math>\frac{1}{n}</math>.
===תרגיל===
הוכח הוכיחו כי עוצמת כל הקבוצות הבאות שווה - כל קטעים מהצורה <math>[a,b],(a,b),[a,b),(a,b]</math> כאשר <math>a<b</math> ממשיים.
====פתרון====
נראה שכולם שווי עוצמה לקטע <math>(0,1)</math>.
ראשית נגדיר <math>f:(0,1)\rightarrow (a,b)</math> ע"י <math>f(x)=a+(b-a)x</math> חח"ע ועל. השאר עם ק.ש.ב. ט: הקטע <math>(\frac{-\pi}{2},\frac{\pi}{2})</math> בעל עוצמה שווה ל <math>\mathbb{R}</math>.
הטענה: הפונקציה הקטע <math>tan:(\frac{-\pi}{2},\frac{\pi}{2})\to </math> בעל עוצמה שווה ל-<math>\mathbb{R}</math> הפיכה בתחום הזה ולכן חח"ע ועל.
הוכחת הטענה: הפונקציה <math>\tan:(\frac{-\pi}{2},\frac{\pi}{2})\to \mathbb{R}</math> הפיכה בתחום הזה ולכן חח"ע ועל.
===תרגיל ===
תהא <math>A </math> קבוצה. הוכח הוכיחו כי <math>|A|\leq |P(A)|</math>.
פתרון: נגדיר את הפונקציה <math>f:A|\to P(A)</math> ע"י <math>a \mapsto \{a\}</math> היא והיא חח"ע.
תהא <math>A </math> קבוצה. הוכח הוכיחו כי <math>|A|\neq |P(A)|</math>.
פתרון: נניח בשלילה כי <math>|A|= |P(A)|</math> אזי קיימת <math>f: A\to P(A)</math> הפיכה, בפרט על. נגדיר <math>X=\{a\in A: a\notin f(a)\}</math>. זוהי תת קבוצה של <math>A </math> ולכן, מכיוון ש -<math>f </math> על, קיים <math>x\in A</math> כך ש -<math>f(x)=X</math>. האם <math>x\in X</math>? אם לא, לפי הגדרת <math>X </math> נקבל כי <math>x\notin f(x)=xX</math> , סתירה. אם כן אז <math>x\in X=f(x)</math> אבל לפי הגדרת <math>X </math> מתקיים <math>x\notin f(x)</math> סתירה. משל/מש"ל.