טענה:
בהינתן קבוצה סופית מתקיים כי:
![{\displaystyle {\big |}{\mathcal {P}}(A){\big |}=|2^{A}|=2^{|A|}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d89a3962074841578b9e19f7d9791230ef1fa089)
- הוכחה אינדוקטיבית
כאשר מתקיים . עבורה מתקיים כי .
וכן עבור מתקיים לכן .
כעת, יהי מספר טבעי כלשהו כך שהטענה נכונה עבור . נראה נכונות הטענה עבור .
תהי קבוצה כלשהי בת אברים. נחלק ל־2 את תתי־הקבוצות של : או שהאבר שייך לקבוצה, או שלא.
מספר כל הקבוצות שעבורן לא שייך לקבוצה הוא לפי הנחת האינדוקציה. ואם נוסיף לכל תת־קבוצה כזו את האבר , אז נקבל פשוט את כל הקבוצות שהאבר הנ"ל כן שייך אליהן. לכן, בסך הכל:
![{\displaystyle |2^{A}|=2^{k}+2^{k}=2^{k+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/42a2f71f258e1fc8a2de5cbc65f6101fb71c1879)
מכאן, מנכונות בסיס וצעד האינדוקציה ועיקרון האינדוקציה, הטענה נכונה לכל .
- הוכחה קומבינטורית
ההוכחה הזו מניחה ידע קומבינטורי שהקורא יכול לוודא בספר מתאים בנושא, או בקורס במתמטיקה דיסקרטית.
טענה 1: מספר האפשרויות לבחור עצמים שונים בלי חשיבות לסדר, מתוך עצמים, נתון על־ידי
![{\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d33401621fb832dd2f9783e80a906d562f669008)
טענה 2: נוסחת הבינום של ניוטון לכל מתקיים כי
![{\displaystyle (1+x)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52c40598c9f3ae74e49f972b954fb9af5bdafab1)
כעת, נשים לב שבהינתן קבוצה סופית בעלת אברים, כמות תתי־הקבוצות של שיש בהן בדיוק אברים הוא , לכן
![{\displaystyle |2^{A}|=\sum _{k=0}^{n}{\binom {n}{k}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbcbaa3a5f77bb8d86819aef6818e30247afdb1a)
לכן על-ידי הצבת בנוסחת הבינום של ניוטון, נקבל:
![{\displaystyle 2^{n}=(1+1)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}=|2^{A}|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3a87912972ad2953c3ddb5e685d4a0f17ffda26)
- הוכחה באמצעות עוצמות
![](//upload.wikimedia.org/wikipedia/commons/thumb/9/92/Edit-undo.svg/50px-Edit-undo.svg.png) |
שקלו לדלג על נושא זה
מומלץ לשקול לדלג על נושא זה בפעם הראשונה בה נתקלים בו, ולחזור אליו רק לאחר מעבר כללי על כל הספר.
|
בהינתן קבוצה סופית בעלת אברים, נרצה למצוא קבוצה שעוצמתה היא , ולהראות שהקבוצה הנ"ל שקולה לקבוצת החזקה.
נסתכל על הקבוצה . קל להראות שזו אכן הקבוצה המבוקשת. נגדיר את הפונקציה:
![{\displaystyle f:\{0,1\}^{n}\to 2^{A}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1aa76ac3e137aa3e35599e125002a4d52c058b2)
על־ידי
![{\displaystyle f(x_{1},\ldots ,x_{n})={\big \{}a_{k}\in A:x_{k}\neq 0{\big \}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc96088018c70a9cf44f725400d7098c6ae94b66)
קל להוכיח שזו אכן פונקציה חח"ע ועל. באופן אינטואיטיבי, מקבלת מעין "מתכון" שאומר איזה מהאברים להכניס לתת-קבוצה ואיזה לא לפי הסדר של ה־0 ו־1 שהיא מקבלת.
אם היא מקבלת 1 במקום ה־ , האבר ה־ בקבוצה נכנס לתת־קבוצה ש– מחזירה.
הוכחת החד-חד הערכיות והעל של מושארת כתרגיל לקורא.
|