תורת הקבוצות/עוצמות: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
אין תקציר עריכה
אין תקציר עריכה
שורה 1:
'''עוצמה''' היא מדד לגודל הקבוצה, גם אם הקבוצה אינסופית. אם הקבוצה סופית, אז עוצמה שלה היא מספר האיברים בה. כך למשל, העוצמה של הקבוצה <math>\{0,1,2\}</math> היא 3, ונסמן <math>|\{0,1,2\}|=3</math>. נאמר שלשתי קבוצות יש את אותה עוצמה, אם הן שקולות, כלומר יש פונקציה חד חד ערכית ועל ביניהן. כך למשל, הפונקציה <math>S:\N\to\N\setminus\{0\}</math> המוגדרת על פי <math>S(n)=n+1</math>, היא חד חד ערכית ועל, לכן נאמר כי <math>|\N|=|\N\setminus\{0\}|</math>. קבוצה תיקרא '''אינסופית''' אם יש לה תת קבוצה ממש בעלת אותה עוצמה. הפונקציה שהבאנו קודם מראה כי קבוצת המספרים הטבעיים אינסופית.
 
{{משפט|שם=משפט 3.1|תוכן=אם <math>|A|=|B|,|C|=|D|</math> והקבוצות <math>A,C</math> זרות ו<math>B,D</math> זרות, אז <math>|A\cup C|=|B\cup D|</math>.}}
 
הוכחה: יהו <math>f:A\to B,g:C\to D</math> חד חד ערכיות ועל. נגדיר <math>\psi:A\cup C\to B\cup D:\psi(x)=\begin{cases}f(x)&&x\in A\\g(x)&&x\in C\end{cases}</math>. זוהי פונקציה חד חד ערכית ועל.
==<math>\aleph_0</math> וקבוצה בת מנייה==
{{הגדרה|שם=<math>\aleph_0</math> וקבוצה בת מנייה|תוכן=<math>\aleph_0</math> (קרי: '''אָלֶף אֶפֶס''') הוא הסימון המקובל לעוצמת הקבוצה <math>\N</math>, כלומר <math>|\N|=\aleph_0</math>. נאמר כי קבוצה היא '''בת מנייה''', אם היא סופית, או שעוצמתה <math>\aleph_0</math>. }}
כך למשל, <math>\Z</math>, קבוצת המספרים השלמים, היא בת מנייה, כי הפונקציה <math>f:\Z\to\N</math> המוגדרת <math>f(x)=\begin{cases}2x&&x\geq0\\2|x|+1&&x<0\end{cases}</math> היא חד חד ערכית ועל, לכן <math>|\Z|=|\N|=\aleph_0</math>. השם '''קבוצה בת מנייה''' בא לומר שניתן למנות את איברי הקבוצה בזה אחר זה (כלומר, לשכנם בסדרה) בלי לפספס אף איבר. אין משמעות העניין שהמנייה חייבת להסתיים מתישהו, אלא שכל איבר יגיע לאחר מספר סופי של צעדים. המנייה תיעשה על פי <math>f(0),f(1),f(2),...</math> כאשר <math>f:\N\to A</math> היא חד חד ערכית ועל (קיימת כזו כי הקבוצה בת מנייה). אם A סופית, כמובן שניתן למנות את איבריה, בכל סדר שנרצה, ותמיד לא נפספס אף איבר. גם ההיפך נכון - אם ניתן למנות איברי קבוצה בצורה הזו, אז יש פונקציה חד חד ערכית ועל ממנה לקבוצת המספרים הטבעיים: נניח שהמנייה היא <math>a_0,a_1,a_2,...</math> כאשר לכל i, <math>a_i\in A</math>. אז הפונקציה <math>f(a_n)=n</math> היא חד חד ערכית ועל (אם <math>f(a_n)=f(a_m)</math> אז בהכרח <math>n=m</math>. כמו כן, כל מספר טבעי יופיע בתמונת הפונקציה, כי הקבוצה אינסופית והמנייה לא מדלגת על אף מספר טבעי), ואז <math>|A|=\aleph_0</math>.
 
'''{{משפט|שם=משפט''': 3.2|תוכן=קבוצה <math>A</math> היא בת מנייה, אם ורק אם קיימת פונקציה <math>f:A\to\N</math> חח"ע.}}
 
