שינויים

'''[[88-195 מתמטיקה בדידה לתיכוניסטים תשעא/- מערך שיעורתרגול|חזרה למערכי התרגול]]'''

*קבוצות הן שוות אם הן מכילות את אותם האיברים. הדרך הנפוצה להוכיח שיוויון הינה '''הכלה דו כיוונית''': 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>A=\{1,2,\{1\}\},B=\{1,\{2\}\},C=\{2,\{1,2\}\}</math> קבוצות. אזי: <math>A\cup B =\{1,2 ,\{1\},\{2\}\} </math> <math>(A\cup B)\cap C =\{2\} </math> <math> B \cap C = \emptyset</math> <math>C \smallsetminus A =\{\{1,2\}\}</math> <math> B \Delta C = B \cup C</math>

*A '''הפרש''' B הינה הקבוצה המכילה את כל האיברים בA שאינם בB (מסומן A\B). מתקיים ש <math>x\in A/B \iff (xDelta C = \in A) {1,\{1\},\{1,2\and (x}\notin B)}</math>.

הוכח כי <math>(A\cap B)\cup C = (A\cup C)\cap (AB\cup C)</math>. במילים: האיברים שהם (גם בA וגם בB) או בC הם בדיוק האיברים ב(A או C) וגם ב(B או C)

כעת, מתוך הטאוטולוגיה <math>(p\and q)\or r \iff (p\or r)\and(pq\or r)</math> קל להשיג את השקילות למה שצריך.(הערה: ניתן להשתכנע בקלות בטאוטולוגיה באופן הבא: אם r=1 אזי נשאר עם הטאוטולוגיה<math>1\iff 1</math> אם r=0 אזי נשאר עם הטאוטולוגיה<math>(p\land q)\iff (p)\land (q)</math>)

הוכח כי :א. הקבוצה הריקה <math>\phi=\{\}</math> מוכלת בכל קבוצה A ב. <math>\phi \cap A = \phi </math> ג. <math>\phi \cup A = A </math> 

א. יש להוכיח את הפסוק הבא: <math>\forall a\in\phi : a\in A</math>. אבל מכיוון שאין איברים בקבוצה הריקה, המשפט הזה נכון '''באופן ריק'''. זכרו ששקר גורר כל דבר, לכן האטום "איבר a שייך לקבוצה הריקה" גורר כל דבר. הערה: שימו לב שעל מנת להוכיח שקבוצה A אינה מוכלת בקבוצה B, יש להראות כי '''קיים''' איבר בA שאינו שייך לB. אם היינו משתמשים בפסוק "כל האיברים בA אינם בB" היינו מקבלים שהקבוצה הריקה לא מוכלת בכל קבוצה, וגם אינה מוכלת בכל קבוצה.

הערהב. <math>\phi \cap A = \{x: שימו לב שעל מנת להוכיח שקבוצה x\in \phi \and x\in A אינה מוכלת בקבוצה B, יש להראות כי '''קיים''' איבר בA שאינו שייך לB. אם היינו משתמשים בפסוק "כל האיברים בA אינם בB" היינו מקבלים שהקבוצה הריקה כל מוכלת בכל קבוצה, וגם אינה מוכלת בכל קבוצה.\}\subseteq \{x:x\in \phi \}=\phi </math>

===תרגיל===נתון ג. <math>A=\{\phi\}</math> ונתון <math>Bcup A = \{x:x\in \phi,\{or x\phiin A\}= \}</math>. סמן את הביטויים הנכונים{x:#<math>\phi\subseteq B</math> (כן)#<math>\phix\in \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>\iff [(x\in A) \and (x\in B)]\and [(x\notin C)\or(x\notin A)]\iff\iff [(x\in A) \and (x\in B)]\and \neg [(x\in C)\and(x\in A)] </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>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>   ===הכללה לאיחודים וחיתוכים כל שהם==='''מוטיבציה:''' הגדרנו את החיתוך והאיחוד עבור שתי קבוצות. לעיתים נרצה לחתוך או לאחד יותר קבוצות, לדוגמא נרצה לדבר על חיתוכן של 17 הקבוצות <math>A_1,A_2,\ldots,A_{17}</math>. מכיוון שחיתוך ואיחוד הן פעולות אסוציטיביות, ניתן לרשום <math>A_1\cap A_2\cap \ldots\cap A_{17}</math>, וזה ביטוי חד משמעי. אך צורת רישום זו היא ארוכה, ולכן אנו מסמנים את החיתוך הזה בקיצור הבא: <math>\bigcap _{i=1} ^{17} A_i</math>. לעיתים נרצה לחתוך או לאחד אוסף אינסופי של קבוצות, ולכך באה ההכללה הבאה: '''הגדרה:'''יהיו <math>\{A_i\}_{i\in I}</math> אוסף קבוצות כאשר <math>I</math> הוא קבוצת אינדקסים אזי נגדיר את האיחוד והחיתוך של אוסף הקבוצות כך:  <math>\bigcup _{i\in I} A_i := \{x| \exist i\in I :x\in A_i \} </math> <math>\bigcap _{i\in I} A_i := \{x| \forall i\in I :x\in A_i \} </math>. כאן יש להניח שקבוצת האינדקסים <math>I</math> לא ריקה. דוגמא: נגדיר <math>\forall n\in \mathbb{N} \; A_n:=[n,n+1]</math> אזי  <math>\bigcup _{i\in \mathbb{N}} A_i = [ 1,\infty ) </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>\{A_i\}_{i\in I}</math> אוסף קבוצות, B קבוצה. הוכיחו כי <math>(\bigcup _{i\in I} A_i)\cap B= \bigcup _{i\in I} (A_i\cap B) </math> פתרון: יהא <math>x\in (\bigcup _{i\in I} A_i)\cap B</math> אזי <math>x\in B</math> וגם <math>x\in (\bigcup _{i\in I} A_i)</math> לכן <math>x\in B</math> וגם <math>\exist i\in I :x\in A_i</math> ולכן <math>x\in A_i\cap B</math> ומכאן ש <math>x\in \bigcup _{i\in I} (A_i\cap B)</math> בכיוון שני: יהא <math>x\in \bigcup _{i\in I} (A_i\cap B)</math> ולכן <math>\exist i\in I :x\in A_i\cap B</math> לכן <math>x\in B</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>U\setminus A</math>), מסומן <math>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>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 מוכל בחיתוך בסתירה לכך שהחיתוך ריק.