88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 1

קישורים

מידע רב חופף בין הקורס שלנו לקורס תורת הקבוצות, ניתן להעזר לכן בקורס תורת הקבוצות בויקיפדיה

קבוצות

ההגדרה האינטואיטיבית לקבוצה הינה "אוסף של איברים". ההגדרה הזו מובילה לסתירות לוגיות כגון "פרדוקס ראסל". נביט בקבוצה הבאה:

• X=אוסף כל הקבוצות שאינן שייכות לעצמן

אם X שייכת לקבוצה הזו, אזי היא אינה שייכת לקבוצה. אולם, אם היא אינה שייכת לקבוצה אזי היא כן שייכת לקבוצה.

סתירה אינה מקובלת במחוזות המתמטיקאים, ולכן הגדירו את "תורת הקבוצות האקסיומטית" העוקפת בעייה זו. ניתן לקרוא יותר על נושא זה בקישור לעיל, עבורנו מספיקה ההגדרה האינטואיטיבית.

אם כן, נחזור להגדרתנו הנאיבית; קבוצה הינה אוסף של איברים שונים. בקבוצה אין משמעות לסדר האיברים, ואיבר אינו יכול להופיע פעמיים. דוגמאות ל3 קבוצות:

[math]\displaystyle{ \{1,horse,3\} }[/math], [math]\displaystyle{ \{1,2,3\} }[/math] ו[math]\displaystyle{ \{1,\{2,3\},\{\}\} }[/math]

איבר השייך לקבוצה אנו מסמנים בסימן [math]\displaystyle{ \in }[/math]. למשל [math]\displaystyle{ 1\in\{1,2,3\} }[/math], ואילו [math]\displaystyle{ 4\notin\{1,2,3\} }[/math]. שימו לב שגם [math]\displaystyle{ 1\notin\{\{1,2,3\}\} }[/math] שכן האיבר היחיד בקבוצה זו הינה הקבוצה [math]\displaystyle{ \{1,2,3\} }[/math].

• אומרים שקבוצה A מוכלת בקבוצה B (מסומן [math]\displaystyle{ A \subseteq B }[/math]) אם כל האיברים בA הם גם איברים בB. בשפה מדויקת, A מוכלת בB אם מתקיים [math]\displaystyle{ \forall a\in A: a\in B }[/math].

• חיתוך של שתי קבוצות A ו B הינו אוסף האיברים המוכלים גם בA וגם בB (מסומן [math]\displaystyle{ A\cap B }[/math]). מתקיים ש[math]\displaystyle{ a \in A\cap B \iff (a\in A \and a\in B) }[/math].

• איחוד של שתי קבוצות A ו B הינו אוסף האיברים המוכלים בA או בB (מסומן [math]\displaystyle{ A\cup B }[/math]). מתקיים ש[math]\displaystyle{ a \in A\cup B \iff (a\in A \or a\in B) }[/math].

• קבוצות הן שוות אם הן מכילות את אותם האיברים. הדרך הנפוצה להוכיח שיוויון הינה הכלה דו כיוונית: A=B אם [math]\displaystyle{ (A\subseteq B) \and (B \subseteq A) }[/math].

• A הפרש B הינה הקבוצה המכילה את כל האיברים בA שאינם בB (מסומן A\B). מתקיים ש [math]\displaystyle{ x\in A/B \iff (x\in A) \and (x\notin B) }[/math].

• ההפרש הסימטרי בין שתי קבוצות A וB הוא אוסף האיברים הנמצאים באחת הקבוצות אך לא בחיתוך (מסומן [math]\displaystyle{ A\Delta B }[/math]). מתקיים ש [math]\displaystyle{ 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 / A\cap B) }[/math]

תכונות האיחוד והחיתוך (דומה לכפל וחיבור)