'''הוכחה''': נניח שA בת מנייה. אז או שהיא סופית, ואז נסמן <math>A=\{a_0,...,a_n\}</math> את כל איברי A עבור n כלשהו, שהוא <math>|A|+1</math>. הפונקציה <math>f:A\to\N:f(a_i)=i</math> היא חח"ע. המקרה השני הוא ש<math>|A|=\aleph_0</math>, ואז <math>|A|=|\N|</math> ולכן קיימת <math>f:a\to\N</math> חח"ע ועל, ובפרט חח"ע. נניח שקיימת פונקציה חד חד ערכית <math>f:A\to\N</math>. אם A סופית המקרה טריוויאלי. לכן נניח שA אינסופית. נסמן <math>B=\mathrm{Im}(f)</math>. מכיוון שf חח"ע, <math>|B|=|A|</math>, ואז B אינסופית גם כן. נגדיר פונקציה <math>g:B\to\N</math> כך: <math>g(x)=|\{y\in B:y<x\}|</math>. נראה כי פונקציה זו חח"ע: נניח ש<math>x\not=y</math>. נניח ללא הגבלת הכלליות ש<math>x<y</math>. אז <math>x\in\{z\in B:z<y\}</math>, לכן <math>\{z\in B:z<x\}\subset\{z\in B:z<y\}</math>. מכיוון שהקבוצות סופיות, מתקיים <math>|\{z\in B:z<x\}|<|\{z\in B:z<y\}|</math>, לכן <math>g(x)<g(y)</math> ובפרט <math>g(x)\not=g(y)</math>. נראה כי פונקציה זו היא על: נשתמש בכך שלכל קבוצה לא ריקה של מספרים טבעיים, יש איבר ראשון. נוכיח באינדוקציה על n, שיש איבר שn הוא הדמות שלו על ידי g. עבור n=0 - <math>g(a)=0</math> כאשר a הוא האיבר הראשון בקבוצה B. יהי n>0: אז יהי b האיבר הראשון בקבוצה <math>B\setminus\{g^{-1}(x):x<n\}</math> (הקבוצה קיימת על פי הנחת האינדוקציה). אז מתקיים <math>g(b)=n</math>. לכן <math>|A|=|B|=|\N|=\aleph_0</math>, ואז A בת מנייה.
שורה 11 ⟵ 13:
באמצעות משפט זה נוכל להחליף בכל מקום את "A סופית או שעוצמתה אלף אפס" בנוסח הנוח היותר של "קיימת פונקציה חד חד ערכית בינה לבין קבוצת המספרים הטבעיים".
===איחוד, חיתוך, ומכפלה קרטזית של קבוצות בנות מנייה===
'''{{משפט'''|שם=משפט 3.3: איחוד של קבוצות בנות מנייה|תוכן=אם <math>A,B</math> בנות מנייה, אז <math>A\cup B</math> בת מנייה.}}
 
'''הוכחה''': יהו <math>f:A\to\N,g:B\to\N</math> חד חד ערכיות. נגדיר פונקציות <math>p:\N\to2\N,q:\N\to2\N+1</math> (<math>2\N=\{2n:n\in\N\}</math>, וכן <math>2\N+1=\{2n+1:n\in\N\}</math>) על פי <math>p(n)=2n,q(n)=2n+1</math>. שתי פונקציות אלו חד חד ערכיות, ותמונותיהן זרות, לכן נוכל להגדיר פונקציה <math>\psi:A\cup B\to\N</math> על פי <math>\psi(x)=\begin{cases}(p\circ f)(x)&&x\in A\\(q\circ g)(x)&&x\in B\setminus A\end{cases}</math>, שהיא גם כן חד חד ערכית. לכן <math>|A\cup B|=\aleph_0</math>.
 
'''{{משפט'''|שם=משפט 3.3.1: איחוד בן מנייה של קבוצות בנות מנייה|תוכן=אם לכל n טבעי, <math>A_n</math> בת מנייה, אז <math>\bigcup^\infty_{n=0}A_n</math> נוסח אחר: איחוד בן מנייה של קבוצות בנות מנייה הוא בן מנייה.}}
 
'''הוכחה''': לכל n טבעי, תהי <math>f_n:A_n\to\N</math> חד חד ערכית. נגדיר את הפונקציה <math>f:\bigcup^\infty_{n=0}A_n\to\N</math> על פי <math>f(x)=p_n^{f_n(x)}</math> כאשר <math>x\in A_n</math> ו<math>p_n</math> הוא הראשוני הn. מתכונת הפירוק היחיד של המספרים הטבעיים, נקבל שf חד חד ערכית.
 
