תורת הקבוצות/עוצמות

עוצמה היא מדד לגודל הקבוצה, גם אם הקבוצה אינסופית. אם הקבוצה סופית, אז עוצמה שלה היא מספר האיברים בה. כך למשל, העוצמה של הקבוצה $\{0,1,2\}$ היא 3, ונסמן $|\{0,1,2\}|=3$. נאמר שלשתי קבוצות יש את אותה עוצמה, אם הן שקולות, כלומר יש פונקציה חד חד ערכית ועל ביניהן. כך למשל, הפונקציה $S:\mathbb {N} \to \mathbb {N} \setminus \{0\}$ המוגדרת על פי $S(n)=n+1$, היא חד חד ערכית ועל, לכן נאמר כי $|\mathbb {N} |=|\mathbb {N} \setminus \{0\}|$. קבוצה תיקרא אינסופית אם יש לה תת קבוצה ממש בעלת אותה עוצמה. הפונקציה שהבאנו קודם מראה כי קבוצת המספרים הטבעיים אינסופית.

משפט 4.0: אם $|A|=|B|,|C|=|D|$ והקבוצות $A,C$ זרות ו$B,D$ זרות, אז $|A\cup C|=|B\cup D|$.

הוכחה: יהו $f:A\to B,g:C\to D$ חד חד ערכיות ועל. נגדיר $\psi :A\cup C\to B\cup D:\psi (x)={\begin{cases}f(x)&&x\in A\\g(x)&&x\in C\end{cases}}$. זוהי פונקציה חד חד ערכית ועל.

$\aleph _{0}$ וקבוצה בת מנייה

הגדרה: $\aleph _{0}$ וקבוצה בת מנייה $\aleph _{0}$ (קרי: אָלֶף אֶפֶס) הוא הסימון המקובל לעוצמת הקבוצה $\mathbb {N}$, כלומר $|\mathbb {N} |=\aleph _{0}$. נאמר כי קבוצה היא בת מנייה, אם היא סופית, או שעוצמתה $\aleph _{0}$.

כך למשל, $\mathbb {Z}$, קבוצת המספרים השלמים, היא בת מנייה, כי הפונקציה $f:\mathbb {Z} \to \mathbb {N}$ המוגדרת $f(x)={\begin{cases}2x&&x\geq 0\\2|x|+1&&x<0\end{cases}}$ היא חד חד ערכית ועל, לכן $|\mathbb {Z} |=|\mathbb {N} |=\aleph _{0}$. השם קבוצה בת מנייה בא לומר שניתן למנות את איברי הקבוצה בזה אחר זה (כלומר, לשכנם בסדרה) בלי לפספס אף איבר. אין משמעות העניין שהמנייה חייבת להסתיים מתישהו, אלא שכל איבר יגיע לאחר מספר סופי של צעדים. המנייה תיעשה על פי $f(0),f(1),f(2),...$ כאשר $f:\mathbb {N} \to A$ היא חד חד ערכית ועל (קיימת כזו כי הקבוצה בת מנייה). אם A סופית, כמובן שניתן למנות את איבריה, בכל סדר שנרצה, ותמיד לא נפספס אף איבר. גם ההיפך נכון - אם ניתן למנות איברי קבוצה בצורה הזו, אז יש פונקציה חד חד ערכית ועל ממנה לקבוצת המספרים הטבעיים: נניח שהמנייה היא $a_{0},a_{1},a_{2},...$ כאשר לכל i, $a_{i}\in A$. אז הפונקציה $f(a_{n})=n$ היא חד חד ערכית ועל (אם $f(a_{n})=f(a_{m})$ אז בהכרח $n=m$. כמו כן, כל מספר טבעי יופיע בתמונת הפונקציה, כי הקבוצה אינסופית והמנייה לא מדלגת על אף מספר טבעי), ואז $|A|=\aleph _{0}$.

משפט 4.1: קבוצה $A$ היא בת מנייה, אם ורק אם קיימת פונקציה $f:A\to \mathbb {N}$ חח"ע.

