=המשך קבוצות=
==תרגילמשלים ==הוכיחו כי <math>A\cap (B\setminus C)=(A\cap B) \setminus (A\cap C)</math>.
===פתרון===דרך גרירות לוגיות'''הגדרה''':תהי קבוצה <math>U</math>, ונביט בתת קבוצה שלה <math>A</math>. ניתן להגדיר את ה'''משלים''' של <math>A</math> כאוסף האיברים ב-<math>U</math> שאינם ב-<math>A</math> (כלומר ההפרש <math>U\setminus A</math>), המסומן <math>A^c</math>. לא ניתן לדבר על משלים אוניברסלי ללא <math>U</math> מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).
תכונות בסיסיות:* <math>xA\in cup A^c = U</math>* <math>\cap (B\setminus C) \iffvarnothing^c = U</math>* <math>(x\in A) \and [(x\in B) \and (x\notin C)] U^c = \iffvarnothing</math>* <math>[(x\in A^c) \and (x\in B) \and (x\notin C)] \or [(x\in ^c = A) \and (x\in B) \and (x\notin A)] </math>
בשורה האחרונה הוספנו סתירה בעזרת הקשר "או" ולכן נשארנו עם ביטוי שקול. כעת נשתמש בחוק הפילוג של הלוגיקהעל המשלימים מתקיימים חוקי דה מורגן (הנובעים ישירות מחוקי דה מורגן בלוגיקה):*<math>(A\cap B)^c = A^c \cup B^c</math>*<math>(A\cup B)^c = A^c \cap B^c</math>הערה: באופן כללי מתקיים * <math>(\bigcap _{i\in I} A_i)^c = \bigcup _{i\in I} A_{i}^c </math>* <math>(\bigcup _{i\in I} A_i)^c = \bigcap _{i\in I} A_{i}^c </math>
<math>\iff [(x\in A) \and (x\in B)]\and [(x\notin C)\or(x\notin A)]\iff</math><math>[(x\in A) \and (x\in B)]\and \neg [(x\in C)\and(x\in A)]</math>===תרגיל===
וזה בדיוק מה שרצינוהוכיחו כי <math>A \triangle B = A^c \triangle B^c</math>.
הוכחה נוספת בעזרת הכלה דו כיוונית:====פתרון====
בכיוון (<math>\subseteq</math>) נניח <math>x\in A\cap(B\backslash C)</math> אזי נשתמש בהצגת ההפרש הסימטרי כאיחוד ההפרשים:
<math>x\in A \land triangle B \iff (x\in B A \land x\notnotin B)\lor (x\in C B \land x\notin A) \Leftarrowiff</math>
<math>(x\in notin A^c \cap land x\in B ^c)\land lor (x\notnotin B^c \land x\in A\cap C \Leftarrow^c)</math>ומחילופיות "וגם" ו"או":
<math>(x\notin B^c \land x\in A^c)\lor (x\notin A^c \cap land x\in B^c) \backslash iff</math><math>(x\in A^c \cap Cland x\notin B^c)\lor (x\in B^c \land x\notin A^c) \iff x\in A^c \triangle B^c</math>
בכיוון (===תרגיל===לכל <math>n\supseteqin \mathbb{N}</math>) נניח נגדיר <math>xA_n=\{k\in (A\cap B) mathbb{N}|2\backslash (Aleq k\leq 2n-1\}</math> ונגדיר <math>B_n=A_{n+1}\cap C)smallsetminus A_n</math> אזי .
א. מצאו את <math>x\in A\cap B \land x\notbigcup_{n\in A\cap C \Leftarrowmathbb{N}} B_n</math>.
ב. נגדיר <math>xD_n=\in A mathbb{N}\land x\in B \land xsmallsetminus B_n</math>. מצאו את <math>\notbigcap_{n\in C \Leftarrow mathbb{N}} D_n</math>.
(כי אם <math>x\in C</math> אזי <math>x\in A\cap C</math> סתירה)====פתרון====
א. התשובה: <math>x\in Amathbb{N}\cap(Bsmallsetminus \backslash C){1\Leftarrow }</math>. הוכחה:
== משלים ==<math>\bigcup_{n\in \mathbb{N}} B_n \subseteq \mathbb{N}\smallsetminus \{1\} </math>: הכל תת קבוצות של הטבעיים וכל הקבוצות מוגדרות ע"י איברים הגדולים מ-<math>2</math>.
'''הגדרה''': תהי קבוצה <math>U\mathbb{N}\smallsetminus \{1\} \subseteq \bigcup_{n\in \mathbb{N}} B_n</math>, ונביט בתת קבוצה שלה : יהי <math>Aa\in \mathbb{N}\smallsetminus \{1\}</math>נמצא קבוצה בה הוא נמצא. ניתן להגדיר את ה'''משלים''' של נשים לב ש-<math>AB_n=\{2\leq k\leq 2n+1\}\smallsetminus \{2\leq k\leq 2n-1\}=\{2n,2n+1\}</math> כאוסף האיברים ב-. לכן אם <math>Ua</math> שאינם זוגי הוא נמצא ב-<math>AB_{\frac{n}{2}}</math> (כלומר ההפרש ואם אי-זוגי אז <math>Ua\setminus Ain B_{\frac{n-1}{2}}</math>), המסומן <math>A^c</math>. לא ניתן לדבר על משלים אוניברסלי ללא <math>U</math> מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).
תכונות בסיסיות:* ב. נתייחס ל-<math>A\cup A^c = Umathbb{N}</math>* <math>\varnothing^c = U</math>* <math>U^c = \varnothing</math>* <math>(A^c)^c = A</math> על המשלימים מתקיימים חוקי כקבוצה האוניברסלית לדיוננו. לפי דה -מורגן (הנובעים ישירות מחוקי דה מורגן בלוגיקה)נקבל:*<math>(A\cap B)^c = A^c bigcap_{n\cup B^c</math>*<math>(Ain \cup B)^c = A^c \cap B^c</math>הערה: באופן כללי מתקיים * <math>(\bigcap _mathbb{i\in IN} A_i)^c } D_n= \bigcup _bigcap_{in\in I} A_\mathbb{iN}}B_n^c </math>* <math>=(\bigcup _bigcup_{in\in I\mathbb{N}} A_iB_n)^c = \bigcap _{i1\in I} A_{i}^c </math>.
==קבוצת החזקה==
'''הגדרה''': תהי קבוצה <math>A</math>. נגדיר את '''קבוצת החזקה''' של <math>A</math> בתור אוסף כל תת הקבוצות של <math>A</math>. נסמן <math>P(A)=\{X:X\subseteq A\}</math>.
דוגמה: נבחר <math>A=\{1,2\}</math> אזי
<math>P(A)=\{\{\},\{1\},\{2\},\{1,2\}\}</math>.
האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה? הוכיחו זאת באינדוקציה.
===תרגיל===
הוכיחו או הפריכו: <math>A\cap P(P(A))=\varnothing</math>.
====פתרון====
הפרכה : ניקח <math>A=\{1,\{\{1\}\}\}</math>.
===תרגיל===
הוכיחו או הפריכו:
א. <math>P(A)\cap P(B)=P(A\cap B)</math>
ב. <math>P(A)\cup P(B)=P(A\cup B)</math>
====פתרון====
א. הוכחה: <math>X\in P(A)\cap P(B) \iff X\subseteq A\land X\subseteq B\iff</math>
<math>X\subseteq A\cap B\iff X\in P(A\cap B)</math>
ב. הפרכה: ניקח <math>A=\{1\},B=\{2\}</math>. אז <math>\{1,2\} \in P(A\cup B)</math>, אבל לא ל-<math>P(A)\cup P(B)</math>.
למעשה הוכיחו כי <math>P(A)\cup P(B)=P(A\cup B)</math> אם ורק אם <math>A\subseteq B</math> או <math>B\subseteq A</math>.
===תרגיל ממבחן===
ג. אם <math>A\cap B=\varnothing</math> אזי <math>P(A)\cap P(B) = \{\varnothing\}</math>
===פתרון===
א. '''הפרכה''': <math>A=\{1,2\},B=\{1\},C=\{2\}</math>. אזי ברור ש-<math>A</math> איננה מוכלת בחיתוך <math>B\cap C</math> אבל <math>(A\setminus B)\cap(A\setminus C)=\{2\}\cap\{1\}=\varnothing</math>.
ב. נתון שלכל <math>a\in A</math> מתקיים <math>a \in B</math>. אזי
<math>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)] </math>
כעת, הצד הימני הוא טאוטולוגיה וניתן להסיר אותו. מכיוון שנתון <math>[(x\in A)\rightarrow or (x\in B)</math> ניתן להסיק בקלות ש<math>] \and [(x\in A)\or (x\in B) \iff (x\in Bnotin A)] </math> כפי שרצינו.
דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית כעת, הצד הימני הוא טאוטולוגיה וניתן להסיר אותו. מכיוון שנתון <math>U:=(x\in A)\rightarrow (x\in B)</math> ואז צריך להוכיח כי ניתן להסיק בקלות ש-<math>A(x\cup in A^c =U)\or (x\in B) \iff (x\in B)</math> וזה אכן נכון!, כפי שרצינו.
דרך נוספת: נגדיר את <math>B</math> להיות הקבוצה האוניברסאלית <math>U:=B</math> ואז צריך להוכיח כי
<math>A\cup A^c =U</math> וזה אכן נכון!
ג. נניח בשלילה ש-<math>P(A)\cap P(B)\neq \{\varnothing\}</math>. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה , החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה <math>C \varnothing ne\not=Cvarnothing</math> השייכת לחיתוך <math>P(A)\cap P(B)</math>. קבוצות החזקה הן אוסף תת הקבוצות, ולכן <math>C\subseteq A \and C\subseteq B</math>. מכיוון שC ש-<math>C</math> אינה ריקה קיים בה איבר <math>\exists c\in C</math> וקל מאד לראות ש-<math>(c\in A)\and (c\in B) </math> ולכן <math>c </math> מוכל בחיתוך , בסתירה לכך שהחיתוך ריק.