שיעור תאוריה

קבוצת חזקה, עוצמה והפרש סימטרי

איך מזהים שהנושא מתאים

אינטואיציה

דמיינו מדף עם כמה חפצים ותיק שאפשר לארוז. עבור כל חפץ מחליטים בנפרד אם להכניס אותו או להשאיר אותו בחוץ. קבוצת החזקה היא אוסף כל התיקים השונים שאפשר לקבל, כולל התיק הריק והתיק שמכיל הכול.

אם כלל מסוים כבר מחייב להכניס חלק מהחפצים ולהשאיר אחרים בחוץ, הם אינם יוצרים בחירה חדשה. רק האיברים שלא הוכרעו נשארים חופשיים. לכל אחד מהם יש שתי אפשרויות בלתי תלויות, ולכן k איברים חופשיים יוצרים 2k תתי-קבוצות שונות, לא רק k.

כשנתון תנאי כמו B∩{1,2,3,4}={1,3}, חלק מהבחירות כבר כפויות: 1,3 חייבים להיות ב-B, ואילו 2,4 חייבים לא להיות ב-B. רק שאר האיברים נשארים חופשיים.

הגדרות פורמליות

P(A) = {B | B ⊆ A}

כל איבר של P(A) הוא בעצמו קבוצה.

P(D)∩P(E)=P(D∩E)

מדוע הזהות נכונה? קבוצה X נמצאת בצד שמאל בדיוק כאשר היא תת-קבוצה גם של D וגם של E. זה שקול לכך שכל איבר של X נמצא בחיתוך D∩E, כלומר X⊆D∩E. לפי הגדרת קבוצת חזקה, זהו בדיוק התנאי X∈P(D∩E).

במקרה הפרטי D∩E=∅, מתקבל P(D)∩P(E)=P(∅)={∅}. חשוב להבדיל בין ∅, שאין בה איברים, לבין {∅}, שהיא קבוצה שאיברה היחיד הוא הקבוצה הריקה.

|P(A)| = 2|A|

כאן |A| הוא מספר האיברים ב-A. הסיבה היא שלכל איבר ב-A יש בדיוק שתי אפשרויות בבניית תת-קבוצה: להיכלל או לא להיכלל.

|A×B| = |A|·|B|

עבור קבוצות סופיות, כל איבר a∈A יכול להופיע כרכיב ראשון עם כל אחד מ-|B| האיברים האפשריים כרכיב שני. מאחר שיש |A| בחירות לרכיב הראשון, מספר הזוגות הסדורים הוא מכפלת מספר הבחירות.

|P(A×B)| = 2|A×B| = 2|A|·|B|

כאן מפעילים שני שלבים שונים: קודם סופרים את הזוגות הסדורים ב-A×B, ואז כל זוג כזה מקבל החלטה עצמאית אם להיכלל בתת-קבוצה של המכפלה.

עבור תנאי חיתוך מהצורה B∩S=T, כאשר T⊆S⊆A, האיברים של T חייבים להיכנס ל-B, האיברים של S\T חייבים לצאת מ-B, והאיברים של A\S הם החופשיים.

|{B⊆A | B∩S=T}| = 2|A\S|

בנוסחה זו B היא תת-הקבוצה שאותה סופרים, S היא קבוצת האיברים שעליהם התנאי מדבר, ו-T היא קבוצת האיברים מתוך S שחייבים להופיע ב-B.

מדוע החזקה היא דווקא מספר האיברים ב-A\S? לאחר שקבענו מה קורה לכל איבר ב-S, כל תת-קבוצה חוקית מתקבלת באופן יחיד מבחירת תת-קבוצה של A\S. לכן יש התאמה מלאה בין התוצאות שאנו סופרים לבין P(A\S), ומספרן הוא 2|A\S|.

A Δ B = (A \ B) ∪ (B \ A)

הפרש סימטרי מכיל את האיברים שנמצאים בדיוק באחת משתי הקבוצות.

|A Δ B| = |A| + |B| - 2|A∩B|

הנוסחה מתקבלת מספירת שני חלקים זרים: ב-A\B יש |A|-|A∩B| איברים, וב-B\A יש |B|-|A∩B| איברים. מחברים את שני הגדלים, ולכן גודל החיתוך מופחת פעמיים.

כאשר קבוצות מוגדרות באמצעות חזקות של ראשוניים, משתמשים ביחידות הפירוק לגורמים ראשוניים: מספר חיובי קובע באופן יחיד את המעריכים של כל ראשוני בפירוק שלו. לכן מספר ששייך לשתי משפחות המבוססות על ראשוניים שונים יכול להופיע בחיתוך רק אם המעריכים של הראשוניים שאינם משותפים מתאפסים.

שיטת פתרון

  1. בקבוצת חזקה זוכרים שאיברים הם תתי-קבוצות, לא האיברים המקוריים עצמם.
  2. בחיתוך של שתי קבוצות חזקה לוקחים תת-קבוצה מועמדת, פותחים את שתי השייכויות לתנאי הכלה, ומאחדים אותן לתנאי X⊆D∩E.
  3. בספירת תתי-קבוצות מחלקים את האיברים לכפויים להיכנס, כפויים לצאת, וחופשיים.
  4. מנמקים את הספירה: כל איבר חופשי נותן החלטה עצמאית אחת של כניסה או יציאה, ולכן מספר הבחירות הוא 2 בחזקת מספר האיברים החופשיים.
  5. כדי להוכיח שבחירות שונות של מעריכים נותנות מספרים שונים, מניחים שוויון בין שתי תוצאות, מפרקים את שני האגפים לגורמים ראשוניים ומשווים את המעריך של כל ראשוני. יחידות הפירוק מחייבת שכל המעריכים המתאימים יהיו שווים, ולכן גם הבחירות המקוריות היו זהות.
  6. כדי למצוא חיתוך בין שתי קבוצות שמוגדרות בחזקות של ראשוניים, לוקחים מספר שרירותי בחיתוך וכותבים את שתי הצורות שלו כשוויון. ראשוני שמופיע רק באגף אחד חייב לקבל מעריך אפס, ולראשוני שמופיע בשני האגפים חייב להיות אותו מעריך. בסיום מתרגמים את המעריכים שנותרו בחזרה לתיאור החיתוך.
  7. להפרש סימטרי מזהים תחילה את שני החלקים הזרים A\B ו-B\A; חישוב גודל החיתוך מאפשר למצוא את גודל כל חלק.

הערות מוכנות למבחן

  • {1} הוא איבר אפשרי של P({1}), אבל 1 אינו איבר של P({1}).
  • כאשר D ו-E מוגדרות בעזרת חזקות של ראשוניים, איבר משותף חייב לקבל מעריך אפס לכל ראשוני שמופיע רק באחת ההגדרות, ומעריכים שווים לכל ראשוני משותף.
  • בביטוי |P(D×E)| קודם מחשבים את |D×E|, ורק אז מעלים את 2 בחזקה הזאת.