תורת הקבוצות/קבוצת החזקה

דיברנו כבר בעבר על המושג של תת-קבוצה. בפרק זה נראה מה ניתן לומר על קבוצת כל תתי־הקבוצות של קבוצה נתונה.

הגדרה ותכונות בסיסיות

הגדרה: בהינתן קבוצה $A$ , קבוצת החזקה של $A$ מסומנת על־ידי ${\mathcal {P}}(A)$ או על־ידי $2^{A}$ (סימון זה יובהר בהמשך ובמהלך הספר נשתמש בסימונים השונים לסרוגין), קבוצת כל הקבוצות החלקיות של הקבוצה $A$ . ${\mathcal {P}}(A)=\{\alpha :\alpha \subseteq A\}$

קל לראות שמתקיים $A\in {\mathcal {P}}(A)$ וכן $\varnothing \in {\mathcal {P}}(A)$ . וכן, באופן טריוויאלי אם מתקיים $\alpha \subset A$ אזי מתקיים $\alpha \in {\mathcal {P}}(A)$ .

דוגמאות

בהינתן $A=\{0,1,2\}$ אזי

$2^{A}={\Big \{}\varnothing ,\{0\},\{1\},\{2\},\{0,1\},\{0,2\},\{1,2\},\{0,1,2\}{\Big \}}$

הערה

נשים לב, שכמות האברים בקבוצת החזקה של $A$ הוא בדיוק 2 בחזקת כמות האברים ב־$A$ . טענה זו תוכלל בסעיף הבא, ותהיה לה חשיבות רבה בהמשך כשנדבר על עוצמות.

קבוצת החזקה של קבוצה סופית

כפי שראינו בדוגמאות, קבוצת החזקה של קבוצה $A$ (שאיננה ריקה) תמיד מכילה לפחות 2 אברים (אבר אחד בלבד אם היא הקבוצה הריקה), הקבוצה עצמה והקבוצה הריקה. ברצוננו לגלות כמה אברים יש בקבוצת החזקה של קבוצה סופית. לדבר יש הוכחות רבות, גם מתוך תורת הקבוצות וגם מתוך קומבינטוריקה. ההוכחות הקומבינטורית והאינדוקטיבית הן אלמנטריות, ההוכחה באמצעות עוצמות דורשת ידע מפרק מתקדם יותר בספר זה, ומומלץ לקורא המתחיל לחכות לפני שהוא קורא אותה.

הגדרה: בהינתן קבוצה סופית $A=\{a_{1},\ldots ,a_{n}\}$ בעלת $n$ אברים, נסמן $|A|$ את מספר האברים של הקבוצה.

טענה: בהינתן קבוצה סופית $A=\{a_{1},\ldots ,a_{n}\}$ מתקיים כי: ${\big |}{\mathcal {P}}(A){\big |}=|2^{A}|=2^{|A|}$ הוכחה אינדוקטיבית כאשר $n=0$ מתקיים $A=\varnothing$ . עבורה מתקיים כי $|2^{A}|=|\{\varnothing \}|=1$ . וכן עבור $n=1$ מתקיים $A=\{a_{1}\}$ לכן $|2^{A}|={\Big |}{\big \{}\varnothing ,\{a_{1}\}{\big \}}{\Big |}=2$ . כעת, יהי $k$ מספר טבעי כלשהו כך שהטענה נכונה עבור $n=k$ . נראה נכונות הטענה עבור $n=k+1$ . תהי $A=\{a_{1},\ldots ,a_{k+1}\}$ קבוצה כלשהי בת $k+1$ אברים. נחלק ל־2 את תתי־הקבוצות של $A$ : או שהאבר $a_{k+1}$ שייך לקבוצה, או שלא. מספר כל הקבוצות שעבורן $a_{k+1}$ לא שייך לקבוצה הוא $2^{k}$ לפי הנחת האינדוקציה. ואם נוסיף לכל תת־קבוצה כזו את האבר $a_{k+1}$ , אז נקבל פשוט את כל הקבוצות שהאבר הנ"ל כן שייך אליהן. לכן, בסך הכל: $|2^{A}|=2^{k}+2^{k}=2^{k+1}$ מכאן, מנכונות בסיס וצעד האינדוקציה ועיקרון האינדוקציה, הטענה נכונה לכל $n$ . $\blacksquare$ הוכחה קומבינטורית ההוכחה הזו מניחה ידע קומבינטורי שהקורא יכול לוודא בספר מתאים בנושא, או בקורס במתמטיקה דיסקרטית. טענה 1: מספר האפשרויות לבחור $k$ עצמים שונים בלי חשיבות לסדר, מתוך $n$ עצמים, נתון על־ידי ${\binom {n}{k}}={\frac {n!}{k!(n-k)!}}$ טענה 2: נוסחת הבינום של ניוטון לכל $x\in \mathbb {R}$ מתקיים כי $(1+x)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}$ כעת, נשים לב שבהינתן קבוצה סופית $A$ בעלת $n$ אברים, כמות תתי־הקבוצות של $A$ שיש בהן בדיוק $k$ אברים הוא ${\binom {n}{k}}$ , לכן $|2^{A}|=\sum _{k=0}^{n}{\binom {n}{k}}$ לכן על-ידי הצבת $x=1$ בנוסחת הבינום של ניוטון, נקבל: $2^{n}=(1+1)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}=|2^{A}|$ $\blacksquare$ הוכחה באמצעות עוצמות שקלו לדלג על נושא זה מומלץ לשקול לדלג על נושא זה בפעם הראשונה בה נתקלים בו, ולחזור אליו רק לאחר מעבר כללי על כל הספר. בהינתן קבוצה $A$ סופית בעלת $n$ אברים, נרצה למצוא קבוצה שעוצמתה היא $2^{n}$ , ולהראות שהקבוצה הנ"ל שקולה לקבוצת החזקה. נסתכל על הקבוצה $\{0,1\}^{n}$ . קל להראות שזו אכן הקבוצה המבוקשת. נגדיר את הפונקציה: $f:\{0,1\}^{n}\to 2^{A}$ על־ידי $f(x_{1},\ldots ,x_{n})={\big \{}a_{k}\in A:x_{k}\neq 0{\big \}}$ קל להוכיח שזו אכן פונקציה חח"ע ועל. באופן אינטואיטיבי, $f$ מקבלת מעין "מתכון" שאומר איזה מהאברים להכניס לתת-קבוצה ואיזה לא לפי הסדר של ה־0 ו־1 שהיא מקבלת. אם היא מקבלת 1 במקום ה־$k$ , האבר ה־$k$ בקבוצה $A$ נכנס לתת־קבוצה ש–$f$ מחזירה. הוכחת החד-חד הערכיות והעל של $f$ מושארת כתרגיל לקורא.

הפרק הקודם: מכפלה קרטזית

קבוצת החזקה

הפרק הבא: יחסים