• אסוציאטיביות: [math]\displaystyle{ (A\cap B)\cap C = A\cap (B\cap C) }[/math] (וכנ"ל לגבי איחוד)
• חילוף: [math]\displaystyle{ A\cap B = B\cap A }[/math] (וכנ"ל לגבי איחוד)
• דיסטריביוטיביות: [math]\displaystyle{ A\cap (B\cup C) = (A\cap B) \cup (A\cap C) }[/math], וגם [math]\displaystyle{ A\cup (B\cap C) = (A\cup B) \cap (A\cup C) }[/math]

תרגיל

הוכח כי [math]\displaystyle{ (A\cap B)\cup C = (A\cup C)\cap (A\cup C) }[/math]. במילים: האיברים שהם (גם בA וגם בB) או בC הם בדיוק האיברים ב(A או C) וגם ב(B או C)

פתרון

נראה שקילות בין התנאים של איבר להיות באחת הקבוצות.

[math]\displaystyle{ x\in (A\cap B)\cup C \iff [x\in (A\cap B)] \or [x\in C] \iff [x\in A \and x\in B] \or [x\in C] }[/math]

כעת, מתוך הטאוטולוגיה [math]\displaystyle{ (p\and q)\or r \iff (p\or r)\and(p\or r) }[/math] קל להשיג את השקילות למה שצריך.

תרגיל

הוכח כי הקבוצה הריקה [math]\displaystyle{ \phi=\{\} }[/math] מוכלת בכל קבוצה A

פתרון

יש להוכיח את הפסוק הבא: [math]\displaystyle{ \forall a\in\phi : a\in A }[/math]. אבל מכיוון שאין איברים בקבוצה הריקה, המשפט הזה נכון באופן ריק. זכרו ששקר גורר כל דבר, לכן האטום "איבר a שייך לקבוצה הריקה" גורר כל דבר.

הערה: שימו לב שעל מנת להוכיח שקבוצה A אינה מוכלת בקבוצה B, יש להראות כי קיים איבר בA שאינו שייך לB. אם היינו משתמשים בפסוק "כל האיברים בA אינם בB" היינו מקבלים שהקבוצה הריקה כל מוכלת בכל קבוצה, וגם אינה מוכלת בכל קבוצה.

תרגיל

נתון [math]\displaystyle{ A=\{\phi\} }[/math] ונתון [math]\displaystyle{ B=\{\phi,\{\phi\}\} }[/math]. סמן את הביטויים הנכונים:

1. [math]\displaystyle{ \phi\subseteq B }[/math] (כן)
2. [math]\displaystyle{ \phi\in \phi }[/math] (לא)
3. [math]\displaystyle{ A\subseteq B }[/math] (כן)
4. [math]\displaystyle{ A\in B }[/math] (כן)
5. [math]\displaystyle{ A\cup B = B }[/math] (כן)
6. [math]\displaystyle{ A\cap B=\phi }[/math] (לא)

תרגיל

הוכח כי [math]\displaystyle{ A\cap (B/C)=(A\cap B) / (A\cap C) }[/math]

פתרון

[math]\displaystyle{ 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]\displaystyle{ \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]\displaystyle{ A=\{2m+1:m\in\mathbb{Z}\} }[/math], ו [math]\displaystyle{ B=\{2m+3:m\in\mathbb{Z}\} }[/math]. הוכח שA=B.

פתרון

נוכיח הכלה דו כיוונית. נניח [math]\displaystyle{ x\in A }[/math] לכן קיים מספר שלם m כך ש [math]\displaystyle{ x=2m+1 }[/math]. קל לראות שמתקיים [math]\displaystyle{ x=2(m-1)+3 }[/math] אבל אז מכיוון ש m-1 הינו מספר שלם מתקיים [math]\displaystyle{ x\in B }[/math] כפי שרצינו.

ההכלה בכיוון ההפוך דומה.

הגדרה: תהי קבוצה U, ונביט בתתי קבוצות שלה A. ניתן להגדיר את המשלים של A כאוסף האיברים בU שאינם בA (ההפרש), מסומן [math]\displaystyle{ A^c }[/math]. לא ניתן לדבר על משלים אוניברסאלי ללא U מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיד לסתירות כמו פרדוקס ראסל).

על המשלימים מתקיימים חוקי דה מורגן (הנובעים ישירות מחוקי דה מורגן בלוגיקה):

• [math]\displaystyle{ (A\cap B)^c = A^c \cup B^c }[/math]
• [math]\displaystyle{ (A\cup B)^c = A^c \cap B^c }[/math]

הגדרה: תהי קבוצה A. נגדיר את קבוצת החזקה של A בתור אוסף כל תתי הקבוצות של A. מסומן [math]\displaystyle{ P(A)=\{X:X\subseteq A\} }[/math]

דוגמא:

[math]\displaystyle{ A=\{1,2\} }[/math] אזי [math]\displaystyle{ P(A)=\{\{\},\{1\},\{2\},\{1,2\}\} }[/math].

האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה?

תרגיל ממבחן

יהיו A,B,C קבוצות. הוכיחו/הפריכו: א. אם [math]\displaystyle{ A \not\subseteq B \cap C }[/math] אזי [math]\displaystyle{ (A/B)\cap(A/C)\neq \phi }[/math] ב. אם [math]\displaystyle{ A\subseteq B }[/math] אזי [math]\displaystyle{ A\cup(B/A)=B }[/math] ג. אם [math]\displaystyle{ A\cap B=\phi }[/math] אזי [math]\displaystyle{ P(A)\cap P(B) = \{\phi\} }[/math]

פתרון

א. הפרכה: [math]\displaystyle{ A=\{1,2\},B=\{1\},C=\{2\} }[/math]. אזי ברור שA איננה מוכלת בחיתוך של B וC אבל [math]\displaystyle{ (A/B)\cap(A/C)=\{2\}\cap\{1\}=\phi }[/math]

ב. נתון שלכל [math]\displaystyle{ a\in A }[/math] מתקיים [math]\displaystyle{ a \in B }[/math]. אזי [math]\displaystyle{ 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]\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{ P(A)\cap P(B)\neq \{\phi\} }[/math]. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה C המוכלת בחיתוך. קבוצות החזקה הן אוסף תתי הקבוצות, ולכן [math]\displaystyle{ C\subseteq A \and C\subseteq B }[/math]. מכיוון שC אינה ריקה קיים בה איבר [math]\displaystyle{ \exists c\in C }[/math] וקל מאד לראות ש[math]\displaystyle{ (c\in A)\and (c\in B) }[/math] ולכן c מוכל בחיתוך בסתירה לכך שהחיתוך ריק.