ה סט כוח של סט א הוא אוסף כל קבוצות המשנה של א. כאשר עובדים עם סופי סט עם n אלמנטים, שאלה אחת שאנחנו עשויים לשאול היא, "כמה אלמנטים יש במערכת הכוח של א? " נראה כי התשובה לשאלה זו היא 2n ולהוכיח באופן מתמטי מדוע זה נכון.
תצפית על התבנית
אנו נחפש דפוס על ידי התבוננות במספר האלמנטים בערכת הכוח של א, איפה א יש ל n אלמנטים:
- אם א = {} (הסט הריק), אם כן א אין בו אלמנטים אלא P (A) = {{}}, קבוצה עם אלמנט אחד.
- אם א = {א}, אם כן א יש אלמנט אחד ו P (A) = {{}, {א}}, קבוצה עם שני אלמנטים.
- אם א = {א, ב}, אם כן א יש שני אלמנטים ו P (A) = {{}, {א}, {ב}, {א, ב}}, קבוצה עם שני אלמנטים.
בכל המצבים הללו, ניתן יהיה לראות זאת באופן ברור סטים עם מספר קטן של אלמנטים שאם יש מספר סופי של n אלמנטים ב אואז מערכת החשמל ע (א) יש 2n אלמנטים. אך האם דפוס זה נמשך? רק בגלל שדפוס נכון n = 0, 1 ו- 2 לא בהכרח אומר שהתבנית נכונה לערכים גבוהים יותר של n.
אבל הדפוס הזה אכן ממשיך. כדי להראות שזה אכן המקרה, נשתמש בהוכחה באמצעות אינדוקציה.
הוכחה על ידי אינדוקציה
הוכחה על ידי אינדוקציה מועילה להוכחת הצהרות הנוגעות לכל המספרים הטבעיים. אנו משיגים זאת בשני שלבים. בשלב הראשון אנו מעגן את הוכחתנו על ידי הצגת אמירה אמיתית לערך הראשון של
n שאנחנו רוצים לקחת בחשבון. השלב השני בהוכחתנו הוא להניח שההצהרה מתייחסת n = kוההצגה שמשמעה מכך אמורה ההצהרה n = k + 1.תצפית נוספת
כדי לעזור בהוכחתנו, נצטרך התבוננות נוספת. מהדוגמאות לעיל, אנו יכולים לראות ש- P ({a}) היא תת-קבוצה של P ({a, b}). קבוצות המשנה של {a} מהוות בדיוק מחצית משנה של קבוצות המשנה של {a, b}. אנו יכולים להשיג את כל קבוצות המשנה של {a, b} על ידי הוספת האלמנט b לכל אחת מתת הקבוצות של {a}. תוספת קבועה זו מושגת באמצעות הפעולה הקבועה של האיחוד:
- סט ריק U {b} = {b}
- {א} U {b} = {א, ב}
אלה שני האלמנטים החדשים ב- P ({a, b}) שלא היו מרכיבים של P ({a}).
אנו רואים התרחשות דומה עבור P ({a, b, c}). נתחיל בארבע הקבוצות של P ({a, b}), ולכל אחת מהן אנו מוסיפים את האלמנט c:
- סט ריק U {c} = {c}
- {א} U {c} = {א, ג}
- {b} U {c} = {b, c}
- {א, ב} U {c} = {א, ב, ג}
וכך בסופו של דבר שמונה יסודות ב- P ({a, b, c}).
ההוכחה
אנו מוכנים כעת להוכיח את ההצהרה, "אם הסט א מכיל n אלמנטים, ואז מערכת הכוח P (A) יש 2n אלמנטים."
נפתח בציין כי ההוכחה על ידי אינדוקציה כבר עוגנה למקרים n = 0, 1, 2 ו -3. אנו מניחים על ידי אינדוקציה שההצהרה מתייחסת לה k. עכשיו תן לסט א להכיל n + 1 אלמנטים. אנחנו יכולים לכתוב א = ב U {x}, ושקול כיצד ליצור קבוצות משנה של א.
אנו לוקחים את כל המרכיבים של P (B)ועל פי ההשערה האינדוקטיבית ישנם 2n של אלה. ואז אנו מוסיפים את האלמנט x לכל אחת מאותן תת קבוצות אלה ב, וכתוצאה מכך עוד 2n קבוצות משנה של ב. זה ממצה את רשימת קבוצות המשנה של בוכך הסכום הוא 2n + 2n = 2(2n) = 2n + 1 אלמנטים של מערך הכוח של א.