גרסה אחרונה מ־19:17, 9 ביולי 2019

המשך קבוצות

משלים

הגדרה: תהי קבוצה [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\cap P(P(A))=\varnothing }[/math].

פתרון

הפרכה : ניקח [math]\displaystyle{ A=\{1,\{\{1\}\}\} }[/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] מוכל בחיתוך, בסתירה לכך שהחיתוך ריק.

@@ שורה 1: / שורה 1: @@
-==המשך קבוצות==
+חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].
+=המשך קבוצות=
+== משלים ==
+'''הגדרה''': תהי קבוצה <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>A\cup A^c = U</math>
+* <math>\varnothing^c = U</math>
+* <math>U^c = \varnothing</math>
+* <math>(A^c)^c = 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=\{\phi\}</math> ונתון <math>B=\{\phi,\{\phi\}\}</math>. סמן את הביטויים הנכונים:
-#<math>\phi\subseteq B</math> (כן)
-#<math>\phi\in \phi</math> (לא)
-#<math>\phi \subseteq \phi</math> (כן)
-#<math>A\subseteq B</math> (כן)
-#<math>A\in B</math> (כן)
-#<math>A\cup B = B</math> (כן)
-#<math>A\cap B=\phi</math> (לא)
-===תרגיל===
+הוכיחו כי <math>A \triangle B = A^c \triangle B^c</math>.
-הוכח כי <math>A\cap (B/C)=(A\cap B) / (A\cap C)</math>
 ====פתרון====
-דרך גרירות לוגיות:
-<math>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>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\in \mathbb{N}</math> נגדיר <math>A_n=\{k\in \mathbb{N}|2\leq k\leq 2n-1\}</math> ונגדיר <math>B_n=A_{n+1}\smallsetminus A_n</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>\bigcup_{n\in \mathbb{N}} B_n</math>.
+ב. נגדיר <math>D_n=\mathbb{N}\smallsetminus B_n</math>. מצאו את <math>\bigcap_{n\in \mathbb{N}} D_n</math>.
-וזה בדיוק מה שרצינו.
+====פתרון====
+א. התשובה: <math>\mathbb{N}\smallsetminus \{1\}</math>. הוכחה:
-דרך הכלה דו כיוונית:
+<math>\bigcup_{n\in \mathbb{N}} B_n \subseteq \mathbb{N}\smallsetminus \{1\} </math>: הכל תת קבוצות של הטבעיים וכל הקבוצות מוגדרות ע"י איברים הגדולים מ-<math>2</math>.
-(<math>\subseteq</math>) נניח <math>x\in A\cap(B\backslash C)</math> אזי
+<math>\mathbb{N}\smallsetminus \{1\} \subseteq \bigcup_{n\in \mathbb{N}} B_n</math>: יהי <math>a\in \mathbb{N}\smallsetminus \{1\}</math> נמצא קבוצה בה הוא נמצא. נשים לב ש-<math>B_n=\{2\leq k\leq 2n+1\}\smallsetminus \{2\leq k\leq 2n-1\}=\{2n,2n+1\}</math>. לכן אם <math>a</math> זוגי הוא נמצא ב- <math>B_{\frac{n}{2}}</math> ואם אי-זוגי אז <math>a\in B_{\frac{n-1}{2}}</math>.
-<math>x\in A \land x\in B \land x\not\in C \Leftarrow</math>
+ב. נתייחס ל-<math>\mathbb{N}</math> כקבוצה האוניברסלית לדיוננו. לפי דה-מורגן נקבל:<math>\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>x\in A\cap B \land x\not\in A\cap C \Leftarrow</math>
-<math>x\in (A\cap B) \backslash (A\cap C)</math>
-(<math>\supseteq</math>) נניח <math>x\in (A\cap B) \backslash (A\cap C)</math> אזי
+==קבוצת החזקה==
-<math>x\in A\cap B \land x\not\in A\cap C \Leftarrow</math>
+'''הגדרה''': תהי קבוצה <math>A</math>. נגדיר את '''קבוצת החזקה''' של <math>A</math> בתור אוסף כל תת הקבוצות של <math>A</math>. נסמן <math>P(A)=\{X:X\subseteq A\}</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>A=\{2m+1:m\in\mathbb{Z}\}</math>, ו <math>B=\{2m+3:m\in\mathbb{Z}\}</math>. הוכח שA=B.
+הוכיחו או הפריכו: <math>A\cap P(P(A))=\varnothing</math>.
 ====פתרון====
