שינויים
/* תרגיל */
::<math>\mathbb{C}=\{a+bi : a,b\in \mathbb{R}, i^2 =-1\}</math> המספרים המרוכבים
==== תרגיל (חשוב!)====
מצאו קבוצות A,B כך ש:
*<math>A\in B, A\subseteq B</math>
*<math>A\in B, A\not\subseteq B</math>
*<math>A\not\in B, A\subseteq B</math>
*<math>A\not\in B, A\not\subseteq B</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=\{2m+1:m\in\mathbb{Z}\}</math>, ו <math>B=\{2m+3:m\in\mathbb{Z}\}</math>. הוכח שA=B.
פתרון
נוכיח הכלה דו כיוונית. נניח <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>\{n^2\mid n\in \mathbb{N}\}=\{n\in \mathbb{N}\mid \sqrt{n}\in \mathbb{N}\}</math>
==== תרגיל ====
הוכיחו כי <math>\left\{ 8x+6y\,\mid x,y\in\mathbb{Z}\right\} =\left\{ n\in\mathbb{Z}\,\mid\exists k\in\mathbb{Z}:\,n=2k\right\}</math>
=== פעולות על קבוצות ===
*'''חיתוך''' של שתי קבוצות A ו B הינו אוסף האיברים השייכים גם לA וגם לB (מסומן <math>A\cap B</math>). מתקיים ש<math>a \in A\cap B \iff (a\in A \and a\in B)</math>.
*קבוצות הן שוות אם הן מכילות את אותם האיברים. הדרך הנפוצה להוכיח שיוויון הינה '''הכלה דו כיוונית''': A=B אם ורק אם <math>(A\subseteq B) \and (B \subseteq A) </math>.
*A '''הפרש''' B הינה הקבוצה המכילה את כל האיברים בA שאינם בB (מסומן A\B). מתקיים ש <math>x\in A/\setminus B \iff (x\in A) \and (x\notin B)</math>.
*'''ההפרש הסימטרי''' בין שתי קבוצות A וB הוא אוסף האיברים הנמצאים באחת הקבוצות אך לא בחיתוך (מסומן <math>A\Delta B</math>). מתקיים ש <math>x\in A\Delta B \iff ((x\in A)\and (x\notin B)) \or ((x\in B)\and (x\notin A)) \iff x\in (A\cup B) / \smallsetminus (A\cap B)</math>
דוגמא:
<math> B \cap C = \emptyset</math>
<math>C \backslash smallsetminus A =\{\{1,2\}\}</math>
<math> B \Delta C = B \cup C</math>
ג. <math>\phi \cup A = \{x:x\in \phi \or x\in A\}= \{x:x\in A \}=A </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>\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>\subseteq</math>) נניח <math>x\in A\cap(B\backslash C)</math> אזי
<math>x\in A \land x\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)</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>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>\bigcap _{i\in \mathbb{N}} A_i = \phi </math>
==== תרגיל ====
לכל n>1 טבעי נגדיר <math>A_n</math> להיות קבוצת כל הראשוניים המחלקים את n.
חשבו את
*<math>A_{12}\cap A_{10}</math>
*<math>\cup_{n=2}^{15} A_n</math>
*<math>\cap_{n=2}^5 A_{6n}</math>
*<math>\bigcup _{i=2}^\infty A_i</math>
*<math>\bigcup _{i=1}^\infty A_{2^i}</math>
==== תרגיל (הכללת פילוג)====
וגם <math>x\in A_i</math> לכן <math>x\in B</math> וגם <math>x\in (\bigcup _{i\in I} A_i)</math> ולכן <math>x\in (\bigcup _{i\in I} A_i)\cap B</math>
====פתרוןמשלים ====דרך גרירות לוגיות:
'''הגדרה''': תהי קבוצה U, ונביט בתת קבוצה שלה A. ניתן להגדיר את ה'''משלים''' של A כאוסף האיברים בU שאינם בA (כלומר ההפרש <math>xU\in setminus A\cap (B</Cmath>)\iff (x\in , מסומן <math>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)] ^c</math>. לא ניתן לדבר על משלים אוניברסאלי ללא U מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).
תכונות בסיסיות:
* <math>A\cup A^c = U</math>
* <math>\emptyset^c = U</math>
* <math>U^c = \emptyset</math>
* <math>(A^c)^c = A</math>
===תרגיל===
הוכיחו כי <math>\iff [(x\in A) \and (x\in triangle B)]\and [(x\notin C)\or(x\notin = A)]^c \iff [(x\in A) \and (x\in triangle B)]\and \neg [(x\in C)\and(x\in A)] ^c</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\in A\cap B \land x\not\in A\cap C \Leftarrow^c</math>אזי <math>x\in A \land x\in notin B \land x\not\in C \Leftarrow </math>(כי אם לכן לפי נתון <math>x\in C</math> אזי <math>x\in notin A\cap C</math> סתירה)לכן <math>x\in A\cap(B\backslash C)\Leftarrow ^c</math>.
===תרגיל== תרגיל ==נתונות <math>A=\{2m+1:m\in\mathbb{Z}\}</math>, ו <math>B=\{2m+3:m\in\mathbb{Z}\}</math>. הוכח שA=B.
ב. <math>\bigcap _{n\in \mathbb{N}} A_n ==== משלים ====\varnothing </math>
ב. מספיק להראות <math>A_1\cap A_2=\phi</math>.
ג. נתייחס ל-<math>\mathbb{R}</math> כקבוצה האוניברסלית לדיוננו. לפי דה-מורגן נקבל:<math>\bigcap_{n\in \mathbb{N}} B_n=\bigcap_{n\in \mathbb{N}} A_n^c=(\bigcup_{n\in \mathbb{N}} A_n)^c=(\mathbb{Z}^c)^c=\mathbb{Z}</math>.
=== קבוצת החזקה ===
'''הגדרה''': תהי קבוצה A. נגדיר את '''קבוצת החזקה''' של A בתור אוסף כל תתי הקבוצות של A. מסומן <math>P(A)=\{X:X\subseteq A\}</math>
האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה?
====תרגיל====
הוכיחו או הפריכו:
א. לכל A,B מתקיים: <math>P(A)\cap P(B)=P(A\cap B)</math>
ב. לכל A,B מתקיים: <math>P(A)\cup P(B)=P(A\cup B)</math>
ג. קיימת A כך ש <math>A\cap P(A)\neq \emptyset</math>
ד. קיימת A סופית כך ש <math>A\cap P(A)=P(A)</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=\{\emptyset\}</math>
ד. לא, כי אז <math>P(A)\subseteq A</math> שלא ייתכן משיקולי עוצמה (בקבוצה סופית: ב <math>P(A)</math> יש יותר איברים מ Aׂׂ)
==== תרגיל ====
הוכיחו כי אם <math>P(A)\cup P(B)=P(A\cup B)</math> אז <math>A\subseteq B</math> או <math>B\subseteq A</math>
==== תרגיל ====
תהא <math>A\subseteq U</math>. הוכיחו כי <math>P(A^c)\setminus\{\emptyset\}\subseteq P(A)^c</math>
===תרגיל ממבחן===
דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית <math>U:=B</math> ואז צריך להוכיח כי
<math>A\cap 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 מוכל בחיתוך בסתירה לכך שהחיתוך ריק.