לדלג לתוכן
שינוי מצב סרגל צד
Math-Wiki
חיפוש
יצירת חשבון
כלים אישיים
יצירת חשבון
כניסה לחשבון
דפים לעורכים שלא נכנסו לחשבון
מידע נוסף
שיחה
תרומות
ניווט
עמוד ראשי
שינויים אחרונים
העלאת קובץ
כלים
דפים המקושרים לכאן
שינויים בדפים המקושרים
דפים מיוחדים
מידע על הדף
עריכת הדף "
מתמטיקה בדידה - ארז שיינר
" (פסקה)
דף
שיחה
עברית
קריאה
עריכה
גרסאות קודמות
עוד
קריאה
עריכה
גרסאות קודמות
אזהרה:
אינכם מחוברים לחשבון. כתובת ה־IP שלכם תוצג בפומבי אם תבצעו עריכות כלשהן. אם
תיכנסו לחשבון
או
תיצרו חשבון
, העריכות שלכם תיוחסנה לשם המשתמש שלכם ותקבלו גם יתרונות אחרים.
בדיקת אנטי־ספאם.
אין
למלא שדה זה!
==פרק 5 - עוצמות== ===מבוא=== <videoflash>TG97scv77QI</videoflash> <videoflash>Wh9MuSOLF2Q</videoflash> ===השוואת עוצמות=== *A שקולת עוצמה לB או עוצמתה של A שווה לB, אם קיימת פונקציה הפיכה (חח"ע ועל) <math>f:A\to B</math>. *במקרה זה מסמנים <math>A\sim B</math> או <math>|A|=|B|</math>. **כל קבוצה שקולת עוצמה לעצמה **אם A שקולת עוצמה לB, גם B שקולת עוצמה לA **אם A שקולת עוצמה לB וB שקולת עוצמה לC אזי A שקולת עוצמה לC *עוצמתה של A קטנה או שווה לזו של B, אם קיימת פונקציה חח"ע <math>f:A\to B</math>. *במקרה זה מסמנים <math>|A|\leq |B|</math> *כל קבוצה A השקולת עוצמה לקבוצת הטבעיים מסומנת <math>|A|=\aleph_0</math> *כל קבוצה A השקולת עוצמה לקבוצת הממשיים מסומנת <math>|A|=\aleph</math> <videoflash>Zu0tX3VcZbg</videoflash> ===משפט קנטור=== *<math>|A|<|P(A)|</math> <videoflash>H4IwZiUCUvM</videoflash> ===קבוצות בנות מנייה=== *קבוצה A נקראת בת מנייה אם <math>|A|\leq \aleph_0</math> *כל קבוצה A בת מנייה אינסופית מקיימת <math>|A|=\aleph_0</math> <videoflash>7TyjNpInOsc</videoflash> ===חשבון עוצמות (אריתמטיקה של עוצמות)=== ====חיבור עוצמות==== *תהיינה שתי עוצמות a,b ותהיינה שתי נציגות זרות לעוצמות A,B. *נגדיר <math>a+b=|A\cup B|</math>, הגדרה זו אינה תלוייה בבחירת הנציגות. <videoflash>eDpiO50cDmI</videoflash> ====כפל עוצמות==== *תהיינה שתי עוצמות a,b ותהיינה שתי נציגות לעוצמות A,B. *נגדיר <math>a\cdot b=|A\times B|</math>, הגדרה זו אינה תלוייה בבחירת הנציגות. <videoflash>AQNIw1ys8B4</videoflash> ====חזקת עוצמות==== *תהיינה שתי עוצמות a,b ותהיינה שתי נציגות לעוצמות A,B. *נגדיר את <math>A^B</math> להיות אוסף כל הפונקציות מB לA (מהמעריך לבסיס). *נגדיר <math>a^b=|A^B|</math>, הגדרה זו אינה תלוייה בבחירת הנציגות. <videoflash>aBV5Vt1eMG4</videoflash> *חוקי חזקות *תהיינה עוצמות a,b,c אזי **<math>a^b\cdot a^c = a^{b+c}</math> **<math>(a^b)^c = a^{b\cdot c}</math> **<math>a^b\cdot c^b = (a\cdot c)^b</math> <videoflash>KUTIHDhwjsE</videoflash> ====עוצמת קבוצת החזקה==== *<math>|P(A)|=2^{|A|}</math> <videoflash>pPG6BgSY_Wg</videoflash> ====השוואת חשבון עוצמות==== *תהיינה עוצמות a,b,c,d כך ש <math>a\leq c</math> וכן <math>b\leq d</math> אזי: **<math>a+b\leq c+d</math> **<math>a\cdot b\leq c\cdot d</math> *אם בנוסף נתון כי <math>c\neq 0</math> אזי **<math>a^b\leq c^d</math> <videoflash>i07f9wwcjtU</videoflash> ===משפט קנטור-שרדר-ברנשטיין=== *אם <math>|A|\leq |B|</math> וגם <math>|B|\leq |A|</math> אזי <math>A\sim B</math> ====למת נקודת השבת==== *תהי פונקציה עולה <math>h:P(A)\to P(A)</math> כלומר המקיימת לכל <math>X_1\subseteq X_2</math> כי <math>h(X_1)\subseteq h(X_2)</math> *אזי קיימת נק' שבת <math>K\subseteq A</math> כך ש <math>h(K)=K</math>. <videoflash>csJJBPs9NaI</videoflash> ====הוכחת המשפט==== <videoflash>KlZHXHxkzJk</videoflash> ====עוצמות קטעים ממשיים==== *<math>|\mathbb{R}|=|[a,\infty)|=|[a,b]|=|(a,b)|=\aleph</math> <videoflash>qDGHoXKOpzk</videoflash> ===אקסיומת הבחירה ועקרון המקסימום של האוסדורף=== ====אקסיומת הבחירה==== *תהי S קבוצת קבוצות לא ריקות, ונסמן את האיחוד הכללי ב <math>U=\cup_{X\in S}X</math>. *אזי קיימת פונקצית בחירה <math>f:S\to U</math> הבוחרת איבר מתוך כל קבוצה, כלומר: **<math>\forall X\in S: f(X)\in X</math> *דוגמא: **תהי פונקציה על <math>f:A\to B</math> אזי קיימת תת קבוצה <math>X\subseteq A</math> כך ש <math>f:X\to B</math> חח"ע ועל. <videoflash>q2OP1NCWKHU</videoflash> *תהיינה <math>A,B\neq\emptyset</math> אזי <math>|A|\leq |B|</math> אם ורק אם קיימת <math>g:B\to A</math> על. *בכיוון ראשון: **תהי <math>f:A\to B</math> חח"ע **כיוון ש<math>A\neq \emptyset</math> קיים <math>a\in A</math> **נגדיר פונקציה <math>g:B\to A</math> באופן הבא: ***לכל <math>b\in B</math> ***אם קיים <math>x\in A</math> כך ש <math>f(x)=b</math> נגדיר <math>f(b)=x</math> (בגלל החח"ע זה מוגדר היטב) ***אם <math>b\not\in Im(f)</math> נגדיר <math>f(b)=a</math> **הפונקציה <math>g</math> שהגדרנו היא אכן על, כי לכל <math>x\in A</math> מתקיים כי <math>g(f(x))=x</math> *בכיוון שני: **תהי <math>g:B\to A</math> על, אזי כל הקבוצות באוסף <math>U=\left\{g^{-1}[\{a\}]|a\in A\right\}</math> אינן ריקות. **ניקח פונקצית בחירה <math>h:U\to B</math> ונגדיר <math>f:A\to B</math> ע"י <math>f(a)=h(g^{-1}[\{a\}])</math> **אכן <math>f</math> חח"ע כי אם <math>f(a_1)=f(a_2)=b</math> אזי <math>b\in g^{-1}[\{a_1\}]</math> וכן <math>b\in g^{-1}[\{a_2\}]</math> **ולכן <math>g(b)=a_1</math> וכן <math>g(b)=a_2</math>, כלומר <math>a_1=a_2</math> <videoflash>Dl6sgVGZksk</videoflash> ====עקרון המקסימום של האוסדורף==== *תהי קבוצה A עם יחס סדר חלקי, תת קבוצה <math>S\subseteq A</math> נקראת שרשרת אם היחס מלא עליה (ניתן להשוות בין כל שני איברים בS). *שרשרת נקראת מקסימלית בA אם היא אינה מוכלת באף שרשרת אחרת. *עקרון המקסימום של האוסדורף אומר שכל שרשרת מוכלת בשרשרת מקסימלית. *דוגמא - אוסף עיגולים במישור שאינם חותכים זה את זה, ולא ניתן להוסיף אפילו עיגול אחד נוסף. <videoflash>O_uDtoDRRZ8</videoflash> *טענות שימושיות להמשך: *תהי <math>U</math> קבוצה של יחסים מ<math>A</math> ל <math>B</math>, תהי <math>M\subseteq U</math> שרשרת ביחס ההכלה ונסמן את האיחוד הכללי של השרשרת ב<math>f=\cup_{R\in M} R</math> *אזי: **אם כל היחסים ב<math>M</math> ח"ע, אז גם <math>f</math> ח"ע ***אכן, יהיו <math>(a,b_1),(a,b_2)\in f</math> ***לכן קיימים <math>R_1,R_2\in M</math> כך ש <math>(a,b_1)\in R_1</math> וכן <math>(a,b_2)\in R_2</math> ***כיוון ש<math>M</math> שרשרת, אזי <math>R_1\subseteq R_2</math> (או ההפך) ולכן <math>(a,b_1),(a,b_2)\in R_2</math> ***כיוון ש<math>R_2</math> ח"ע נובע כי <math>b_1=b_2</math> כפי שרצינו. **אם כל היחסים ב<math>M</math> חח"ע, אזי גם <math>f</math> חח"ע ***הוכחה דומה לח"ע ===איחוד בן מנייה של קבוצות בנות מנייה=== (בהנחת אקסיומת הבחירה) *תהי S קבוצה בת מנייה של קבוצות בנות מנייה, כלומר: **<math>|S|\leq\aleph_0</math> **<math>\forall X\in S:|X|\leq\aleph_0</math> *אזי גם האיחוד הכללי הוא בן מנייה: **<math>|\cup_{X\in S}X|\leq \aleph_0</math> *מסקנה: אוסף תתי הקבוצות הסופיות של המספרים הטבעיים הוא בן מנייה. *הערה לסרטון: אנחנו משתמשים באקסיומת הבחירה כאשר "בוחרים" את הפונקציות החח"ע מהקבוצות באוסף אל הטבעיים. <videoflash>0S6r0s2SnNc</videoflash> ===השוואת עוצמות=== (בהנחת עיקרון המקסימום של האוסדורף) *תהיינה שתי קבוצות A,B אזי <math>|A|\leq|B|</math> או <math>|A|\geq |B|</math> *נביט ב<math>U</math> אוסף היחסים הח"ע והחח"ע מ<math>A</math> ל<math>B</math>, וניקח שרשרת מקסימלית ביחס ההכלה <math>M\subseteq U</math> *נסמן ב<math>f</math> את האיחוד הכללי על השרשרת <math>M</math> *ראינו שנובע במקרה זה כי <math>f</math> יחס ח"ע וחח"ע מ<math>A</math> ל<math>B</math>. **אם <math>f</math> שלם, אזי <math>f:A\to B</math> פונקציה חח"ע ולכן <math>|A|\leq |B|</math> **אם <math>f</math> על, אזי <math>f:X\to B</math> פונקציה על עבור <math>X\subseteq A</math> ולכן <math>|B|\leq |X|\leq |A|</math> **אחרת, קיים זוג <math>(a,b)\in A\times B</math> כך ש <math>f\cup\{(a,b)\}</math> יחס ח"ע וחח"ע שניתן להוסיף לשרשרת <math>M</math> בסתירה למקסימליות שלה. <videoflash>XZkMt26fQyE</videoflash> ====אלף אפס היא העוצמה האינסופית הקטנה ביותר==== (בהנחת עקרון המקסימום של האוסדורף) *תהי A קבוצה אינסופית, אזי <math>\aleph_0\leq |A|</math> *דרך נוספת לזו המופיעה בסרטון: **נוכיח בהמשך כי ניתן להשוות עוצמה בין כל שתי קבוצות **אם <math>|A|\leq |\mathbb{N}|</math>, כיוון ש<math>A</math> אינסופית נובע כי <math>|A|=\aleph_0</math> **אחרת, <math>|\mathbb{N}|\leq |A|</math> ולכן <math>\aleph_0\leq |A|</math> כפי שרצינו. <videoflash>W4see8tTArk</videoflash> *תהי A קבוצה אינסופית, ותהי B קבוצה סופית, אזי: **<math>|A|=|A\cup B|=|A\setminus B|</math> *דרך נוספת לזו המופיעה בסרטון: **בהמשך נוכיח כי לכל קבוצה אינסופית <math>X</math> מתקיים כי <math>|X|+|X|=|X|</math> **לכן <math>|A|\leq |A\cup B|=|A|+|B\setminus A|\leq |A|+|A|=|A|</math> ולפי ק.ש.ב <math>|A|=|A\cup B|</math>. ***שימו לב כי <math>B\setminus A</math> סופית ולכן קטנה יותר מהקבוצה האינסופית <math>A</math>. **כמו כן <math>|A|=|A\setminus B|+|B\cap A|</math> **כעת <math>|A\setminus B|\leq|A\setminus B|+|B\cap A|\leq |A\setminus B|+|A\setminus B|=|A\setminus B|</math>. ***שימו לב כי <math>B\cap A</math> סופית ולכן קטנה יותר מהקבוצה האינסופית <math>A\setminus B</math>. **לכן לפי ק.ש.ב <math>|A|=|A\setminus B|+|B\cap A|=|A\setminus B|</math> <videoflash>eaonM-yfR3w</videoflash> ===סכום ומכפלה של עוצמות אינסופיות שווה לגדולה מבין העוצמות=== *תהיינה עוצמות <math>a\leq b</math> אזי: **<math>b\leq a+b</math> *נניח בנוסף כי <math>2\leq a\leq b</math> אזי: **<math>a+b\leq a\cdot b</math> *נניח בנוסף כי b אינסופית, ונקבל ביחד **<math>b\leq a+b \leq a\cdot b\leq b\cdot b =b</math> (המעבר <math>b\cdot b=b</math> מוכח בסרטון השני). *ולכן לפי משפט ק.ש.ב נקבל כי **<math>a+b=a\cdot b = b</math> *דוגמא - מה היא עוצמת קבוצת המספרים האי-רציונאליים? *<math>\mathbb{R}=\mathbb{Q}\cup (\mathbb{R}\setminus\mathbb{Q})</math> (איחוד זר כמובן) *לכן <math>|\mathbb{R}|=|\mathbb{Q}|+ |(\mathbb{R}\setminus\mathbb{Q})|</math> *לכן <math>\aleph=\aleph_0 +|(\mathbb{R}\setminus\mathbb{Q})|</math> *לפי המשפט לעיל, סכום העוצמות הוא העוצמה הגדולה מבין השתיים. *כיוון ש <math>\aleph\neq \aleph_0</math> נקבל כי <math>|(\mathbb{R}\setminus\mathbb{Q})|=\aleph</math> <videoflash>Ty-lY6-uRPo</videoflash> ====עוצמה כפול עצמה==== *תהי קבוצה אינסופית <math>B</math> אזי <math>B\times B\sim B</math> *הוכחה: *תהי <math>S</math> קבוצת כל היחסים <math>R\subseteq (B\times B)\times B</math>, כך שקיימת תת קבוצה <math>X\subseteq B</math> כך ש <math>R:X\times X\to X</math> פונקציה הפיכה. *כיוון ש<math>B</math> אינסופית, יש לה תת קבוצה <math>Y\subseteq B</math> כך ש <math>|Y|=\aleph_0</math>. *כיוון ש <math>\aleph_0\times\aleph_0=\aleph_0</math> קיימת פונקציה הפיכה <math>R:Y\times Y\to Y</math>. *נביט ביחס ההכלה על <math>S</math>. לפי עקרון המקסימום של האוסדורף, קיימת שרשרת מקסימלית <math>\{R\}\subseteq M\subseteq S</math>. *נסמן ב<math>f</math> את האיחוד הכללי של השרשרת <math>f=\cup_{T\in M} T</math>. *נוכיח כי קיימת <math>D\subseteq B</math> כך ש <math>f:D\times D\to D</math> פונקציה הפיכה, ואף <math>|D|=|B|</math> וכך נסיים את ההוכחה. *הוכחה כי <math>f\in S</math> פונקציה הפיכה <math>f:D\times D\to D</math> עבור תת קבוצה <math>D\subseteq B</math>: *ראשית, נגדיר את <math>D=\{d\in B | \exists a,b\in B:((a,b),d)\in f\}</math> *נוכיח כי <math>f\subseteq (D\times D)\times D</math>: **יהי זוג <math>((a,b),d)\in f</math>, לפי ההגדרה <math>d\in D</math> **כמו כן, לפי הגדרת האיחוד קיים <math>T\in M</math> כך ש <math>((a,b),d)\in T</math>. **קיימת <math>X\subseteq B</math> כך ש <math>T:X\times X\to X</math> פונקציה הפיכה. **כיוון ש <math>T</math> על, לכל <math>x\in X</math> קיימים <math>p,q\in X</math> כך ש <math>((p,q),x)\in T</math> ולכן <math>((p,q),x)\in f</math> ולכן <math>x\in D</math> **ביחד עם העובדה ש <math>a,b\in X</math> נובע כי <math>a,b\in D</math> *כיוון שכל איברי השרשרת הם יחסים ח"ע, גם <math>f</math> ח"ע. *כיוון שכל איברי השרשרת הם יחסים חח"ע, גם <math>f</math> חח"ע. *כעת נוכיח כי <math>f:D\times D\to D</math> יחס שלם: **יהיו <math>d_1,d_2\in D</math>. **ראינו כי קיימים <math>T_1,T_2\in M</math> ואיברים <math>a_1,b_1,a_2,b_2\in D</math> כך ש <math>((a_1,b_1),d_1)\in T_1</math> וכן <math>((a_2,b_2),d_2)\in T_2</math> **כיוון ש<math>M</math> שרשרת, <math>T_1\subseteq T_2</math> (או ההפך) ולכן <math>a_1,a_2,b_1,b_2\in X</math> עבור תת קבוצה <math>X\subseteq D</math> כך ש <math>T_2:X\times X\to X</math> פונקציה הפיכה. **לכן קיים <math>d_3\in X\subseteq D</math> כך ש <math>((d_1,d_2),d_3)\in T_2</math> ולכן <math>((d_1,d_2),d_3)\in f</math> כלומר <math>f</math> שלם. *הוכחנו כי <math>f:D\times D\to D</math> היא פונקציה (יחס ח"ע ושלם) חח"ע, נותר להוכיח כי היא על: **יהי <math>d\in D</math>. ראינו כי קיים <math>T\in M</math> וקיימים <math>a,b\in D</math> כך ש <math>((a,b),d)\in T</math> ולכן <math>((a,b),d)\in f</math> ולכן הפונקציה על. *הוכחה כי <math>|D|=|B|</math>: *ראשית, נשים לב כי <math>Y\subseteq D</math> כיוון ש <math>R:Y\times Y\to Y</math> פונקציה הפיכה וכן <math>R\in M</math>, ולכן <math>D</math> אינסופית. *כעת, נזכור שהוכחנו כי <math>|D\times D|=|D|</math>. *נביט ב <math>B\setminus D</math> ונחלק למקרים: *אם <math>|B\setminus D|\leq D</math> אזי: **<math>|B|=|D|+|B\setminus D|\leq |D|+|D|\leq |D|\times |D| =|D|</math> **כמובן ש <math>|D|\leq |B|</math> ולפי ק.ש.ב נסיק כי במקרה זה <math>|B|=|D|</math> וסיימנו. *אם <math>|B\setminus D|\geq |D|</math> נראה כי נגיע לסתירה, ולכן מקרה זה בלתי אפשרי: **ניקח תת קבוצה <math>U\subseteq B\setminus D</math> כך ש <math>|U|=|D|</math>. **לכן <math>|(U\times D) \cup (D\times U) \cup (U\times U)|=|D|+|D|+|D|=|D|</math> (הרי ראינו מקודם כי <math>|D|+|D|=|D|</math>) **לכן קיימת פונקציה הפיכה <math>g:(U\times D) \cup (D\times U) \cup (U\times U)\to U</math>. **האיחוד <math>h=f\cup g</math> הוא פונקציה הפיכה <math>h:(U\cup D)\times (U\cup D)\to (U\cup D)</math>, ולכן <math>h\in S</math>. **ניתן להוסיף את <math>h</math> לשרשרת <math>M</math> ולהגדיל אותה, בסתירה למקסימליות שלה. <videoflash>e6cBpbJzs2A</videoflash> ===הקשר בין עוצמת הטבעיים לעוצמת הממשיים=== *<math>2^{\aleph_0}=\aleph</math> כלומר <math> P(\mathbb{N})\sim\mathbb{R}</math> <videoflash>dhrT0edcmJE</videoflash> ===תרגול=== *[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 6|תרגול בנושא עוצמות]] *[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 7|חשבון (אריתמטיקה) של עוצמות]]
תקציר:
לתשומת לבך: תורמים אחרים עשויים לערוך או אף להסיר את תרומתך ל־Math-Wiki. אם אינך רוצה שעבודתך תהיה זמינה לעריכה על־ידי אחרים, אין לפרסם אותה פה.
כמו־כן, שמירת העריכה משמעה הבטחה שכתבת את הטקסט הזה בעצמך, או העתקת אותו ממקור שאינו מוגן בזכויות יוצרים (אפשר לעיין בדף
Math-Wiki:זכויות יוצרים
לפרטים נוספים).
אין לעשות שימוש בחומר המוגן בזכויות יוצרים ללא רשות!
ביטול
עזרה בעריכה
(נפתח בחלון חדש)