הבדלים בין גרסאות בדף "88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 1"
אחיה בר-און (שיחה | תרומות) (←תרגיל) |
(←תרגיל) |
||
(16 גרסאות ביניים של 3 משתמשים אינן מוצגות) | |||
שורה 32: | שורה 32: | ||
::<math>\mathbb{C}=\{a+bi : a,b\in \mathbb{R}, i^2 =-1\}</math> המספרים המרוכבים | ::<math>\mathbb{C}=\{a+bi : a,b\in \mathbb{R}, i^2 =-1\}</math> המספרים המרוכבים | ||
− | ==== תרגיל==== | + | ==== תרגיל (חשוב!)==== |
מצאו קבוצות A,B כך ש: | מצאו קבוצות A,B כך ש: | ||
*<math>A\in B, A\subseteq B</math> | *<math>A\in B, A\subseteq B</math> | ||
שורה 38: | שורה 38: | ||
*<math>A\not\in B, A\subseteq B</math> | *<math>A\not\in B, A\subseteq B</math> | ||
*<math>A\not\in B, A\not\subseteq B</math> | *<math>A\not\in B, A\not\subseteq B</math> | ||
− | ====תרגיל==== | + | |
+ | ====תרגיל (חשוב)==== | ||
נתון <math>A=\{\phi\}</math> ונתון <math>B=\{\phi,\{\phi\}\}</math>. סמן את הביטויים הנכונים: | נתון <math>A=\{\phi\}</math> ונתון <math>B=\{\phi,\{\phi\}\}</math>. סמן את הביטויים הנכונים: | ||
#<math>\phi\subseteq B</math> (כן) | #<math>\phi\subseteq B</math> (כן) | ||
שורה 52: | שורה 53: | ||
פתרון | פתרון | ||
− | נוכיח הכלה דו כיוונית. נניח <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</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>\{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> | ||
=== פעולות על קבוצות === | === פעולות על קבוצות === | ||
שורה 66: | שורה 69: | ||
*קבוצות הן שוות אם הן מכילות את אותם האיברים. הדרך הנפוצה להוכיח שיוויון הינה '''הכלה דו כיוונית''': A=B אם ורק אם <math>(A\subseteq B) \and (B \subseteq A) </math>. | *קבוצות הן שוות אם הן מכילות את אותם האיברים. הדרך הנפוצה להוכיח שיוויון הינה '''הכלה דו כיוונית''': A=B אם ורק אם <math>(A\subseteq B) \and (B \subseteq A) </math>. | ||
− | *A '''הפרש''' B הינה הקבוצה המכילה את כל האיברים בA שאינם בB (מסומן A\B). מתקיים ש <math>x\in A | + | *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) | + | *'''ההפרש הסימטרי''' בין שתי קבוצות 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> |
דוגמא: | דוגמא: | ||
שורה 82: | שורה 85: | ||
<math> B \cap C = \emptyset</math> | <math> B \cap C = \emptyset</math> | ||
− | <math>C \ | + | <math>C \smallsetminus A =\{\{1,2\}\}</math> |
<math> B \Delta C = B \cup C</math> | <math> B \Delta C = B \cup C</math> | ||
שורה 122: | שורה 125: | ||
ג. <math>\phi \cup A = \{x:x\in \phi \or x\in A\}= \{x:x\in A \}=A </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> | ||
+ | |||
+ | |||
===הכללה לאיחודים וחיתוכים כל שהם=== | ===הכללה לאיחודים וחיתוכים כל שהם=== | ||
שורה 163: | שורה 203: | ||
וגם <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> | וגם <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> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==== משלים ==== | ==== משלים ==== | ||
שורה 220: | שורה 221: | ||
* <math>(\cap _{i\in I} A_i)^c = \cup _{i\in I} A_{i}^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>(\cup _{i\in I} A_i)^c = \cap _{i\in I} A_{i}^c </math> | ||
+ | |||
+ | ===תרגיל=== | ||
+ | |||
+ | הוכיחו כי <math>A \triangle B = A^c \triangle B^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\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> | ||
===== תרגיל ===== | ===== תרגיל ===== | ||
שורה 227: | שורה 243: | ||
בכיוון שני: יהא <math>x\in B^c</math> אזי <math>x\notin B</math> לכן לפי נתון <math>x\notin A</math> לכן <math>x\in A^c</math>. | בכיוון שני: יהא <math>x\in B^c</math> אזי <math>x\notin B</math> לכן לפי נתון <math>x\notin A</math> לכן <math>x\in A^c</math>. | ||
+ | |||
+ | ===== תרגיל ===== | ||
+ | |||
+ | נגדיר <math>\forall n\in \mathbb{N}\cup \{0\} \; A_n:=(n,n+1) \cup (-n-1,-n)</math> אזי | ||
+ | |||
+ | א. <math>\bigcup _{n\in \mathbb{N}} A_n = \mathbb{R}\smallsetminus \mathbb{Z} </math> | ||
+ | |||
+ | ב. <math>\bigcap _{n\in \mathbb{N}} A_n = \varnothing </math> | ||
+ | |||
+ | ג. נגדיר <math>B_n=\mathbb{R}\smallsetminus A_n</math>. חשבו את <math>\bigcap_{n\in \mathbb{N}} B_n</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>. | ||
=== קבוצת החזקה === | === קבוצת החזקה === | ||
שורה 236: | שורה 270: | ||
האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה? | האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה? | ||
+ | |||
+ | ====תרגיל==== | ||
+ | הוכיחו או הפריכו: | ||
+ | |||
+ | א. לכל 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> | ||
===תרגיל ממבחן=== | ===תרגיל ממבחן=== | ||
שורה 257: | שורה 322: | ||
דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית <math>U:=B</math> ואז צריך להוכיח כי | דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית <math>U:=B</math> ואז צריך להוכיח כי | ||
− | <math>A\ | + | <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 \{\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 מוכל בחיתוך בסתירה לכך שהחיתוך ריק. |
גרסה אחרונה מ־14:35, 22 ביולי 2023
תוכן עניינים
קישורים
מידע רב חופף בין הקורס שלנו לקורס תורת הקבוצות, ניתן להעזר לכן בקורס תורת הקבוצות בויקיפדיה
קבוצות
ההגדרה האינטואיטיבית לקבוצה הינה "אוסף של איברים". ההגדרה הזו מובילה לסתירות לוגיות כגון "פרדוקס ראסל". נביט בקבוצה הבאה:
- X=אוסף כל הקבוצות שאינן שייכות לעצמן
אם X שייכת לקבוצה הזו, אזי היא אינה שייכת לקבוצה. אולם, אם היא אינה שייכת לקבוצה אזי היא כן שייכת לקבוצה.
סתירה אינה מקובלת במחוזות המתמטיקאים, ולכן הגדירו את "תורת הקבוצות האקסיומטית" העוקפת בעייה זו. ניתן לקרוא יותר על נושא זה בקישור לעיל, עבורנו מספיקה ההגדרה האינטואיטיבית.
אם כן, נחזור להגדרתנו הנאיבית; קבוצה הינה אוסף של איברים שונים. בקבוצה אין משמעות לסדר האיברים, ואיבר אינו יכול להופיע פעמיים. דוגמאות ל3 קבוצות:
,
ו
איבר השייך לקבוצה אנו מסמנים בסימן . למשל
, ואילו
. שימו לב שגם
שכן האיבר היחיד בקבוצה זו הינה הקבוצה
.
- אומרים שקבוצה A מוכלת בקבוצה B (מסומן
) אם כל האיברים בA הם גם איברים בB. בשפה מדויקת, A מוכלת בB אם מתקיים
.
- דוגמא:
כאשר
המספרים הטבעיים
המספרים השלמים
המספרים הרציונאלים (שברים)
המספרים הממשיים ("כל המספרים" על הישר)
המספרים המרוכבים
תרגיל (חשוב!)
מצאו קבוצות A,B כך ש:
תרגיל (חשוב)
נתון ונתון
. סמן את הביטויים הנכונים:
(כן)
(לא)
(כן)
(כן)
(כן)
(כן)
(לא)
תרגיל
נתונות , ו
. הוכח שA=B.
פתרון
נוכיח הכלה דו כיוונית. נניח לכן קיים מספר שלם m כך ש
. קל לראות שמתקיים
אבל אז מכיוון ש m-1 הינו מספר שלם מתקיים
כמו שרצינו.
ההכלה בכיוון ההפוך דומה.
תרגיל
הוכיחו כי
תרגיל
הוכיחו כי
פעולות על קבוצות
- חיתוך של שתי קבוצות A ו B הינו אוסף האיברים השייכים גם לA וגם לB (מסומן
). מתקיים ש
.
- איחוד של שתי קבוצות A ו B הינו אוסף האיברים השייכים לA או לB (מסומן
). מתקיים ש
.
- קבוצות הן שוות אם הן מכילות את אותם האיברים. הדרך הנפוצה להוכיח שיוויון הינה הכלה דו כיוונית: A=B אם ורק אם
.
- A הפרש B הינה הקבוצה המכילה את כל האיברים בA שאינם בB (מסומן A\B). מתקיים ש
.
- ההפרש הסימטרי בין שתי קבוצות A וB הוא אוסף האיברים הנמצאים באחת הקבוצות אך לא בחיתוך (מסומן
). מתקיים ש
דוגמא:
יהיו קבוצות.
אזי:
תכונות האיחוד והחיתוך (דומה לכפל וחיבור)
- אסוציאטיביות:
(וכנ"ל לגבי איחוד)
- חילוף:
(וכנ"ל לגבי איחוד)
- דיסטריביוטיביות:
, וגם
תרגיל
הוכח כי . במילים: האיברים שהם (גם בA וגם בB) או בC הם בדיוק האיברים ב(A או C) וגם ב(B או C)
פתרון
נראה שקילות בין התנאים של איבר להיות באחת הקבוצות.
כעת, מתוך הטאוטולוגיה קל להשיג את השקילות למה שצריך.
(הערה: ניתן להשתכנע בקלות בטאוטולוגיה באופן הבא: אם r=1 אזי נשאר עם הטאוטולוגיה
אם r=0 אזי נשאר עם הטאוטולוגיה
)
תרגיל
הוכח כי:
א. הקבוצה הריקה מוכלת בכל קבוצה A
ב.
ג.
פתרון
א. יש להוכיח את הפסוק הבא: . אבל מכיוון שאין איברים בקבוצה הריקה, המשפט הזה נכון באופן ריק. זכרו ששקר גורר כל דבר, לכן האטום "איבר a שייך לקבוצה הריקה" גורר כל דבר.
הערה: שימו לב שעל מנת להוכיח שקבוצה A אינה מוכלת בקבוצה B, יש להראות כי קיים איבר בA שאינו שייך לB. אם היינו משתמשים בפסוק "כל האיברים בA אינם בB" היינו מקבלים שהקבוצה הריקה לא מוכלת בכל קבוצה, וגם אינה מוכלת בכל קבוצה.
ב.
ג.
תרגיל
הוכח כי
פתרו:
דרך גרירות לוגיות:
בצד הימני הוספנו סתירה בעזרת הקשר "או" ולכן נשארנו עם ביטוי שקול. כעת נשתמש בחוק הפילוג של הלוגיקה:
וזה בדיוק מה שרצינו.
דרך הכלה דו כיוונית:
() נניח
אזי
() נניח
אזי
(כי אם
אזי
סתירה)
הכללה לאיחודים וחיתוכים כל שהם
מוטיבציה: הגדרנו את החיתוך והאיחוד עבור שתי קבוצות. לעיתים נרצה לחתוך או לאחד יותר קבוצות, לדוגמא נרצה לדבר על חיתוכן של 17 הקבוצות . מכיוון שחיתוך ואיחוד הן פעולות אסוציטיביות, ניתן לרשום
, וזה ביטוי חד משמעי. אך צורת רישום זו היא ארוכה, ולכן אנו מסמנים את החיתוך הזה בקיצור הבא:
. לעיתים נרצה לחתוך או לאחד אוסף אינסופי של קבוצות, ולכך באה ההכללה הבאה:
הגדרה:
יהיו אוסף קבוצות כאשר
הוא קבוצת אינדקסים אזי נגדיר את האיחוד והחיתוך של אוסף הקבוצות כך:
. כאן יש להניח שקבוצת האינדקסים
לא ריקה.
דוגמא:
נגדיר אזי
תרגיל
לכל n>1 טבעי נגדיר להיות קבוצת כל הראשוניים המחלקים את n.
חשבו את
תרגיל (הכללת פילוג)
יהיו אוסף קבוצות, B קבוצה. הוכיחו כי
פתרון:
יהא אזי
וגם
לכן
וגם
ולכן
ומכאן ש
בכיוון שני: יהא ולכן
לכן
וגם
לכן
וגם
ולכן
משלים
הגדרה: תהי קבוצה U, ונביט בתת קבוצה שלה A. ניתן להגדיר את המשלים של A כאוסף האיברים בU שאינם בA (כלומר ההפרש ), מסומן
. לא ניתן לדבר על משלים אוניברסאלי ללא U מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).
תכונות בסיסיות:
על המשלימים מתקיימים חוקי דה מורגן (הנובעים ישירות מחוקי דה מורגן בלוגיקה):
הערה: באופן כללי מתקיים
תרגיל
הוכיחו כי .
פתרון:
נשתמש בהצגת ההפרש הסימטרי כאיחוד ההפרשים:
ומחילופיות "וגם" ו"או":
תרגיל
יהיו A,B ת"ק של U אזי
פתרון: בכיוון אחד- יהא אזי
לכן לפי נתון
לכן
.
בכיוון שני: יהא אזי
לכן לפי נתון
לכן
.
תרגיל
נגדיר אזי
א.
ב.
ג. נגדיר . חשבו את
הוכחה:
א. ע"י הכלה דו כיוונית.
ב. מספיק להראות .
ג. נתייחס ל- כקבוצה האוניברסלית לדיוננו. לפי דה-מורגן נקבל:
.
קבוצת החזקה
הגדרה: תהי קבוצה A. נגדיר את קבוצת החזקה של A בתור אוסף כל תתי הקבוצות של A. מסומן
דוגמא:
אזי
.
האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה?
תרגיל
הוכיחו או הפריכו:
א. לכל A,B מתקיים:
ב. לכל A,B מתקיים:
ג. קיימת A כך ש
ד. קיימת A סופית כך ש . לגבי אינסופית תראו בבעתיד.
פתרון:
א. הוכחה:
ב. הפרכה: ניקח . אז
, אבל לא ל-
.
למעשה הוכיחו כי אם ורק אם
או
.
ג. ייתכן, למשל
ד. לא, כי אז שלא ייתכן משיקולי עוצמה (בקבוצה סופית: ב
יש יותר איברים מ Aׂׂ)
תרגיל
הוכיחו כי אם אז
או
תרגיל
תהא . הוכיחו כי
תרגיל ממבחן
יהיו A,B,C קבוצות. הוכיחו/הפריכו:
א. אם אזי
ב. אם אזי
ג. אם אזי
פתרון
א. הפרכה: . אזי ברור שA איננה מוכלת בחיתוך של B וC אבל
ב. נתון שלכל מתקיים
. אזי
כעת, הצד הימני הוא טאוטולוגיה וניתן להסיר אותו. מכיוון שנתון ניתן להסיק בקלות ש
כפי שרצינו.
דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית ואז צריך להוכיח כי
וזה אכן נכון!
ג. נניח בשלילה ש. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה
השייכת לחיתוך
. קבוצות החזקה הן אוסף תתי הקבוצות, ולכן
. מכיוון שC אינה ריקה קיים בה איבר
וקל מאד לראות ש
ולכן c מוכל בחיתוך בסתירה לכך שהחיתוך ריק.