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

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

המשך קבוצות

משלים

הגדרה: תהי קבוצה [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 \triangle B = A^c \triangle B^c }[/math].

פתרון

נשתמש בהצגת ההפרש הסימטרי כאיחוד ההפרשים:

[math]\displaystyle{ x\in A \triangle B \iff (x\in A \land x\notin B)\lor (x\in B \land x\notin A) \iff }[/math]

[math]\displaystyle{ (x\notin A^c \land x\in B^c)\lor (x\notin B^c \land x\in A^c) }[/math] ומחילופיות "וגם" ו"או":

[math]\displaystyle{ (x\notin B^c \land x\in A^c)\lor (x\notin A^c \land x\in B^c) \iff }[/math] [math]\displaystyle{ (x\in A^c \land x\notin B^c)\lor (x\in B^c \land x\notin A^c) \iff x\in A^c \triangle B^c }[/math]

תרגיל

לכל [math]\displaystyle{ n\in \mathbb{N} }[/math] נגדיר [math]\displaystyle{ A_n=\{k\in \mathbb{N}|2\leq k\leq 2n-1\} }[/math] ונגדיר [math]\displaystyle{ B_n=A_{n+1}\smallsetminus A_n }[/math].

א. מצאו את [math]\displaystyle{ \bigcup_{n\in \mathbb{N}} B_n }[/math].

ב. נגדיר [math]\displaystyle{ D_n=\mathbb{N}\smallsetminus B_n }[/math]. מצאו את [math]\displaystyle{ \bigcap_{n\in \mathbb{N}} D_n }[/math].

פתרון

א. התשובה: [math]\displaystyle{ \mathbb{N}\smallsetminus \{1\} }[/math]. הוכחה:

[math]\displaystyle{ \bigcup_{n\in \mathbb{N}} B_n \subseteq \mathbb{N}\smallsetminus \{1\} }[/math]: הכל תת קבוצות של הטבעיים וכל הקבוצות מוגדרות ע"י איברים הגדולים מ-[math]\displaystyle{ 2 }[/math].

[math]\displaystyle{ \mathbb{N}\smallsetminus \{1\} \subseteq \bigcup_{n\in \mathbb{N}} B_n }[/math]: יהי [math]\displaystyle{ a\in \mathbb{N}\smallsetminus \{1\} }[/math] נמצא קבוצה בה הוא נמצא. נשים לב ש-[math]\displaystyle{ B_n=\{2\leq k\leq 2n+1\}\smallsetminus \{2\leq k\leq 2n-1\}=\{2n,2n+1\} }[/math]. לכן אם [math]\displaystyle{ a }[/math] זוגי הוא נמצא ב- [math]\displaystyle{ B_{\frac{n}{2}} }[/math] ואם אי-זוגי אז [math]\displaystyle{ a\in B_{\frac{n-1}{2}} }[/math].

ב. נתייחס ל-[math]\displaystyle{ \mathbb{N} }[/math] כקבוצה האוניברסלית לדיוננו. לפי דה-מורגן נקבל:[math]\displaystyle{ \bigcap_{n\in \mathbb{N}} D_n=\bigcap_{n\in \mathbb{N}} B_n^c=(\bigcup_{n\in \mathbb{N}} B_n)^c=\{1\} }[/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{ P(A)\cap P(B)=P(A\cap B) }[/math]

ב. [math]\displaystyle{ P(A)\cup P(B)=P(A\cup B) }[/math]

פתרון

א. הוכחה: [math]\displaystyle{ X\in P(A)\cap P(B) \iff X\subseteq A\land X\subseteq B\iff }[/math]

[math]\displaystyle{ X\subseteq A\cap B\iff X\in P(A\cap B) }[/math]

ב. הפרכה: ניקח [math]\displaystyle{ A=\{1\},B=\{2\} }[/math]. אז [math]\displaystyle{ \{1,2\} \in P(A\cup B) }[/math], אבל לא ל-[math]\displaystyle{ P(A)\cup P(B) }[/math].

למעשה הוכיחו כי [math]\displaystyle{ P(A)\cup P(B)=P(A\cup B) }[/math] אם ורק אם [math]\displaystyle{ A\subseteq B }[/math] או [math]\displaystyle{ B\subseteq A }[/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\setminus A)] \iff (x\in A) \or [(x\in B)\and (x\notin A)] \iff }[/math]

[math]\displaystyle{ [(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], כפי שרצינו.

דרך נוספת: נגדיר את [math]\displaystyle{ B }[/math] להיות הקבוצה האוניברסאלית [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{ C \ne\varnothing }[/math] השייכת לחיתוך [math]\displaystyle{ P(A)\cap P(B) }[/math]. קבוצות החזקה הן אוסף תת הקבוצות, ולכן [math]\displaystyle{ C\subseteq A \and C\subseteq B }[/math]. מכיוון ש-[math]\displaystyle{ C }[/math] אינה ריקה קיים בה איבר [math]\displaystyle{ c\in C }[/math] וקל לראות ש-[math]\displaystyle{ (c\in A)\and (c\in B) }[/math] ולכן [math]\displaystyle{ c }[/math] מוכל בחיתוך, בסתירה לכך שהחיתוך ריק.