'''{{משפט'''|שם=משפט 3.4: חיתוך של קבוצות בנות מנייה|תוכן=חיתוך של קבוצה בת מנייה עם קבוצה כלשהי הוא בן מנייה.}}
 
'''הוכחה''': מתקיים <math>A\cap B\subseteq A</math>, לכן יש פונקציה <math>g:A\cap B\to A</math> חד חד ערכית (על פי <math>g(x)=x</math>). בנוסף, תהי <math>f:A\to\N</math> חד חד ערכית. אז הפונקציה <math>f\circ g</math> חד חד ערכית, לכן <math>A\cap B</math> בת מנייה.
 
'''{{משפט'''|שם=משפט 3.5: מכפלה קרטזית של קבוצות בנות מנייה|תוכן=מכפלה קרטזית של קבוצות בנות מנייה היא בת מנייה.}}
 
'''הוכחה''': נתבונן בקבוצה <math>\N\times\N</math>. נוכל למנות את איבריה כך: [[קובץ:Rationals.png|250px]] לכן <math>|\N\times\N|=\aleph_0</math>. המנייה המתוארת ניתנת לביטוי גם באמצעות הפונקציה: <math>\pi(k_1,k_2) := \frac{1}{2}(k_1 + k_2)(k_1 + k_2 + 1)+k_2.</math>. ראו הוכחה [[w:פונקציית זיווג#היפוך פונקציית הזיווג|כאן]] לכך שהפונקציה חד חד ערכית ועל. כעת, אם <math>f:A\to\N,g:B\to\N</math> חד חד ערכיות, אז הפונקצייה <math>\psi:A\times B\to\N</math> המוגדרת על פי <math>\psi(x,y)=\pi(f(x),g(y))</math> היא חד חד ערכית.
 
===משפטים נוספים על קבוצות בנות מנייה===
'''{{משפט|שם=משפט''': 3.6|תוכן=תת קבוצה של קבוצה בת מנייה היא בת מנייה.}}
 
'''הוכחה''': תהי <math>f:A\to\N</math> חד חד ערכית, ותהי <math>B\subseteq A</math>. אז הפונקציה <math>\psi:B\to\N</math> המגודרת על פי <math>\psi(x)=f(x)</math> היא חד חד ערכית.
 
'''{{משפט|שם=משפט''': 3.7|תוכן=לכל קבוצה אינסופית קיימת תת קבוצה שעוצמתה <math>\aleph_0</math>.}}
 
'''הוכחה''': תהי A אינסופית. יהי <math>a_0\in A</math>. לכל n>0, נגדיר את <math>a_n</math> כאיבר כלשהו בקבוצה <math>A\setminus\{a_i:i<n\}</math>. לא ייתכן שקבוצה זו ריקה, כי אז עוצמת הקבוצה A היא n לכל היותר, אבל A אינסופית. לכן האיבר <math>a_n</math> מוגדר. הקבוצה <math>\{a_n:n\in\N\}</math> היא תת קבוצה של A , ועוצמתה <math>\aleph_0</math>.
 
'''{{משפט|שם=משפט''': 3.8|תוכן=אם <math>A</math> אינסופית ובת מנייה, אז <math>|A|=\aleph_0</math>.}}
 
'''הוכחה''': A בת מנייה אם ורק אם היא סופית או שעוצמתה <math>\aleph_0</math>. מכיוון שהיא אינה סופית, נסיק ש<math>|A|=\aleph_0</math>.
שורה 73 ⟵ 75:
 
נביא משפטים נוספים על העוצמות <math>\aleph,\aleph_0</math>.
'''{{משפט|שם=משפט''': 3.8|תוכן=<math>\R\setminus\N\sim\R</math>.}}
 
'''הוכחה''': <math>\Z\setminus\N\sim\N</math> (<math>\Z\setminus\N</math> תת קבוצה של <math>\Z</math>, לכן היא בת מנייה, ובנוסף היא אינסופית). תהי <math>f:\Z\to\Z\setminus\N</math> חד חד ערכית ועל. נגדיר <math>g:\R\to\R\setminus\N</math> על פי <math>g(x)=\begin{cases}f(x)&&x\in\Z\\x&&x\in\R\setminus\Z\end{cases}</math>. ניתן לראות בקלות שזו פונקציה חד חד ערכית ועל.
 
