=המשך קבוצות=
==תרגילמשלים ==הוכיחו כי <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>x\in A\cap (B\setminus C)\iff (x\in cup A) ^c = U</math>* <math>\and [(xvarnothing^c = U</math>* <math>U^c = \in B) \and varnothing</math>* <math>(x\notin C)]\iff [(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>A \triangle B = A^c \triangle B^c</math>.
<math>\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>x\in A \triangle B \iff (x\in A \land x\notin B)\lor (x\in B \land x\notin A) \iff</math>
<math>(x\notin A^c \land x\in B^c)\lor (x\notin B^c \land x\in A^c)</math> ומחילופיות "וגם" ו"או":
הוכחה בעזרת הכלה דו כיוונית:<math>(x\notin B^c \land x\in A^c)\lor (x\notin A^c \land x\in B^c) \iff</math><math>(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>n\subseteqin \mathbb{N}</math>) נניח נגדיר <math>xA_n=\{k\in A\cap(Bmathbb{N}|2\leq k\leq 2n-1\}</math> ונגדיר <math>B_n=A_{n+1}\backslash C)smallsetminus A_n</math> אזי .
א. מצאו את <math>x\in A \land xbigcup_{n\in B \land x\not\in C \Leftarrow</math><math>x\in A\cap B \land x\not\in A\cap C \Leftarrow</math><math>x\in (A\cap B) \backslash (A\cap C)mathbb{N}} B_n</math>.
בכיוון (ב. נגדיר <math>D_n=\supseteqmathbb{N}\smallsetminus B_n</math>) נניח . מצאו את <math>x\in (Abigcap_{n\cap B) \backslash (Ain \cap C)mathbb{N}} D_n</math> אזי .
<math>x\in A\cap B \land x\not\in A\cap C \Leftarrow</math><math>x\in A \land x\in B \land x\not\in C \Leftarrow </math>(כי אם <math>x\in C</math> אזי <math>x\in A\cap C</math> סתירה)<math>x\in A\cap(B\backslash C)\Leftarrow </math>====פתרון====
=== משלים ===א. התשובה: <math>\mathbb{N}\smallsetminus \{1\}</math>. הוכחה:
'''הגדרה''': תהי קבוצה <math>U\bigcup_{n\in \mathbb{N}} B_n \subseteq \mathbb{N}\smallsetminus \{1\} </math>, ונביט בתת קבוצה שלה <math>A</math>. ניתן להגדיר את ה'''משלים''' : הכל תת קבוצות של <math>A</math> כאוסף האיברים בהטבעיים וכל הקבוצות מוגדרות ע"י איברים הגדולים מ-<math>U</math> שאינם ב-<math>A</math> (כלומר ההפרש <math>U\setminus A</math>), המסומן <math>A^c</math>. לא ניתן לדבר על משלים אוניברסלי ללא <math>U2</math> מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).
תכונות בסיסיות<math>\mathbb{N}\smallsetminus \{1\} \subseteq \bigcup_{n\in \mathbb{N}} B_n</math>:* יהי <math>Aa\cup A^c = Uin \mathbb{N}\smallsetminus \{1\}</math>* נמצא קבוצה בה הוא נמצא. נשים לב ש-<math>B_n=\varnothing^c {2\leq k\leq 2n+1\}\smallsetminus \{2\leq k\leq 2n-1\}= U\{2n,2n+1\}</math>* . לכן אם <math>U^c = a</math> זוגי הוא נמצא ב- <math>B_{\varnothingfrac{n}{2}}</math>* ואם אי-זוגי אז <math>(A^c)^c = Aa\in B_{\frac{n-1}{2}}</math>.
על המשלימים מתקיימים חוקי דה מורגן (הנובעים ישירות מחוקי דה מורגן בלוגיקה):*ב. נתייחס ל-<math>(A\cap B)^c = A^c \cup B^cmathbb{N}</math>*<math>(A\cup B)^c = A^c \cap B^c</math>הערהכקבוצה האוניברסלית לדיוננו. לפי דה-מורגן נקבל: באופן כללי מתקיים * <math>(\bigcap _bigcap_{in\in I\mathbb{N} 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>cap P(P(A))=\{\{\},\{1\},\{2\},\{1,2\}\}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,B,C </math> קבוצות. הוכיחו/או הפריכו:
א. אם <math>A \not\subseteq B \cap C</math> אזי <math>(A\setminus B)\cap(A\setminus C)\neq \varnothing</math>
ג. אם <math>A\cap B=\varnothing</math> אזי <math>P(A)\cap P(B) = \{\varnothing\}</math>
===פתרון===
א. '''הפרכה''': <math>A=\{1,2\},B=\{1\},C=\{2\}</math>. אזי ברור שA ש-<math>A</math> איננה מוכלת בחיתוך של <math>B וC \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>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) \or (x\in B)] \and [(x \in A)\or (x\notin A)] </math>
כעת, הצד הימני הוא טאוטולוגיה וניתן להסיר אותו. מכיוון שנתון <math>(x\in A)\rightarrow (x\in B)</math> ניתן להסיק בקלות ש-<math>(x\in A)\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> מוכל בחיתוך , בסתירה לכך שהחיתוך ריק.