הוכחה: נניח שA בת מנייה. אז או שהיא סופית, ואז נסמן $A=\{a_{0},...,a_{n}\}$ את כל איברי A עבור n כלשהו, שהוא $|A|+1$. הפונקציה $f:A\to \mathbb {N} :f(a_{i})=i$ היא חח"ע. המקרה השני הוא ש$|A|=\aleph _{0}$, ואז $|A|=|\mathbb {N} |$ ולכן קיימת $f:a\to \mathbb {N}$ חח"ע ועל, ובפרט חח"ע. נניח שקיימת פונקציה חד חד ערכית $f:A\to \mathbb {N}$. אם A סופית המקרה טריוויאלי. לכן נניח שA אינסופית. נסמן $B=\mathrm {Im} (f)$. מכיוון שf חח"ע, $|B|=|A|$, ואז B אינסופית גם כן. נגדיר פונקציה $g:B\to \mathbb {N}$ כך: $g(x)=|\{y\in B:y<x\}|$. נראה כי פונקציה זו חח"ע: נניח ש$x\not =y$. נניח ללא הגבלת הכלליות ש$x<y$. אז $x\in \{z\in B:z<y\}$, לכן $\{z\in B:z<x\}\subset \{z\in B:z<y\}$. מכיוון שהקבוצות סופיות, מתקיים $|\{z\in B:z<x\}|<|\{z\in B:z<y\}|$, לכן $g(x)<g(y)$ ובפרט $g(x)\not =g(y)$. נראה כי פונקציה זו היא על: נשתמש בכך שלכל קבוצה לא ריקה של מספרים טבעיים, יש איבר ראשון. נוכיח באינדוקציה על n, שיש איבר שn הוא הדמות שלו על ידי g. עבור n=0 - $g(a)=0$ כאשר a הוא האיבר הראשון בקבוצה B. יהי n>0: אז יהי b האיבר הראשון בקבוצה $B\setminus \{g^{-1}(x):x<n\}$ (הקבוצה קיימת על פי הנחת האינדוקציה). אז מתקיים $g(b)=n$. לכן $|A|=|B|=|\mathbb {N} |=\aleph _{0}$, ואז A בת מנייה.

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

איחוד, חיתוך, ומכפלה קרטזית של קבוצות בנות מנייה

משפט 4.2: איחוד של קבוצות בנות מנייה אם $A,B$ בנות מנייה, אז $A\cup B$ בת מנייה.

הוכחה: יהו $f:A\to \mathbb {N} ,g:B\to \mathbb {N}$ חד חד ערכיות. נגדיר פונקציות $p:\mathbb {N} \to 2\mathbb {N} ,q:\mathbb {N} \to 2\mathbb {N} +1$ ($2\mathbb {N} =\{2n:n\in \mathbb {N} \}$, וכן $2\mathbb {N} +1=\{2n+1:n\in \mathbb {N} \}$) על פי $p(n)=2n,q(n)=2n+1$. שתי פונקציות אלו חד חד ערכיות, ותמונותיהן זרות, לכן נוכל להגדיר פונקציה $\psi :A\cup B\to \mathbb {N}$ על פי $\psi (x)={\begin{cases}(p\circ f)(x)&&x\in A\\(q\circ g)(x)&&x\in B\setminus A\end{cases}}$, שהיא גם כן חד חד ערכית. לכן $|A\cup B|=\aleph _{0}$.

משפט 4.3: איחוד בן מנייה של קבוצות בנות מנייה אם לכל n טבעי, $A_{n}$ בת מנייה, אז $\bigcup _{n=0}^{\infty }A_{n}$ בת מנייה. נוסח אחר: איחוד בן מנייה של קבוצות בנות מנייה הוא בן מנייה.

הוכחה: לכל n טבעי, תהי $f_{n}:A_{n}\to \mathbb {N}$ חד חד ערכית. נגדיר את הפונקציה $f:\bigcup _{n=0}^{\infty }A_{n}\to \mathbb {N}$ על פי $f(x)=p_{n}^{f_{n}(x)}$ כאשר $x\in A_{n}$ ו$p_{n}$ הוא הראשוני הn. מתכונת הפירוק היחיד של המספרים הטבעיים, נקבל שf חד חד ערכית.

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

הוכחה: מתקיים $A\cap B\subseteq A$, לכן יש פונקציה $g:A\cap B\to A$ חד חד ערכית (על פי $g(x)=x$). בנוסף, תהי $f:A\to \mathbb {N}$ חד חד ערכית. אז הפונקציה $f\circ g$ חד חד ערכית, לכן $A\cap B$ בת מנייה.

משפט 4.5: מכפלה קרטזית של קבוצות בנות מנייה מכפלה קרטזית של קבוצות בנות מנייה היא בת מנייה.

הוכחה: נתבונן בקבוצה $\mathbb {N} \times \mathbb {N}$. נוכל למנות את איבריה כך: לכן $|\mathbb {N} \times \mathbb {N} |=\aleph _{0}$. המנייה המתוארת ניתנת לביטוי גם באמצעות הפונקציה: $\pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}.$. ראו הוכחה כאן לכך שהפונקציה חד חד ערכית ועל. כעת, אם $f:A\to \mathbb {N} ,g:B\to \mathbb {N}$ חד חד ערכיות, אז הפונקצייה $\psi :A\times B\to \mathbb {N}$ המוגדרת על פי $\psi (x,y)=\pi (f(x),g(y))$ היא חד חד ערכית.

משפט 4.5.1: מכפלה קרטזית סופית של קבוצות בנות מנייה אם לכל $0\leq i\leq n$, $A_{i}$ בת מנייה, אז $\prod _{i=0}^{n}A_{i}$ בת מנייה.

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

מסקנה של משפט זה היא שאם A בת מנייה, אז $A^{n}$ בת מנייה, לכל n טבעי.

