תורת הקבוצות/קבוצת החזקה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
|||
שורה 1:
{{תורת הקבוצות}}
דיברנו כבר בעבר על המושג של תת-קבוצה. בפרק זה נראה מה ניתן לומר על קבוצת כל
==הגדרה ותכונות בסיסיות==
{{הגדרה|
תוכן=בהינתן קבוצה <math>A</math> , קבוצת החזקה של <math>A</math> מסומנת
:
קל לראות שמתקיים <math>A\in\mathbb{P}(A)</math> וכן <math>\varnothing\in\mathbb{P}(A)</math> . וכן, באופן טריוויאלי אם מתקיים <math>\alpha\
===דוגמאות===
בהינתן <math>A=
:
;הערה
נשים לב, שכמות האברים בקבוצת החזקה של <math>A</math> הוא בדיוק 2 בחזקת כמות האברים
==קבוצת החזקה של קבוצה סופית==
כפי שראינו בדוגמאות, קבוצת החזקה של קבוצה <math>A</math> (שאיננה ריקה) תמיד מכילה לפחות 2 אברים (אבר אחד בלבד אם היא הקבוצה הריקה), הקבוצה עצמה והקבוצה הריקה. ברצוננו לגלות כמה אברים יש בקבוצת החזקה של קבוצה סופית. לדבר יש הוכחות רבות, גם מתוך תורת הקבוצות וגם מתוך קומבינטוריקה. ההוכחות הקומבינטורית והאינדוקטיבית הן אלמנטריות, ההוכחה באמצעות עוצמות דורשת ידע מפרק מתקדם יותר בספר זה, ומומלץ לקורא המתחיל לחכות לפני שהוא קורא אותה.
{{הגדרה|תוכן=בהינתן קבוצה סופית <math>A=
{{טענה|תוכן=בהינתן קבוצה סופית <math>A=
:
;הוכחה אינדוקטיבית
שורה 31:
כעת, יהי <math>k</math> מספר טבעי כלשהו כך שהטענה נכונה עבור <math>n=k</math> . נראה נכונות הטענה עבור <math>n=k+1</math> .
תהי <math>A=
מספר כל הקבוצות שעבורן <math>a_{k+1}</math> לא שייך לקבוצה הוא <math>2^k</math> לפי הנחת האינדוקציה. ואם נוסיף לכל
:
מכאן, מנכונות בסיס וצעד האינדוקציה ועיקרון האינדוקציה, הטענה נכונה לכל <math>n</math> . <math>\blacksquare</math>
שורה 40:
ההוכחה הזו מניחה ידע קומבינטורי שהקורא יכול לוודא בספר מתאים בנושא, או בקורס במתמטיקה דיסקרטית.
טענה 1: מספר האפשרויות לבחור <math>k</math> עצמים שונים בלי חשיבות לסדר, מתוך <math>n</math> עצמים, נתון
:
טענה 2: נוסחת הבינום של ניוטון לכל <math>x\in\R</math> מתקיים כי
:
כעת, נשים לב שבהינתן קבוצה סופית <math>A</math> בעלת <math>n</math> אברים, כמות
:
לכן על-ידי הצבת <math>x=1</math> בנוסחת הבינום של ניוטון, נקבל:
:
<math>\blacksquare</math>
שורה 57:
נסתכל על הקבוצה <math>\{0,1\}^n</math> . קל להראות שזו אכן הקבוצה המבוקשת. נגדיר את הפונקציה:
:
על־ידי
:
קל להוכיח שזו אכן פונקציה חח"ע ועל. באופן אינטואיטיבי, <math>f</math> מקבלת מעין "מתכון" שאומר איזה מהאברים להכניס לתת-קבוצה ואיזה לא לפי הסדר של
אם היא מקבלת 1 במקום
|