תרגול 6 תשעז

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

המשך קבוצות

תרגיל

הוכיחו כי [math]\displaystyle{ A\cap (B\setminus C)=(A\cap B) \setminus (A\cap C) }[/math].

פתרון

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

[math]\displaystyle{ x\in A\cap (B\setminus C) \iff }[/math] [math]\displaystyle{ (x\in A) \and [(x\in B) \and (x\notin C)] \iff }[/math] [math]\displaystyle{ [(x\in A) \and (x\in B) \and (x\notin C)] \or [(x\in A) \and (x\in B) \and (x\notin A)] }[/math]

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

[math]\displaystyle{ \iff [(x\in A) \and (x\in B)]\and [(x\notin C)\or(x\notin A)]\iff }[/math] [math]\displaystyle{ [(x\in A) \and (x\in B)]\and \neg [(x\in C)\and(x\in A)] }[/math]

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

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

בכיוון ([math]\displaystyle{ \subseteq }[/math]) נניח [math]\displaystyle{ x\in A\cap(B\backslash C) }[/math] אזי

[math]\displaystyle{ x\in A \land x\in B \land x\not\in C \Leftarrow }[/math]

[math]\displaystyle{ x\in A\cap B \land x\not\in A\cap C \Leftarrow }[/math]

[math]\displaystyle{ x\in (A\cap B) \backslash (A\cap C) }[/math]

בכיוון ([math]\displaystyle{ \supseteq }[/math]) נניח [math]\displaystyle{ x\in (A\cap B) \backslash (A\cap C) }[/math] אזי

[math]\displaystyle{ x\in A\cap B \land x\not\in A\cap C \Leftarrow }[/math]

[math]\displaystyle{ x\in A \land x\in B \land x\not\in C \Leftarrow }[/math]

(כי אם [math]\displaystyle{ x\in C }[/math] אזי [math]\displaystyle{ x\in A\cap C }[/math] סתירה)

[math]\displaystyle{ x\in A\cap(B\backslash C)\Leftarrow }[/math]

משלים

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

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

• [math]\displaystyle{ A\cup A^c = U }[/math]
• [math]\displaystyle{ \varnothing^c = U }[/math]
• [math]\displaystyle{ U^c = \varnothing }[/math]
• [math]\displaystyle{ (A^c)^c = A }[/math]

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

• [math]\displaystyle{ (A\cap B)^c = A^c \cup B^c }[/math]
• [math]\displaystyle{ (A\cup B)^c = A^c \cap B^c }[/math]

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

• [math]\displaystyle{ (\bigcap _{i\in I} A_i)^c = \bigcup _{i\in I} A_{i}^c }[/math]
• [math]\displaystyle{ (\bigcup _{i\in I} A_i)^c = \bigcap _{i\in I} A_{i}^c }[/math]

קבוצת החזקה

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

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

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

תרגיל ממבחן

תהינה [math]\displaystyle{ A,B,C }[/math] קבוצות. הוכיחו או הפריכו:

א. אם [math]\displaystyle{ A \not\subseteq B \cap C }[/math] אזי [math]\displaystyle{ (A\setminus B)\cap(A\setminus C)\neq \varnothing }[/math]

ב. אם [math]\displaystyle{ A\subseteq B }[/math] אזי [math]\displaystyle{ A\cup (B\setminus A)=B }[/math]

ג. אם [math]\displaystyle{ A\cap B=\varnothing }[/math] אזי [math]\displaystyle{ P(A)\cap P(B) = \{\varnothing\} }[/math]

פתרון

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

ב. נתון שלכל [math]\displaystyle{ a\in A }[/math] מתקיים [math]\displaystyle{ a \in B }[/math]. אזי

[math]\displaystyle{ 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)] }[/math]

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

דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית [math]\displaystyle{ U:=B }[/math] ואז צריך להוכיח כי [math]\displaystyle{ A\cup A^c =U }[/math] וזה אכן נכון!

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