תרגיל: הוכיחו כי קבוצת הסדרות אינסופיות של מספרים טבעיים (נסמן $\mathbb {N} ^{*}$), הנעשות קבועות ממקום מסוים, היא בת מנייה.

פתרון

נסמן את קבוצת הסדרות הנעשות קבועות מהמקום הn ב$\mathbb {N} _{n}$. ניתן לזהות כל סדרה $(a_{0},...,a_{n},a_{n},...)\in \mathbb {N} _{n}$ עם הסדרה הסופית $(a_{0},...,a_{n})$. נקבל $|\mathbb {N} _{n}|=|\mathbb {N} ^{n}|=\aleph _{0}$, כלומר $\mathbb {N} _{n}$ בת מנייה. נקבל $\mathbb {N} ^{*}=\mathbb {N} _{0}\cup \mathbb {N} _{1}\cup ...=\bigcup _{n=0}^{\infty }\mathbb {N} _{n}$ איחוד בן מנייה של קבוצות בנות מנייה, לכן היא בת מנייה.

משפטים נוספים על קבוצות בנות מנייה

משפט 4.6: תת קבוצה של קבוצה בת מנייה היא לכל היותר בת מנייה.

הוכחה: תהי $f:A\to \mathbb {N}$ חד חד ערכית, ותהי $B\subseteq A$. אז הפונקציה $\psi :B\to \mathbb {N}$ המגודרת על פי $\psi (x)=f(x)$ היא חד חד ערכית.

משפט 4.7: לכל קבוצה אינסופית קיימת תת קבוצה שעוצמתה $\aleph _{0}$.

הוכחה: תהי A אינסופית. יהי $a_{0}\in A$. לכל n>0, נגדיר את $a_{n}$ כאיבר כלשהו בקבוצה $A\setminus \{a_{i}:i<n\}$. לא ייתכן שקבוצה זו ריקה, כי אז עוצמת הקבוצה A היא n לכל היותר, אבל A אינסופית. לכן האיבר $a_{n}$ מוגדר. הקבוצה $\{a_{n}:n\in \mathbb {N} \}$ היא תת קבוצה של A , ועוצמתה $\aleph _{0}$.

משפט 4.8: אם $A$ אינסופית ובת מנייה, אז $|A|=\aleph _{0}$.

הוכחה: A בת מנייה אם ורק אם היא סופית או שעוצמתה $\aleph _{0}$. מכיוון שהיא אינה סופית, נסיק ש$|A|=\aleph _{0}$.

קבוצות שאינן בנות מנייה

טענה: הקטע הפתוח $(0,1)$ אינו בן מנייה.

הוכחה: ברור שהקטע אינסופי, ונוכיח שאין פונקציה חד חד ערכית מקבוצת המספרים הטבעיים אליו. נניח בשלילה ש$f:\mathbb {N} \to (0,1)$ חד חד ערכית ועל. כל מספר ממשי x בקטע יסומן $x=0.x_{0}x_{1}x_{2}...\ (\forall n\in \mathbb {N} ,x_{n}\in \{0,1,2,3,4,5,6,7,8,9\})$. נגדיר את המספר הבא $\forall n\in \mathbb {N} ,a_{n}={\begin{cases}1&&f(n)_{n}=0\\0&&\mathrm {else} \end{cases}}$. המספר $a$ לא יכול להיות בתמונת הפונקציה f, כי אז יהי $f(n)=a$. מהגדרת a נובע ש$a_{n}\not =f(n)_{n}$, לכן $a\not =n$. מכאן שהפונקציה f אינה חד חד ערכית ועל, והקבוצה $(0,1)$ אינה בת מנייה.

כעת נוכיח מספר טענות:

טענה א: כל קטע פתוח בלתי מנוון (כלומר, יש בו יותר מאיבר אחד) שקול ל$(0,1)$.

הוכחה: יהי $(a,b)$ קטע פתוח בלתי מנוון. נגדיר את הפונקציה $f:(0,1)\to (a,b)$ כך: $f(x)=(b-a)x+a$. נראה שזו פונקציה חד חד ערכית: $f(x)=f(y)\Rightarrow (b-a)x+a=(b-a)y+a\Rightarrow (b-a)x=(b-a)y\Rightarrow x=y$. נראה שהיא על: לכל $y\in (a,b)$, יהי $x={\frac {y-a}{b-a}}$. מכיוון ש$a<y<b$, מתקיים $0<y-a<b-a$, ולכן גם $0<{\frac {y-a}{b-a}}<1$, כלומר $x\in (0,1)$.

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

טענה ב: $(0,\infty )\sim (0,1)$.

