תרגול 6 תשעז

המשך קבוצות

תרגיל

נתון [math]\displaystyle{ A=\{\phi\} }[/math] ונתון [math]\displaystyle{ B=\{\phi,\{\phi\}\} }[/math]. סמן את הביטויים הנכונים:

1. [math]\displaystyle{ \phi\subseteq B }[/math] (כן)
2. [math]\displaystyle{ \phi\in \phi }[/math] (לא)
3. [math]\displaystyle{ \phi \subseteq \phi }[/math] (כן)
4. [math]\displaystyle{ A\subseteq B }[/math] (כן)
5. [math]\displaystyle{ A\in B }[/math] (כן)
6. [math]\displaystyle{ A\cup B = B }[/math] (כן)
7. [math]\displaystyle{ A\cap B=\phi }[/math] (לא)

תרגיל

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

פתרון

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

[math]\displaystyle{ x\in A\cap (B/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)] }[/math]

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

[math]\displaystyle{ \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)] }[/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{ A=\{2m+1:m\in\mathbb{Z}\} }[/math], ו [math]\displaystyle{ B=\{2m+3:m\in\mathbb{Z}\} }[/math]. הוכח שA=B.

פתרון

נוכיח הכלה דו כיוונית. נניח [math]\displaystyle{ x\in A }[/math] לכן קיים מספר שלם m כך ש [math]\displaystyle{ x=2m+1 }[/math]. קל לראות שמתקיים [math]\displaystyle{ x=2(m-1)+3 }[/math] אבל אז מכיוון ש m-1 הינו מספר שלם מתקיים [math]\displaystyle{ x\in B }[/math] כפי שרצינו.

ההכלה בכיוון ההפוך דומה.

משלים

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

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

• [math]\displaystyle{ A\cup A^c = U }[/math]
• [math]\displaystyle{ \emptyset^c = U }[/math]
• [math]\displaystyle{ U^c = \emptyset }[/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{ (\cap _{i\in I} A_i)^c = \cup _{i\in I} A_{i}^c }[/math]
• [math]\displaystyle{ (\cup _{i\in I} A_i)^c = \cap _{i\in I} A_{i}^c }[/math]

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

דוגמא:

[math]\displaystyle{ A=\{1,2\} }[/math] אזי [math]\displaystyle{ P(A)=\{\{\},\{1\},\{2\},\{1,2\}\} }[/math].

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

תרגיל ממבחן

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

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

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

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

פתרון

א. הפרכה: [math]\displaystyle{ A=\{1,2\},B=\{1\},C=\{2\} }[/math]. אזי ברור שA איננה מוכלת בחיתוך של B וC אבל [math]\displaystyle{ (A/B)\cap(A/C)=\{2\}\cap\{1\}=\phi }[/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\cap A^c =U }[/math] וזה אכן נכון!

ג. נניח בשלילה ש[math]\displaystyle{ P(A)\cap P(B)\neq \{\phi\} }[/math]. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה [math]\displaystyle{ \phi \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 מוכל בחיתוך בסתירה לכך שהחיתוך ריק.