תורת הקבוצות/עוצמות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
בנציון יעבץ (שיחה | תרומות) |
בנציון יעבץ (שיחה | תרומות) אין תקציר עריכה |
||
שורה 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>. קבוצה תיקרא '''אינסופית''' אם יש לה תת קבוצה ממש בעלת אותה עוצמה. הפונקציה שהבאנו קודם מראה כי קבוצת המספרים הטבעיים אינסופית.
==<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>.
שורה 78 ⟵ 80:
'''הוכחה''': <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 חד חד ערכית ועל.
==סדר בין עוצמות==
{{הגדרה|שם=סדר חלש על עוצמות|תוכן=יחס הסדר <math>\le</math> על עוצמות יוגדר כך: יהו <math>A,B</math> כך ש<math>|A|=\kappa,|B|=\lambda</math>. '''נגדיר <math>\kappa\leq\lambda</math>''' אם ורק אם קיימת <math>f:A\to B</math> חד חד ערכית.}}
בהגדרה זו יש בעיה אחת, והיא שאנו צריכים להוכיח שהסדר לא תלוי בקבוצות שנבחרו. כלומר שאם <math>A\sim C,B\sim D</math>, וקיימת פונקצייה חד-חד-ערכית מA לB, אז קיימת פונקצייה חד-חד-ערכית מC לD. נוכיח זאת: יהו <math>f:A\to C,g:B\to D</math> חד חד ערכיות ועל, ותהי <math>h:A\to B</math> חד חד ערכית. הפונקציה <math>g\circ h\circ f^{-1}:C\to D</math> היא חד חד ערכית, לכן ההגדרה שהבאנו קודם מוגדרת היטב, כלומר משמעות הביטוי <math>\kappa\leq\lambda</math> לא תלויה בקבוצות שנבחרו.
לדוגמה, <math>\aleph_0\leq\aleph</math>, כי הפונקציה <math>f:\N\to\R:f(x)=x</math> חד חד ערכית.
{{משפט|שם=תכונות של הסדר על עוצמות|תוכן=יחס הסדר <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>.
# '''אנטי-סימטריה (משפט קנטר-שרדר-ברנשטיין)''': <math>\kappa\leq\lambda\land\lambda\leq\kappa\Rightarrow \kappa=\lambda</math>.
# '''השוואה''': <math>\forall \kappa,\lambda:\kappa\leq\lambda\lor\lambda\leq\kappa</math>.}}
'''הוכחה''': בכל הסעיפים נגדיר <math>|A|=\kappa,|B|=\lambda,|C|=\mu</math>.
# הפונקציה <math>I:A\to A:I(x)=x</math> חד חד ערכית.
# יהו <math>f:A\to B,g:B\to C</math> חד חד ערכיות. אז <math>g\circ f:A\to C</math> חד חד ערכית.
# קיימות הוכחות רבות למשפט, עליהן ניתן לקרוא [[w:משפט קנטור-שרדר-ברנשטיין|כאן]]. נביא אחת מהן:
:נניח ש-{\displaystyle f}f היא פונקציה חד-חד-ערכית מ-{\displaystyle A}A ל-{\displaystyle B}B, וש-{\displaystyle g}g היא פונקציה חד-חד-ערכית מ-{\displaystyle B}B ל-{\displaystyle A}A. כמו כן נניח, ללא הגבלת הכלליות שהקבוצות {\displaystyle A}A ו-{\displaystyle B}B זרות (אחרת מספיק להוכיח ש<math>|A\setminus B|=|B\setminus A|</math>, ואז מאיחוד קבוצות נקבל שוויון). נראה שקיימת התאמה חד-חד-ערכית ועל בין שתי הקבוצות. נבנה עבור כל איבר {\displaystyle a}a של הקבוצה {\displaystyle A}A, וכל איבר {\displaystyle b}b של הקבוצה {\displaystyle B}B, סדרת איברים מ-{\displaystyle A}A ומ-{\displaystyle B}B לסירוגין, כך שכל איבר מתקבל על ידי החלת הפונקציה החד-חד-ערכית המתאימה על האיבר שקודם לו:
:{\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}h מ-{\displaystyle A}A ל-{\displaystyle B}B: עבור איברי {\displaystyle A}A ששייכים לסדרת קצה-{\displaystyle A}A, נגדיר את {\displaystyle h(a)}{\displaystyle h(a)} כ-{\displaystyle f(a)}{\displaystyle f(a)} (כלומר, נלך צעד אחד ימינה בסדרה המתאימה לאיבר). עבור איברי {\displaystyle A}A ששייכים לסדרת קצה-{\displaystyle B}B, נגדיר את {\displaystyle h(a)}{\displaystyle h(a)} כ-{\displaystyle g^{-1}(a)}{\displaystyle g^{-1}(a)} (כלומר, נלך צעד אחד שמאלה בסדרה המתאימה לאיבר), ובאותו אופן נגדיר גם את {\displaystyle h}h עבור איברי {\displaystyle A}A ששייכים לסדרה ללא קצה. קל לראות שהפונקציה {\displaystyle h}h היא אכן חד-חד-ערכית ועל.
| |||