הוכחה: תהי $f:(0,\infty )\to (0,1)$ על פי $f(x)={\frac {x}{x+1}}$. נראה שהיא חח"ע: $f(x)=f(y)\Rightarrow {\frac {x}{x+1}}={\frac {y}{y+1}}\Rightarrow xy+x=xy+y\Rightarrow x=y$. נראה שהיא על: $y\in (0,1)\Rightarrow 0<y<1\Rightarrow y>0\land 1-y>0\Rightarrow {\frac {y}{1-y}}\in (0,\infty )$. בדיקה פשוטה תראה ש$f\left({\frac {y}{1-y}}\right)=y$.

טענה ג: $|(-\infty ,0]|=|(-1,0]|$.

הוכחה: $g:(-\infty ,0]\to (-1,0]:g(x)={\begin{cases}-f(-x)&&x\not =0\\0&&x=0\end{cases}}$.

טענה סופית: $\forall a<b,\mathbb {R} \sim (a,b)$.

הוכחה: $\psi :\mathbb {R} \to (-1,1):\psi (x)={\begin{cases}f(x)&&x\in (0,\infty )\\g(x)&&x\in (-\infty ,0]\end{cases}}$. מכיוון שכל שני קטעים פתוחים לא מנוונים הם שקולים, נקבל $\mathbb {R} \sim (a,b)$.

מסקנה: $\mathbb {R}$ אינה בת מנייה.

הגדרה: $\aleph :=|\mathbb {R} |$. מכיוון שקבוצת המספרים הממשיים אינה בת מנייה, נקבל $\aleph \not =\aleph _{0}$. סימונים נוספים לעוצמה זו הם $c,\beth _{1}$.

טענה: ${\mathcal {P}}(\mathbb {N} )$ - קבוצת החזקה של המספרים הטבעיים - אינה בת מנייה.

הוכחה: ממשפט 2.2, נקבל שאין פונקציה חד חד ערכית ועל בין $\mathbb {N}$ ל ${\mathcal {P}}(\mathbb {N} )$. ברור שקבוצת החזקה אינסופית, לכן היא אינה בת מנייה.

נביא משפטים נוספים על העוצמות $\aleph ,\aleph _{0}$.

טענה 4.9: $\mathbb {R} \setminus \mathbb {N} \sim \mathbb {R}$.

הוכחה: $\mathbb {Z} \setminus \mathbb {N} \sim \mathbb {N}$ ($\mathbb {Z} \setminus \mathbb {N}$ תת קבוצה של $\mathbb {Z}$, לכן היא בת מנייה, ובנוסף היא אינסופית). תהי $f:\mathbb {Z} \to \mathbb {Z} \setminus \mathbb {N}$ חד חד ערכית ועל. נגדיר $g:\mathbb {R} \to \mathbb {R} \setminus \mathbb {N}$ על פי $g(x)={\begin{cases}f(x)&&x\in \mathbb {Z} \\x&&x\in \mathbb {R} \setminus \mathbb {Z} \end{cases}}$. ניתן לראות בקלות שזו פונקציה חד חד ערכית ועל.

משפט 4.10: אם $|A|=\aleph$, ו$B$ בת מנייה, אז $|A\setminus B|=\aleph$.

הוכחה: $A\setminus B=A\setminus (A\cap B)$, לכן מספיק להניח כי $B\subset A$. $A\setminus B$ אינסופית, לכן תהי $C\subset A\setminus B$ שעוצמתה $\aleph _{0}$. $C\cup B$ איחוד של קבוצות בנות מנייה, לכן היא בת מנייה. תהי $h:B\cup C\to C$ חד חד ערכית ועל. נגדיר $f:A\setminus B\to A$ על ידי $f(x)={\begin{cases}h(x)&&x\in B\cup C\\x&&{\text{else}}\end{cases}}$. משימה לקורא היא להראות שf חד חד ערכית ועל.

טענה 4.11: $|\{0,1\}^{\mathbb {N} }|=\aleph$

הוכחה: נגדיר פונקציה $f:(0,1)\to \{0,1\}^{\mathbb {N} }$: את המספר $x\in (0,1)$ נעביר לכתיב בינארי $x=0.x_{0}x_{1}x_{2}...$ כאשר $x_{i}\in \{0,1\}$. מספר שממקום מסוים ואילך יש בו רק אחדות, ניתן להמיר במספר אחר באמצעות $0.x_{0}...x_{n}111...=0.x_{0}...x_{n}+0.\underbrace {00...0} _{n}11...=0.x_{0}...x_{n}+0.\underbrace {00...0} _{n-1}1$. כעת נגדיר $f(x)=f(0.x_{0}x_{1}x_{2}...)=(x_{0},x_{1},x_{2},...)$. ניתן לראות שזו פונקציה חח"ע, לכן $(0,1)\sim \mathrm {Im} (f)$. אם נסמן את קבוצת הסדרות של אפסים ואחדות עם מופע של אחד ממקום מסוים והלאה או שכל הסדרה אפסים ב$\{0,1\}^{\mathbb {N} *}$, נקבל $|(0,1)|=|\{0,1\}^{\mathbb {N} }\setminus \{0,1\}^{\mathbb {N} *}|$. הקבוצה $\{0,1\}^{\mathbb {N} *}$ היא תת קבוצה של $\mathbb {N} ^{*}$ - קבוצת הסדרות שנעשות קבועות ממקום מסוים, והיא אינסופית, לכן $|\{0,1\}^{\mathbb {N} *}|=\aleph _{0}$. נקבל: $|\{0,1\}^{\mathbb {N} }|=|(\{0,1\}^{\mathbb {N} }\setminus \{0,1\}^{\mathbb {N} *})\cup \{0,1\}^{\mathbb {N} *}|=|(0,1)\cup \mathbb {N} |=|(\mathbb {R} \setminus \mathbb {N} )\cup \mathbb {N} |=|\mathbb {R} |=\aleph$. (השתמשנו במשפט 4.0, ובכך ש$|\mathbb {R} \setminus \mathbb {N} |=\aleph$)

