תורת הקבוצות/קבוצת החזקה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
|||
שורה 1:
{{תורת הקבוצות}}
דיברנו כבר בעבר על המושג של תת-קבוצה. בפרק זה נראה מה ניתן לומר על קבוצת כל
==הגדרה ותכונות בסיסיות==▼
הגדרה: בהינתן קבוצה A, קבוצת החזקה של A, מסומנת על ידי <math>\mathbb{P}\left( A\right)</math> או על ידי <math>2^A</math> (סימון זה יובהר בהמשך ובמהלך הספר נשתמש בסימונים השונים לסירוגין), קבוצת כל הקבוצות החלקיות של הקבוצה A. באופן פורמאלי:▼
<math>\ \mathbb{P}\left( A\right) = \{ \alpha\vert\alpha\subset A\}</math>▼
▲==הגדרה ותכונות בסיסיות==
קל לראות שמתקיים <math>A\in \mathbb{P}\left( A\right)</math> וכן, <math>\empty\in\mathbb{P}\left( A\right)</math>. וכן, באופן טריוויאלי▼
▲הגדרה: בהינתן קבוצה <math>A</math> , קבוצת החזקה של <math>A
▲קל לראות שמתקיים <math>A\in
===דוגמאות===
בהינתן <math>
<center><math>
הערה: נשים לב, שכמות
▲<math>\ 2^A=\{\empty ,\{ 0\} ,\{ 1\} ,\{ 2\} ,\{ 0,1\} ,\{ 0,2\} ,\{ 1,2\} ,\{ 0,1,2\}\} </math>
▲הערה: נשים לב, שכמות האיברים בקבוצת החזקה של A הוא בדיוק 2 בחזקת כמות האיברים בA. טענה זו תוכלל בסעיף הבא, ותהיה לה חשיבות רבה בהמשך כשנדבר על עוצמות.
==קבוצת החזקה של קבוצה סופית==
כפי שראינו בדוגמאות, קבוצת החזקה של קבוצה <math>A</math> (שאיננה ריקה) תמיד מכילה לפחות 2
הגדרה: בהינתן קבוצה סופית <math>A=\{
טענה: בהינתן קבוצה סופית <math>A=\{
<center><math>\big|\mathbb{P}(A)\big|=|2^A|=2^{|A|}</math></center>
===הוכחה אינדוקטיבית===
כאשר <math>n=0
וכן, עבור <math>n=1</math> מתקיים
כעת, יהי <math>k</math> מספר טבעי כלשהו כך שהטענה נכונה עבור <math>n=k</math> . נראה נכונות הטענה עבור <math>n=k+1</math> . תהי
קבוצה כלשהי בת <math>k+1</math>
▲<math>\ A=\{ a_1,\ldots ,a_{k+1}\}</math>
מכאן, מנכונות בסיס וצעד האינדוקציה ועיקרון האינדוקציה, הטענה נכונה לכל <math>n</math> . כנדרש.▼
▲קבוצה כלשהי בת k+1 איברים. נחלק את התת-קבוצות של A ל2: או שהאיבר <math>a_{k+1}</math> שייך לקבוצה, או שלא. מספר כל הקבוצות שעבורן <math>a_{k+1}</math> לא שייך לקבוצה הוא, לפי הנחת האינדוקציה, <math>2^k</math>. ואם נוסיף לכל תת-קבוצה כזו את האיבר
▲<math>\vert 2^A\vert = 2^{k}+2^k=2^{k+1}</math>
▲מכאן, מנכונות בסיס וצעד האינדוקציה ועיקרון האינדוקציה, הטענה נכונה לכל n. כנדרש.
===הוכחה קומבינטורית===
ההוכחה הזו מניחה ידע קומבינטורי שהקורא יכול לוודא בספר מתאים בנושא, או בקורס במתמטיקה דיסקרטית.
טענה 1: מספר האפשרויות לבחור <math>k</math> עצמים שונים בלי חשיבות לסדר, מתוך <math>n</math> עצמים, נתון על
▲<math>\binom{n}{k} = \frac{n!}{k!\left( n-k\right) ! }</math>
כעת, נשים לב שבהינתן קבוצה סופית <math>A</math> בעלת <math>n</math>
▲טענה 2: נוסחאת הבינום של ניוטון לכל <math>x\in\mathbb{R}</math> מתקיים ש:
▲<math>\ \left( 1+x\right)^n=\sum_{k=0}^{n}\binom{n}{k}x^k</math>
▲כעת, נשים לב שבהינתן קבוצה סופית A בעלת n איברים, כמות התת-קבוצות של A שיש בהן בדיוק k איברים הוא <math>\binom{n}{k}</math>, לכן,
<center><math>2^n
▲<math>\ \vert 2^A\vert = \sum_{k=0}^{n}\binom{n}{k}</math>
▲לכן, על ידי הצבה של x=1 בנוסחת הבינום של ניוטון, נקבל:
▲<math>2^n =\left( 1+ 1\right)^n=\sum_{k=0}^{n}\binom{n}{k}=\vert 2^A\vert </math>
כנדרש.
שורה 70 ⟵ 49:
{{שקול לדלג|ההוכחה הנ"ל משתמשת במושג של פונקציות ועוצמות שעדיין לא למדנו. מומלץ לחזור לקרוא את ההוכחה הנ"ל מיד לאחר שסיימת לקרוא את הפרק על עוצמות, שכן היא מדגימה בצורה טובה את השימוש בעוצמות לשם הוכחות קומבינטוריות.}}
בהינתן קבוצה <math>A</math> סופית בעלת <math>n</math>
נסתכל על הקבוצה <math>\{
▲<math>\ f:\{ 0,1\}^n\rightarrow 2^A</math>
קל להוכיח שזו אכן פונקציה חח"ע ועל. באופן אינטואטיבי, <math>f</math> מקבלת מעין "מתכון" שאומר איזה מהאברים להכניס לתת-קבוצה ואיזה לא לפי הסדר של
▲על ידי
▲<math>\ f(x_1,\ldots ,x_n)=\{ a_i\in A\vert x_i\neq 0\}</math>
▲קל להוכיח שזו אכן פונקציה חח"ע ועל. באופן אינטואטיבי, f מקבלת מעין "מתכון" שאומר איזה מהאברים להכניס לתת-קבוצה ואיזה לא לפי הסדר של ה0 ו1 שהיא מקבלת. אם היא מקבלת 1 במקום הi, האיבר הi בקבוצה A נכנס לתת-קבוצה שf מחזירה.
הוכחת החד-חד הערכיות והעל של <math>f</math> מושארת כתרגיל לקורא.
{{תורת הקבוצות|מוגבל}}
[[קטגוריה:תורת הקבוצות|קבוצת החזקה]]
| |||