תורת הקבוצות/קבוצת החזקה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
שורה 3:
==הגדרה ותכונות בסיסיות==
{{הגדרה|
:<font size=4><math>\mathbb{P}(A)=\big\{\alpha|\alpha\subset A\big\}</math></font size=4>}}
קל לראות שמתקיים <math>A\in\mathbb{P}(A)</math> וכן ===דוגמאות===
בהינתן <math>A=\big\{0,1,2\big\}</math> אזי
:<
הערה: נשים לב, שכמות האברים בקבוצת החזקה של <math>A</math> הוא בדיוק 2 בחזקת כמות האברים ב- <math>A</math> . טענה זו תוכלל בסעיף הבא, ותהיה לה חשיבות רבה בהמשך כשנדבר על עוצמות.▼
;הערה
▲
==קבוצת החזקה של קבוצה סופית==
כפי שראינו בדוגמאות, קבוצת החזקה של קבוצה <math>A</math> (שאיננה ריקה) תמיד מכילה לפחות 2 אברים (אבר אחד בלבד אם היא הקבוצה הריקה), הקבוצה עצמה והקבוצה הריקה. ברצוננו לגלות כמה אברים יש בקבוצת החזקה של קבוצה סופית. לדבר יש הוכחות רבות, גם מתוך תורת הקבוצות וגם מתוך קומבינטוריקה. ההוכחות הקומבינטורית והאינדוקטיבית הן אלמנטריות, ההוכחה באמצעות עוצמות דורשת ידע מפרק מתקדם יותר בספר זה, ומומלץ לקורא המתחיל לחכות לפני שהוא קורא אותה.
{{הגדרה
{{טענה
:<
כאשר <math>n=0</math> מתקיים <math>A=\varnothing</math> . עבורה
וכן
כעת, יהי <math>k</math> מספר טבעי כלשהו כך שהטענה נכונה עבור <math>n=k</math> . נראה נכונות הטענה עבור <math>n=k+1</math> .
קבוצה כלשהי בת <math>k+1</math> אברים. נחלק ל-2 את תת-הקבוצות של <math>A</math> : או שהאבר <math>a_{k+1}</math> שייך לקבוצה, או שלא. מספר כל הקבוצות שעבורן <math>a_{k+1}</math> לא שייך לקבוצה הוא, לפי הנחת האינדוקציה, <math>2^k</math> . ואם נוסיף לכל תת-קבוצה כזו את האבר <math>a_{k+1}</math> , אז נקבל פשוט את כל הקבוצות שהאבר הנ"ל כן שייך אליהן. לכן, בסך הכל:▼
<center><math>|2^A|=2^k+2^k=2^{k+1}</math></center>▼
מכאן, מנכונות בסיס וצעד האינדוקציה ועיקרון האינדוקציה, הטענה נכונה לכל <math>n</math> . כנדרש.▼
תהי <math>A=\big\{a_1,\ldots,a_{k+1}\big\}</math> קבוצה כלשהי בת <math>k+1</math> אברים. נחלק ל-2 את תת-הקבוצות של <math>A</math> : או שהאבר <math>a_{k+1}</math> שייך לקבוצה, או שלא.
===הוכחה קומבינטורית===▼
▲
▲מכאן, מנכונות בסיס וצעד האינדוקציה ועיקרון האינדוקציה, הטענה נכונה לכל <math>n</math> .
ההוכחה הזו מניחה ידע קומבינטורי שהקורא יכול לוודא בספר מתאים בנושא, או בקורס במתמטיקה דיסקרטית.
טענה 1: מספר האפשרויות לבחור <math>k</math> עצמים שונים בלי חשיבות לסדר, מתוך <math>n</math> עצמים, נתון על-ידי
:<
טענה 2: נוסחת הבינום של ניוטון לכל <math>x\in\R</math> מתקיים
:<
כעת, נשים לב שבהינתן קבוצה סופית <math>A</math> בעלת <math>n</math> אברים, כמות תת-הקבוצות של <math>A</math> שיש בהן בדיוק <math>k</math> אברים הוא <math>\binom{n}{k}</math> , לכן
:<
<math>\blacksquare</math>
▲לכן, על-ידי הצבה של <math>x=1</math> בנוסחת הבינום של ניוטון, נקבל:
▲<center><math>2^n=(1+1)^n=\sum_{k=0}^n\binom{n}{k}=|2^A|</math></center>
▲===הוכחה באמצעות עוצמות===
{{שקול לדלג|ההוכחה הנ"ל משתמשת במושג של פונקציות ועוצמות שעדיין לא למדנו. מומלץ לחזור לקרוא את ההוכחה הנ"ל מיד לאחר שסיימת לקרוא את הפרק על עוצמות, שכן היא מדגימה בצורה טובה את השימוש בעוצמות לשם הוכחות קומבינטוריות.}}
בהינתן קבוצה <math>A</math> סופית בעלת <math>n</math> אברים, נרצה למצוא קבוצה
נסתכל על הקבוצה <math>\{0,1\}^n</math> . קל להראות שזו אכן הקבוצה המבוקשת. נגדיר את הפונקציה:
:<
על-ידי
:<
קל להוכיח שזו אכן פונקציה חח"ע ועל. באופן
אם היא מקבלת 1 במקום ה- הוכחת החד-חד הערכיות והעל של <math>f</math> מושארת כתרגיל לקורא.}}
{{תורת הקבוצות|מוגבל}}
|