תרגול 6 תשעז

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

המשך קבוצות

משלים

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

פתרון

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

$x\in A \triangle B \iff (x\in A \land x\notin B)\lor (x\in B \land x\notin A) \iff$

$(x\notin A^c \land x\in B^c)\lor (x\notin B^c \land x\in A^c)$ ומחילופיות "וגם" ו"או":

$(x\notin B^c \land x\in A^c)\lor (x\notin A^c \land x\in B^c) \iff$ $(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$

תרגיל

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

א. מצאו את $\bigcup_{n\in \mathbb{N}} B_n$.

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

פתרון

א. התשובה: $\mathbb{N}\smallsetminus \{1\}$. הוכחה:

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

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

ב. נתייחס ל-$\mathbb{N}$ כקבוצה האוניברסלית לדיוננו. לפי דה-מורגן נקבל:$\bigcap_{n\in \mathbb{N}} D_n=\bigcap_{n\in \mathbb{N}} B_n^c=(\bigcup_{n\in \mathbb{N}} B_n)^c=\{1\}$.

קבוצת החזקה

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

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

תרגיל

הוכיחו או הפריכו: $A\cap P(P(A))=\varnothing$.

פתרון

הפרכה : ניקח $A=\{1,\{\{1\}\}\}$.

תרגיל

הוכיחו או הפריכו:

א. $P(A)\cap P(B)=P(A\cap B)$

ב. $P(A)\cup P(B)=P(A\cup B)$

פתרון

א. הוכחה: $X\in P(A)\cap P(B) \iff X\subseteq A\land X\subseteq B\iff$

$X\subseteq A\cap B\iff X\in P(A\cap B)$

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

למעשה הוכיחו כי $P(A)\cup P(B)=P(A\cup B)$ אם ורק אם $A\subseteq B$ או $B\subseteq A$.

תרגיל ממבחן

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