'''{{משפט|שם=משפט''': 3.9|תוכן=אם <math>|A|=\aleph</math>, ו<math>B</math> בת מנייה, אז <math>|A\setminus B|=\aleph</math>.}}
 
'''הוכחה''': <math>A\setminus B=A\setminus(A\cap B)</math>, לכן מספיק להניח כי <math>B\subset A</math>. <math>A\setminus B</math> אינסופית, לכן תהי <math>C\subset A\setminus B</math> שעוצמתה <math>\aleph_0</math>. <math>C\cup B</math> איחוד של קבוצות בנות מנייה, לכן היא בת מנייה. תהי <math>h:B\cup C\to C</math> חד חד ערכית ועל. נגדיר <math>f:A\setminus B\to A</math> על ידי <math>f(x)=\begin{cases}h(x)&&x\in B\cup C\\x&&\text{else}\end{cases}</math>. משימה לקורא היא להראות שf חד חד ערכית ועל.
שורה 86 ⟵ 88:
לדוגמה, <math>\aleph_0\leq\aleph</math>, כי הפונקציה <math>f:\N\to\R:f(x)=x</math> חד חד ערכית.
 
{{משפט|שם=משפט 3.10: תכונות של הסדר על עוצמות|תוכן=יחס הסדר <math>\leq</math> על עוצמות מקיים:
# '''רפלקסיביות''': לכל עוצמה <math>\kappa</math> מתקיים <math>\kappa\leq\kappa</math>.
# '''טרנזיטיביות''': <math>\forall \kappa,\lambda,\mu:\kappa\leq\lambda\land\lambda\leq\mu\Rightarrow\kappa\leq\mu</math>.
שורה 95 ⟵ 97:
# יהו <math>f:A\to B,g:B\to C</math> חד חד ערכיות. אז <math>g\circ f:A\to C</math> חד חד ערכית.
# קיימות הוכחות רבות למשפט, עליהן ניתן לקרוא [[w:משפט קנטור-שרדר-ברנשטיין|כאן]]. נביא אחת מהן:
:נניח ש-{\displaystyle f}<math>f</math> היא פונקציה חד-חד-ערכית מ-{\displaystyle A}<math>A</math> ל-{\displaystyle B}<math>B</math>, וש-{\displaystyle g}<math>g</math> היא פונקציה חד-חד-ערכית מ-{\displaystyle B}<math>B</math> ל-{\displaystyle A}<math>A</math>. כמו כן נניח, [[ללא הגבלת הכלליות]] שהקבוצות {\displaystyle A}<math>A</math> ו-{\displaystyle B}B זרות (אחרת מספיק להוכיח ש<math>|A\setminus B|=|B\setminus A|</math>, ואזזרות מאיחוד(נובע קבוצותממשפט נקבל שוויון3.1). נראה שקיימת התאמה חד-חד-ערכית ועל בין שתי הקבוצות. נבנה עבור כל איבר {\displaystyle a}<math>a</math> של הקבוצה {\displaystyle A}<math>A</math>, וכל איבר {\displaystyle b}<math>b</math> של הקבוצה {\displaystyle B}<math>B</math>, סדרת איברים מ-{\displaystyle A}<math>A</math> ומ-{\displaystyle B}<math>B</math> לסירוגין, כך שכל איבר מתקבל על ידי החלת הפונקציה החד-חד-ערכית המתאימה על האיבר שקודם לו:
 
:{\displaystyle \cdots \rightarrow f^{-1}(g^{-1}(a))\rightarrow g^{-1}(a)\rightarrow a\rightarrow f(a)\rightarrow g(f(a))\rightarrow \cdots }::''<math> \cdots \rightarrow f^{-1}(g^{-1}(a)) \rightarrow g^{-1}(a) \rightarrow a \rightarrow f(a) \rightarrow g(f(a)) \rightarrow \cdots </math>''
 
:נשים לב שניתן להמשיך את הסדרה ימינה ללא סוף, אך מאחר ש-{\displaystyle <math>f^{-1}}{\displaystyle f^{-1}}</math> ו-{\displaystyle <math>g^{-1}}{\displaystyle g^{-1}}</math> לא מוגדרות לכל איברי {\displaystyle B}<math>B</math> ו-{\displaystyle A}<math>A</math> בהתאמה, לא בהכרח ניתן להמשיך את הסדרה שמאלה עד אינסוף. הסדרות יכולות להסתיים משמאל באיבר של {\displaystyle A}<math>A</math>, להסתיים משמאל באיבר של {\displaystyle B}<math>B</math>, או להיות אינסופיות (או מעגליות) לשני הכיוונים. נסווג את הסדרות כסדרותכ'''סדרות קצה-{\displaystyle A}<math>A</math>''', '''סדרות קצה-{\displaystyle B}<math>B</math>''' או '''סדרות ללא קצה''' בהתאמה. מכיוון ש-{\displaystyle f}<math>f</math> ו-{\displaystyle g}<math>g</math> הן פונקציות חד-חד-ערכיות, לכל איבר בכל אחת מהקבוצות קיימת רק סדרה אחת כזו עד כדי זהות: אם איבר מופיע בשתי סדרות, כל האיברים מימינו ומשמאלו חייבים להיות זהים בשתיהן. הסדרות יוצרות [[חלוקה (תורת הקבוצות)|חלוקה]] של האיחודה[[איחוד (מתמטיקה)|איחוד]] של {\displaystyle A}<math>A</math> ו-{\displaystyle B}<math>B</math>. לכן מספיק לבנות פונקציה חד-חד-ערכית ועל מ-{\displaystyle A}<math>A</math> ל-{\displaystyle B}<math>B</math> בכל אחת מהסדרות בנפרד.
:{\displaystyle \cdots \rightarrow f^{-1}(g^{-1}(a))\rightarrow g^{-1}(a)\rightarrow a\rightarrow f(a)\rightarrow g(f(a))\rightarrow \cdots } \cdots \rightarrow f^{-1}(g^{-1}(a)) \rightarrow g^{-1}(a) \rightarrow a \rightarrow f(a) \rightarrow g(f(a)) \rightarrow \cdots
נשים לב שניתן להמשיך את הסדרה ימינה ללא סוף, אך מאחר ש-{\displaystyle f^{-1}}{\displaystyle f^{-1}} ו-{\displaystyle g^{-1}}{\displaystyle g^{-1}} לא מוגדרות לכל איברי {\displaystyle B}B ו-{\displaystyle A}A בהתאמה, לא בהכרח ניתן להמשיך את הסדרה שמאלה עד אינסוף. הסדרות יכולות להסתיים משמאל באיבר של {\displaystyle A}A, להסתיים משמאל באיבר של {\displaystyle B}B, או להיות אינסופיות (או מעגליות) לשני הכיוונים. נסווג את הסדרות כסדרות קצה-{\displaystyle A}A, סדרות קצה-{\displaystyle B}B או סדרות ללא קצה בהתאמה. מכיוון ש-{\displaystyle f}f ו-{\displaystyle g}g הן פונקציות חד-חד-ערכיות, לכל איבר בכל אחת מהקבוצות קיימת רק סדרה אחת כזו עד כדי זהות: אם איבר מופיע בשתי סדרות, כל האיברים מימינו ומשמאלו חייבים להיות זהים בשתיהן. הסדרות יוצרות חלוקה של האיחוד של {\displaystyle A}A ו-{\displaystyle B}B. לכן מספיק לבנות פונקציה חד-חד-ערכית ועל מ-{\displaystyle A}A ל-{\displaystyle B}B בכל אחת מהסדרות בנפרד.
 
:כעת, נבנה את הפונקציה החד-חד-ערכית ועל {\displaystyle h}<math>h</math> מ-{\displaystyle A}<math>A</math> ל-{\displaystyle B}<math>B</math>: עבור איברי {\displaystyle A}<math>A</math> ששייכים לסדרת קצה-{\displaystyle A}<math>A</math>, נגדיר את {\displaystyle <math>h(a)}{\displaystyle h(a)}</math> כ-{\displaystyle <math>f(a)}{\displaystyle f(a)}</math> (כלומר, נלך צעד אחד ימינה בסדרה המתאימה לאיבר). עבור איברי {\displaystyle A}<math>A</math> ששייכים לסדרת קצה-{\displaystyle B}<math>B</math>, נגדיר את {\displaystyle <math>h(a)}{\displaystyle h(a)}</math> כ-{\displaystyle <math>g^{-1}(a)}{\displaystyle g^{-1}(a)}</math> (כלומר, נלך צעד אחד שמאלה בסדרה המתאימה לאיבר), ובאותו אופן נגדיר גם את {\displaystyle h}<math>h</math> עבור איברי {\displaystyle A}<math>A</math> ששייכים לסדרה ללא קצה. קל לראות שהפונקציה {\displaystyle h}<math>h</math> היא אכן חד-חד-ערכית ועל.