-נוכיח הכלה דו כיוונית. נניח <math>x\in A</math> לכן קיים מספר שלם m כך ש <math>x=2m+1</math>. קל לראות שמתקיים <math>x=2(m-1)+3</math> אבל אז מכיוון ש m-1 הינו מספר שלם מתקיים <math>x\in B</math> כפי שרצינו.
+הפרכה : ניקח <math>A=\{1,\{\{1\}\}\}</math>.
-ההכלה בכיוון ההפוך דומה.
+===תרגיל===
+הוכיחו או הפריכו:
-==== משלים ====
+א. <math>P(A)\cap P(B)=P(A\cap B)</math>
-'''הגדרה''': תהי קבוצה U, ונביט בתת קבוצה שלה A. ניתן להגדיר את ה'''משלים''' של A כאוסף האיברים בU שאינם בA (כלומר ההפרש <math>U\setminus A</math>), מסומן <math>A^c</math>. לא ניתן לדבר על משלים אוניברסאלי ללא U מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).
+ב. <math>P(A)\cup P(B)=P(A\cup B)</math>
-תכונות בסיסיות:
+====פתרון====
-* <math>A\cup A^c = U</math>
-* <math>\emptyset^c = U</math>
-* <math>U^c = \emptyset</math>
-* <math>(A^c)^c = 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>(\cap _{i\in I} A_i)^c = \cup _{i\in I} A_{i}^c </math>
-* <math>(\cup _{i\in I} A_i)^c = \cap _{i\in I} A_{i}^c </math>
+א. הוכחה: <math>X\in P(A)\cap P(B) \iff X\subseteq A\land X\subseteq B\iff</math>
-'''הגדרה''': תהי קבוצה A. נגדיר את '''קבוצת החזקה''' של A בתור אוסף כל תתי הקבוצות של A. מסומן <math>P(A)=\{X:X\subseteq A\}</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>A=\{1,2\}</math> אזי <math>P(A)=\{\{\},\{1\},\{2\},\{1,2\}\}</math>.
+למעשה הוכיחו כי <math>P(A)\cup P(B)=P(A\cup B)</math> אם ורק אם <math>A\subseteq B</math> או <math>B\subseteq A</math>.
-האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה?
 ===תרגיל ממבחן===
-יהיו A,B,C קבוצות. הוכיחו/הפריכו:
+תהינה <math>A,B,C</math> קבוצות. הוכיחו או הפריכו:
-א. אם <math>A \not\subseteq B \cap C</math> אזי <math>(A/B)\cap(A/C)\neq \phi</math>
+א. אם <math>A \not\subseteq B \cap C</math> אזי <math>(A\setminus B)\cap(A\setminus C)\neq \varnothing</math>
-ב. אם <math>A\subseteq B</math> אזי <math>A\cup(B/A)=B</math>
+ב. אם <math>A\subseteq B</math> אזי <math>A\cup (B\setminus A)=B</math>
-ג. אם <math>A\cap B=\phi</math> אזי <math>P(A)\cap P(B) = \{\phi\}</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 איננה מוכלת בחיתוך של B וC אבל <math>(A/B)\cap(A/C)=\{2\}\cap\{1\}=\phi</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/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>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</math>
-כעת, הצד הימני הוא טאוטולוגיה וניתן להסיר אותו. מכיוון שנתון <math>(x\in A)\rightarrow (x\in B)</math> ניתן להסיק בקלות ש<math>(x\in A)\or (x\in B) \iff (x\in B)</math> כפי שרצינו.
+<math>[(x\in A) \or (x\in B)] \and [(x \in A)\or (x\notin A)] </math>
-דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית <math>U:=B</math> ואז צריך להוכיח כי
+כעת, הצד הימני הוא טאוטולוגיה וניתן להסיר אותו. מכיוון שנתון <math>(x\in A)\rightarrow (x\in B)</math> ניתן להסיק בקלות ש-<math>(x\in A)\or (x\in B) \iff (x\in B)</math>, כפי שרצינו.
-<math>A\cap A^c =U</math> וזה אכן נכון!
+דרך נוספת: נגדיר את <math>B</math> להיות הקבוצה האוניברסאלית <math>U:=B</math> ואז צריך להוכיח כי
+<math>A\cup A^c =U</math> וזה אכן נכון!
-ג. נניח בשלילה ש<math>P(A)\cap P(B)\neq \{\phi\}</math>. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה <math>\phi \not=C</math> השייכת לחיתוך <math>P(A)\cap P(B)</math>. קבוצות החזקה הן אוסף תתי הקבוצות, ולכן <math>C\subseteq A \and C\subseteq B</math>. מכיוון שC אינה ריקה קיים בה איבר <math>\exists c\in C</math> וקל מאד לראות ש<math>(c\in A)\and (c\in B) </math> ולכן c מוכל בחיתוך בסתירה לכך שהחיתוך ריק.
+ג. נניח בשלילה ש-<math>P(A)\cap P(B)\neq \{\varnothing\}</math>. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה, החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה <math>C \ne\varnothing</math> השייכת לחיתוך <math>P(A)\cap P(B)</math>. קבוצות החזקה הן אוסף תת הקבוצות, ולכן <math>C\subseteq A \and C\subseteq B</math>. מכיוון ש-<math>C</math> אינה ריקה קיים בה איבר <math>c\in C</math> וקל לראות ש-<math>(c\in A)\and (c\in B) </math> ולכן <math>c</math> מוכל בחיתוך, בסתירה לכך שהחיתוך ריק.