שיעור פתרון

מבחן תשפ"ג ב', מועד א', שאלה 3 - קונטרפוזיציה, דוגמה נגדית וקבוצות חזקה

שיעורי תאוריה רלוונטיים

נוסח השאלה

תהיינה A,B,C קבוצות. נתונה הטענה:

אם A⊄B∩C, אז (A\B)∩(A\C)≠∅
  1. נסחו את הקונטרפוזיציה של טענה זו.
  2. תנו דוגמה נגדית לטענה זו.

הוכיחו כי לכל שתי קבוצות D,E מתקיים:

D∩E=∅ ⇔ P(D)∩P(E)={∅}

זיהוי השיטה

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

פתרון מודרך

א1. ניסוח הקונטרפוזיציה

נוסח הסעיף: נסחו את הקונטרפוזיציה של הטענה: אם A⊄B∩C, אז (A\B)∩(A\C)≠∅.

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

שלילת (A\B)∩(A\C)≠∅ היא (A\B)∩(A\C)=∅. שלילת A⊄B∩C היא A⊆B∩C. לכן הקונטרפוזיציה היא:

אם (A\B)∩(A\C)=∅, אז A⊆B∩C

א2. דוגמה נגדית

נוסח הסעיף: תנו דוגמה נגדית לטענה: אם A⊄B∩C, אז (A\B)∩(A\C)≠∅.

ההנחה A⊄B∩C אומרת שקיים איבר של A שאינו נמצא לפחות באחת מן הקבוצות B,C. לעומת זאת, כדי להיות ב-(A\B)∩(A\C), אותו איבר צריך להיעדר משתיהן. הפער הזה מציע לבחור איבר שנמצא ב-B אך אינו נמצא ב-C.

נבחר:

A={1},   B={1},   C=∅

ראשית נבדוק את ההנחה. מתקיים B∩C=∅, ולכן A⊄B∩C.

כעת נבדוק את המסקנה:

A\B=∅,   A\C={1} (A\B)∩(A\C)=∅∩{1}=∅

ההנחה מתקיימת אך המסקנה אינה מתקיימת. לכן זו דוגמה נגדית, והטענה המקורית שגויה.

ב. חיתוך של קבוצות חזקה

נוסח הסעיף: הוכיחו כי לכל שתי קבוצות D,E מתקיים:

D∩E=∅ ⇔ P(D)∩P(E)={∅}

זוהי שקילות, ולכן נוכיח כל כיוון בנפרד.

כיוון ראשון. נניח D∩E=∅. צריך להראות שהאיבר היחיד המשותף לשתי קבוצות החזקה הוא הקבוצה הריקה.

יהי X∈P(D)∩P(E) שרירותי. לפי הגדרת חיתוך:

X∈P(D) ∧ X∈P(E)

לפי הגדרת קבוצת חזקה, מתקיים X⊆D וגם X⊆E. לכן כל איבר של X שייך גם ל-D וגם ל-E, ומכאן:

X⊆D∩E=∅

תת-הקבוצה היחידה של הקבוצה הריקה היא הקבוצה הריקה, ולכן X=∅. קיבלנו P(D)∩P(E)⊆{∅}.

בכיוון ההכלה השני, ∅⊆D וגם ∅⊆E. לכן ∅∈P(D)∩P(E), ומתקבלת ההכלה {∅}⊆P(D)∩P(E). שתי ההכלות נותנות:

P(D)∩P(E)={∅}

כיוון שני. נניח P(D)∩P(E)={∅}. נוכיח שאין איבר ב-D∩E.

נניח לצורך סתירה שקיים x∈D∩E. אז x∈D וגם x∈E, ולכן:

{x}⊆D,   {x}⊆E

לפי הגדרת קבוצת החזקה, {x}∈P(D) וגם {x}∈P(E). לכן {x}∈P(D)∩P(E). אבל {x}≠∅, בסתירה להנחה שהחיתוך הוא {∅}. לכן לא קיים איבר ב-D∩E, ומכאן D∩E=∅.

תשובה סופית

הקונטרפוזיציה היא: אם (A\B)∩(A\C)=∅, אז A⊆B∩C.

דוגמה נגדית: A={1}, B={1}, C=∅.

לכל D,E, מתקיים D∩E=∅ אם ורק אם P(D)∩P(E)={∅}.

המשך במבחן

מבחן תשפ"ג ב', מועד א' · שאלה 3

המשך לפי סדר השאלות במבחן.

לשאלה הבאה: שאלה 4 - עוצמות ותכונות יחס