תורת הקבוצות/קבוצת החזקה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←קבוצת החזקה של קבוצה סופית: עריכה |
←הוכחה אינדוקטיבית: -הכל. |
||
שורה 26:
===הוכחה אינדוקטיבית===
כאשר n=0, מתקיים ש <math>A=\empty</math>. עבורה, מתקיים ש: <math>\vert 2^A\vert =\vert\{ \empty\}\vert = 1</math>.
וכן, עבור n=1 מתקיים ש <math>\ A=\{ a_1\}</math> לכן, <math>\vert 2^A\vert =\vert\{ \empty , \{ a\}\}\vert = 2</math>.
כעת, יהי k מספר טבעי כלשהו כך שהטענה נכונה עבור n=k. נראה נכונות הטענה עבור n=k+1. תהי
<center>
<math>\ A=\{ a_1,\ldots ,a_{k+1}\}</math>
</center>
קבוצה כלשהי בת k+1 איברים. נחלק את התת-קבוצות של A ל2: או שהאיבר <math>a_{k+1}</math> שייך לקבוצה, או שלא. מספר כל הקבוצות שעבורן <math>a_{k+1}</math> לא שייך לקבוצה הוא, לפי הנחת האינדוקציה, <math>2^k</math>. ואם נוסיף לכל תת-קבוצה כזו את האיבר
<math>a_{k+1}</math> , אז נקבל פשוט את כל הקבוצות שהאיבר הנ"ל כן שייך אליהן. לכן, בסך הכל:
<center>
<math>\vert 2^A\vert = 2^{k}+2^k=2^{k+1}</math>
</center>
מכאן, מנכונות בסיס וצעד האינדוקציה ועיקרון האינדוקציה, הטענה נכונה לכל n. כנדרש.
===הוכחה קומבינטורית===
===הוכחה באמצעות עוצמות===
| |||