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

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

המשך קבוצות

תרגיל

הוכיחו כי [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 מוכל בחיתוך בסתירה לכך שהחיתוך ריק.