תרגול 6 תשעז

חזרה לדף מערכי התרגול.

המשך קבוצות

תרגיל

הוכיחו כי $A\cap (B\setminus C)=(A\cap B) \setminus (A\cap C)$.

פתרון

דרך גרירות לוגיות:

$x\in A\cap (B\setminus C) \iff$ $(x\in A) \and [(x\in B) \and (x\notin C)] \iff$ $[(x\in A) \and (x\in B) \and (x\notin C)] \or [(x\in A) \and (x\in B) \and (x\notin A)]$

בשורה האחרונה הוספנו סתירה בעזרת הקשר "או" ולכן נשארנו עם ביטוי שקול. כעת נשתמש בחוק הפילוג של הלוגיקה:

$\iff [(x\in A) \and (x\in B)]\and [(x\notin C)\or(x\notin A)]\iff$ $[(x\in A) \and (x\in B)]\and \neg [(x\in C)\and(x\in A)]$

וזה בדיוק מה שרצינו.

הוכחה נוספת בעזרת הכלה דו כיוונית:

בכיוון ($\subseteq$) נניח $x\in A\cap(B\backslash C)$ אזי

$x\in A \land x\in B \land x\not\in C \Leftarrow$

$x\in A\cap B \land x\not\in A\cap C \Leftarrow$

$x\in (A\cap B) \backslash (A\cap C)$

בכיוון ($\supseteq$) נניח $x\in (A\cap B) \backslash (A\cap C)$ אזי

$x\in A\cap B \land x\not\in A\cap C \Leftarrow$

$x\in A \land x\in B \land x\not\in C \Leftarrow$

(כי אם $x\in C$ אזי $x\in A\cap C$ סתירה)

$x\in A\cap(B\backslash C)\Leftarrow$

משלים

הגדרה: תהי קבוצה $U$, ונביט בתת קבוצה שלה $A$. ניתן להגדיר את המשלים של $A$ כאוסף האיברים ב-$U$ שאינם ב-$A$ (כלומר ההפרש $U\setminus A$), המסומן $A^c$. לא ניתן לדבר על משלים אוניברסלי ללא $U$ מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).

תכונות בסיסיות:

• $A\cup A^c = U$
• $\varnothing^c = U$
• $U^c = \varnothing$
• $(A^c)^c = A$

על המשלימים מתקיימים חוקי דה מורגן (הנובעים ישירות מחוקי דה מורגן בלוגיקה):

• $(A\cap B)^c = A^c \cup B^c$
• $(A\cup B)^c = A^c \cap B^c$

הערה: באופן כללי מתקיים

• $(\bigcap _{i\in I} A_i)^c = \bigcup _{i\in I} A_{i}^c$
• $(\bigcup _{i\in I} A_i)^c = \bigcap _{i\in I} A_{i}^c$

קבוצת החזקה

הגדרה: תהי קבוצה $A$. נגדיר את קבוצת החזקה של $A$ בתור אוסף כל תת הקבוצות של $A$. נסמן $P(A)=\{X:X\subseteq A\}$.

דוגמה: נבחר $A=\{1,2\}$ אזי $P(A)=\{\{\},\{1\},\{2\},\{1,2\}\}$.

האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה? הוכיחו זאת באינדוקציה.

תרגיל ממבחן

תהינה $A,B,C$ קבוצות. הוכיחו או הפריכו:

א. אם $A \not\subseteq B \cap C$ אזי $(A\setminus B)\cap(A\setminus C)\neq \varnothing$

ב. אם $A\subseteq B$ אזי $A\cup (B\setminus A)=B$

ג. אם $A\cap B=\varnothing$ אזי $P(A)\cap P(B) = \{\varnothing\}$

פתרון

א. הפרכה: $A=\{1,2\},B=\{1\},C=\{2\}$. אזי ברור ש-$A$ איננה מוכלת בחיתוך $B\cap C$ אבל $(A\setminus B)\cap(A\setminus C)=\{2\}\cap\{1\}=\varnothing$

ב. נתון שלכל $a\in A$ מתקיים $a \in B$. אזי

$x\in [A\cup(B/A)] \iff (x\in A) \or [(x\in B)\and (x\notin A)] \iff [(x\in A) \or (x\in B)] \and [(x \in A)\or (x\notin A)]$

כעת, הצד הימני הוא טאוטולוגיה וניתן להסיר אותו. מכיוון שנתון $(x\in A)\rightarrow (x\in B)$ ניתן להסיק בקלות ש$(x\in A)\or (x\in B) \iff (x\in B)$ כפי שרצינו.

דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית $U:=B$ ואז צריך להוכיח כי $A\cup A^c =U$ וזה אכן נכון!

ג. נניח בשלילה ש$P(A)\cap P(B)\neq \{\varnothing\}$. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה $\varnothing \not=C$ השייכת לחיתוך $P(A)\cap P(B)$. קבוצות החזקה הן אוסף תת הקבוצות, ולכן $C\subseteq A \and C\subseteq B$. מכיוון שC אינה ריקה קיים בה איבר $\exists c\in C$ וקל מאד לראות ש$(c\in A)\and (c\in B)$ ולכן c מוכל בחיתוך בסתירה לכך שהחיתוך ריק.