את טענה זו נוכל לנסח גם כ-${\mathcal {P}}(\mathbb {N} )\sim \mathbb {R}$.

סדר בין עוצמות

הגדרה: סדר חלש על עוצמות יחס הסדר $\leq$ על עוצמות יוגדר כך: יהו $A,B$ כך ש$|A|=\kappa ,|B|=\lambda$. נגדיר $\kappa \leq \lambda$ אם ורק אם קיימת $f:A\to B$ חד חד ערכית.

בהגדרה זו יש בעיה אחת, והיא שאנו צריכים להוכיח שהסדר לא תלוי בקבוצות שנבחרו. כלומר שאם $A\sim C,B\sim D$, וקיימת פונקצייה חד-חד-ערכית מA לB, אז קיימת פונקצייה חד-חד-ערכית מC לD. נוכיח זאת: יהו $f:A\to C,g:B\to D$ חד חד ערכיות ועל, ותהי $h:A\to B$ חד חד ערכית. הפונקציה $g\circ h\circ f^{-1}:C\to D$ היא חד חד ערכית, לכן ההגדרה שהבאנו קודם מוגדרת היטב, כלומר משמעות הביטוי $\kappa \leq \lambda$ לא תלויה בקבוצות שנבחרו.

לדוגמה, $\aleph _{0}\leq \aleph$, כי הפונקציה $f:\mathbb {N} \to \mathbb {R} :f(x)=x$ חד חד ערכית.

משפט 4.12: תכונות של הסדר על עוצמות יחס הסדר $\leq$ על עוצמות מקיים: רפלקסיביות: לכל עוצמה $\kappa$ מתקיים $\kappa \leq \kappa$. טרנזיטיביות: $\forall \kappa ,\lambda ,\mu :\kappa \leq \lambda \land \lambda \leq \mu \Rightarrow \kappa \leq \mu$. אנטי-סימטריה (משפט קנטר-שרדר-ברנשטיין) (נקרא גם כלל הסנדביץ'): $\kappa \leq \lambda \land \lambda \leq \kappa \Rightarrow \kappa =\lambda$. השוואה: $\forall \kappa ,\lambda :\kappa \leq \lambda \lor \lambda \leq \kappa$.

הוכחה: בכל הסעיפים נגדיר $|A|=\kappa ,|B|=\lambda ,|C|=\mu$.

1. הפונקציה $I:A\to A:I(x)=x$ חד חד ערכית.
2. יהו $f:A\to B,g:B\to C$ חד חד ערכיות. אז $g\circ f:A\to C$ חד חד ערכית.
3. קיימות הוכחות רבות למשפט, עליהן ניתן לקרוא כאן. נביא אחת מהן:

נניח ש-$f$ היא פונקציה חד-חד-ערכית מ-$A$ ל-$B$, וש-$g$ היא פונקציה חד-חד-ערכית מ-$B$ ל-$A$. כמו כן נניח, ללא הגבלת הכלליות שהקבוצות $A$ ו-$B$ זרות (נובע ממשפט 4.0). נראה שקיימת התאמה חד-חד-ערכית ועל בין שתי הקבוצות. נבנה עבור כל איבר $a$ של הקבוצה $A$, וכל איבר $b$ של הקבוצה $B$, סדרת איברים מ-$A$ ומ-$B$ לסירוגין, כך שכל איבר מתקבל על ידי החלת הפונקציה החד-חד-ערכית המתאימה על האיבר שקודם לו:

$\cdots \rightarrow f^{-1}(g^{-1}(a))\rightarrow g^{-1}(a)\rightarrow a\rightarrow f(a)\rightarrow g(f(a))\rightarrow \cdots$

נשים לב שניתן להמשיך את הסדרה ימינה ללא סוף, אך מאחר ש-$f^{-1}$ ו-$g^{-1}$ לא מוגדרות לכל איברי $B$ ו-$A$ בהתאמה, לא בהכרח ניתן להמשיך את הסדרה שמאלה עד אינסוף. הסדרות יכולות להסתיים משמאל באיבר של $A$, להסתיים משמאל באיבר של $B$, או להיות אינסופיות (או מעגליות) לשני הכיוונים. נסווג את הסדרות כסדרות קצה-$A$, סדרות קצה-$B$ או סדרות ללא קצה בהתאמה. מכיוון ש-$f$ ו-$g$ הן פונקציות חד-חד-ערכיות, לכל איבר בכל אחת מהקבוצות קיימת רק סדרה אחת כזו עד כדי זהות: אם איבר מופיע בשתי סדרות, כל האיברים מימינו ומשמאלו חייבים להיות זהים בשתיהן. הסדרות יוצרות חלוקה של האיחוד של $A$ ו-$B$. לכן מספיק לבנות פונקציה חד-חד-ערכית ועל מ-$A$ ל-$B$ בכל אחת מהסדרות בנפרד, ואת שאר העבודה יעשה לנו משפט 4.0.

כעת, נבנה את הפונקציה החד-חד-ערכית ועל $h$ מ-$A$ ל-$B$: עבור איברי $A$ ששייכים לסדרת קצה-$A$, נגדיר את $h(a)$ כ-$f(a)$ (כלומר, נלך צעד אחד ימינה בסדרה המתאימה לאיבר). עבור איברי $A$ ששייכים לסדרת קצה-$B$, נגדיר את $h(a)$ כ-$g^{-1}(a)$ (כלומר, נלך צעד אחד שמאלה בסדרה המתאימה לאיבר), ובאותו אופן נגדיר גם את $h$ עבור איברי $A$ ששייכים לסדרה ללא קצה. קל לראות שהפונקציה $h$ היא אכן חד-חד-ערכית ועל.

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

הגדרה: הסדר החזק על עוצמות נאמר כי $\kappa <\lambda$, אם ורק אם $\kappa \leq \lambda$ וגם $\kappa \not =\lambda$.

נחזור על משפט שכבר הובא בספר זה, בנוסח מעט אחר:

משפט: משפט 2.2: משפט קנטור לכל קבוצה $A$ מתקיים $|A|<|{\mathcal {P}}(A)|$.

הוכחה: נגדיר $g:A\to {\mathcal {P}}(A):g(x)=\{x\}$ חד חד ערכית, לכן $|A|\leq |{\mathcal {P}}(A)|$. נראה שלא קיימת פונקציה חד חד ערכית ועל בין הקבוצות. תהי $f:A\to {\mathcal {P}}(A)$, ונראה שהיא אינה על: נגדיר $D=\{x:x\not \in f(x)\}$. נניח בשלילה שקיים d כך ש$f(d)=D$. נשאל את השאלה: האם $d\in D$? אם $d\in D$, משמע ש$d\not \in f(d)=D$, לכן לא ייתכן $d\in D$. אם $d\not \in D$, אז $d\not \in f(d)$, לכן $d\in D$. לכן לא ייתכן $d\not \in D$, וקיבלנו סתירה. לכן $|A|\not =|{\mathcal {P}}(A)|$, ובסוף $|A|<|{\mathcal {P}}(A)|$.

מסקנה: קיימות אינסוף עוצמות אינסופיות, ולכל עוצמה קיימת עוצמה גדולה ממנה.

משפט 4.12.1: תכונות הסדר החזק על עוצמות הסדר החזק $<$ על עוצמות מקיים: אנטי רפלקסיביות: $\forall \kappa ,\kappa \not <\kappa$. א-סימטריה: $\kappa <\lambda \Rightarrow \lambda \not <\kappa$. טרנזיטיביות: $\kappa <\lambda \land \lambda <\mu \Rightarrow \kappa <\mu$. השוואה: $\forall \kappa ,\lambda :\kappa <\lambda \lor \lambda <\kappa \lor \kappa =\lambda$.

תרגיל: הוכיחו את משפט 4.12.1

פתרון

1. $\kappa =\kappa \Rightarrow \kappa \not <\kappa$.
2. $\kappa <\lambda \land \lambda <\kappa \Rightarrow \kappa \leq \lambda \land \lambda \leq \kappa \land \kappa \not =\lambda \Rightarrow \kappa =\lambda \land \kappa \not =\lambda$. סתירה.
3. $\kappa <\lambda \land \lambda <\mu \Rightarrow \kappa \leq \lambda \land \lambda \leq \mu \Rightarrow \kappa \leq \mu$. נניח ש$\kappa =\mu$. נקבל $\mu <\lambda \land \lambda <\mu$, מה שלא ייתכן, כי היחס א-סימטרי. לכן $\kappa <\mu$.
4. לכל $\kappa ,\lambda$ מתקיים: $\kappa =\lambda \lor \kappa \not =\lambda \Rightarrow \kappa =\lambda \lor (\kappa \not =\lambda \land (\kappa \leq \lambda \lor \lambda \leq \kappa ))\Rightarrow \kappa =\lambda \lor \kappa <\lambda \lor \lambda <\kappa$.

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

חיבור עוצמות

הגדרה: חיבור עוצמות יהו $|A|=\kappa ,|B|=\lambda$, קבוצות זרות. נגדיר את הסכום של העוצמות כך: $\kappa +\lambda =|A|+|B|=|A\cup B|$.

בהגדרה זו יש שתי בעיות: א. מניין לנו שיש קבוצות זרות שעוצמותיהן $\kappa ,\lambda$? ב. עלינו להראות שהחיבור לא תלוי בקבוצות שנבחרו. נפתור את הבעיה הראשונה: אם $|A|=\kappa ,|B|=\lambda$, אז $|A\times \{0\}|=\kappa ,|B\times \{1\}|=\lambda$, והקבוצות $A\times \{0\},B\times \{1\}$ זרות.

תרגיל: הראו שהחיבור לא תלוי בקבוצות שנבחרו.

דוגמאות:

• $|2\mathbb {N} |=|2\mathbb {N} +1|=\aleph _{0}$, לכן $\aleph _{0}+\aleph _{0}=|2\mathbb {N} \cup 2\mathbb {N} +1|=|\mathbb {N} |=\aleph _{0}$.
• $|\mathbb {R} \setminus \mathbb {N} |=\aleph$, לכן $\aleph +\aleph _{0}=\aleph$.

פתרון

ממשפט 4.0 נקבל כי $|A|+|B|=|A\cup B|=|C\cup D|=|C|+|D|$.

משפט 4.13: תכונות החיבור החיבור מקיים את התכונות הבאות: קומוטטיביות: $\kappa +\lambda =\lambda +\kappa$. אסוציאטיביות: $\kappa +(\lambda +\mu )=(\kappa +\lambda )+\mu$. מעתה נסמן פשוט $\kappa +\lambda +\mu$. איבר אפס: $\kappa +0=\kappa$. איזוטוניות: $\kappa \leq \lambda \Rightarrow \kappa +\mu \leq \lambda +\mu$.

תרגיל: הוכיחו את משפט 4.13.

פתרון

נגדיר $|A|=\kappa ,|B|=\lambda ,|C|=\mu$, כאשר כל הקבוצות זרות.

1. $\kappa +\lambda =|A|+|B|=|A\cup B|=|B\cup A|=|B|+|A|=\lambda +\kappa$.
2. $\kappa +(\lambda +\mu )=|A\cup (B\cup C)|=|(A\cup B)\cup C|=(\kappa +\lambda )+\mu$.
3. $\kappa +0=|A\cup \emptyset |=|A|=\kappa$.
4. תהי $f:A\to B$ חח"ע. אז נגדיר $g:A\cup C\to B\cup C:g(x)={\begin{cases}f(x)&&x\in A\\x&&x\in C\end{cases}}$.

כפל עוצמות

הגדרה: כפל עוצמות יהו $|A|=\kappa ,|B|=\lambda$. נגדיר את המכפלה $\kappa \cdot \lambda$ (ובקיצור: $\kappa \lambda$), כך: $\kappa \cdot \lambda =|A\times B|$.

תרגיל: הראו כי ההגדרה לא תלויה בקבוצות שנבחרו.

דוגמאות:

• $\aleph _{0}\cdot \aleph _{0}=|\mathbb {N} \times \mathbb {N} |=\aleph _{0}$.
• $2\aleph _{0}=|\{0,1\}\times \mathbb {N} |=|\{0\}\times \mathbb {N} \cup \{1\}\times \mathbb {N} |=|\mathbb {N} |+|\mathbb {N} |=\aleph _{0}+\aleph _{0}=\aleph _{0}$.

פתרון

נניח כי $f:A\to C,g:B\to D$ חח"ע ועל. נגדיר $h:A\times B\to C\times D$ על פי $h(x,y)=(f(x),g(y))$. זוהי פונקציה חח"ע ועל, לכן $|A|\cdot |B|=|A\times B|=|C\times D|=|C|\cdot |D|$.

משפט 4.14: תכונות הכפל פעולת הכפל מקיימת: קומוטטיביות: $\kappa \lambda =\lambda \kappa$. אסוציאטיביות: $\kappa (\lambda \mu )=(\kappa \lambda )\mu$. להבא נאמר פשוט $\kappa \lambda$.ץ דיסטריבוטיביות: $\kappa (\lambda +\mu )=\kappa \lambda +\kappa \mu$. איבר יחידה: $1\cdot \kappa =\kappa$. איבר מאפס: $0\cdot \kappa =0$. איזוטוניות: $\kappa \leq \lambda \Rightarrow \kappa \mu \leq \lambda \mu$.

תרגיל: הוכיחו את משפט 4.14.

פתרון

יהו $|A|=\kappa ,|B|=\lambda ,|C|=\mu$.

1. נגדיר פונקציה $t:A\times B\to B\times A$ על פי $t(x,y)=(y,x)$.ניתן לראות בקלות שהיא חח"ע ועל.
2. נגדיר $f:A\times (B\times C)\to (A\times B)\times C$ על פי $f(x,(y,z))=((x,y),z)$. ניתן לראות בקלות שהיא חח"ע ועל.
3. $\kappa (\lambda +\mu )=|A|(|B|+|C|)=|A||B\cup C|=|A\times (B\cup C)|=|A\times B\cup A\times C|=|A\times B|+|A\times C|=|A||B|+|A||C|=\kappa \lambda +\kappa \mu$. (בסעיף זה הנחנו גם כי $B,C$ זרות).
4. נגדיר $f:\{0\}\times A\to A:f(0,x)=x$. קל לראות שהיא חח"ע ועל, לכן $1\cdot \kappa =|\{0\}\times A|=|A|=\kappa$.
5. $0\cdot \kappa =|\emptyset \times A|=|\emptyset |=0$.
6. נניח כי $f:A\to B$ חח"ע. נגדיר $g:A\times C\to B\times C$ על ידי $g(x,y)=(f(x),y)$. ניתן לראות בקלות שהיא חח"ע.

חזקה של עוצמות

הגדרה: חזקה של עוצמות יהו $|A|=\kappa ,|B|=\lambda$. נגדיר $\kappa ^{\lambda }=|A^{B}|$. (שימו לב, $A^{B}$ היא קבוצת כל הפונקציות מ$B$ ל$A$.

תרגיל: הוכיחו כי ההגדרה לא תלויה בקבוצות שנבחרו.

פתרון

יהו $g:A\to C,h:B\to D$ חח"ע ועל. נגדיר את הפונקציה $\psi :A^{B}\to C^{D}$ על ידי $\psi (f)=g^{-1}\circ f\circ h$. מכיוון ש$f,g^{-1}$ חח"ע ועל, אז הן מצטמצמות, ולכן $\psi (x)=\psi (y)\Rightarrow x=y$, ולכן הפונקציה חח"ע. ניתן לראות בקלות שהיא על.

דוגמאות:

• $2^{|A|}=|\{0,1\}^{A}|=|{\mathcal {P}}(A)|$.
• $2^{\aleph _{0}}=\aleph$.

משפט 4.15: תכונות החזקה של עוצמות פעולת החזקה של עוצמות מקיימת: $\kappa ^{\lambda }\cdot \kappa ^{\mu }=\kappa ^{\lambda +\mu }$. $\kappa ^{\mu }\cdot \lambda ^{\mu }=(\kappa \cdot \lambda )^{\mu }$. $(\kappa ^{\lambda })^{\mu }=\kappa ^{\lambda \cdot \mu }$. $\kappa ^{1}=\kappa$. $\kappa ^{0}=1$. $1^{\kappa }=1$. $0^{\kappa }={\begin{cases}0&&\kappa \not =0\\1&&\kappa =0\end{cases}}$. (שימו לב: הביטוי $0^{0}$ אינו מוגדר באנליזה המתמטית, אך בתורת הקבוצות הוא מוגדר ושווה ל1)

הוכחה: יהו $|A|=\kappa ,|B|=\lambda ,|C|=\mu$.

1. נניח ש$B,C$ זרות, ונגדיר $\psi :A^{B}\times A^{C}\to A^{B\cup C}$ כך: $\psi (f,g)$ היא הפונקציה $h:B\cup C\to A$ המקיימת $h(x)={\begin{cases}f(x)&&x\in B\\g(x)&&x\in C\end{cases}}$. הראו שהיא חח"ע ועל.
2. נגדיר $\psi :A^{C}\times B^{C}\to (A\times B)^{C}$ כך: $\psi (f,g)$ היא הפונקציה $h:C\to A\times B$ המקיימת $h(x)=(f(x),g(x))$. הראו שהיא חח"ע ועל.
3. נגדיר $\psi :(A^{B})^{C}\to A^{B\times C}$ כך: $\psi (f)$ היא הפונקציה $g:B\times C\to A$ המוגדרת $g(x,y)=f(y)(x)$ (שימו לב, $f(y)$ היא פונקציה). הראו שהיא חח"ע ועל.
4. נגדיר $\psi :A^{\{0\}}\to A$ כך: $\psi (f)=f(0)$.
5. הפונקציה היחידה $f:\emptyset \to A$ היא הפונקציה $f=\{\}=\emptyset$, לכן $|A^{\emptyset }|=1$.
6. הפונקציה היחידה $f:A\to \{0\}$ היא $f(x)=0$, לכן $|\{0\}^{A}|=1$.
7. אם $A\not =\emptyset$, אז לא קיימת פונקציה $f:A\to \emptyset$, כי פונקציה צריכה להיות מוגדרת לכל x. אם $A=\emptyset$, אז הפונקציה $\emptyset :\emptyset \to \emptyset$ היא פונקציה, לכן $|\emptyset ^{\emptyset }|=1$.

הפרק הקודם: יחסי סדר

עוצמות תרגילים

הפרק הבא: סדרות של קבוצות