תורת הקבוצות/פעולות על קבוצות

איחוד קבוצות

דיאגרמת ון של האיחוד של A ו-B

תהיינה A,B קבוצות כלשהן. האיחוד של A ו-B הוא הקבוצה המכילה את כל איברי A ואת כל איברי B, ורק אותם. קבוצה זו מסומנת $A\cup B$. באופן פורמלי נגדיר:

הגדרה 1.5: תהיינה A,B קבוצות כלשהן. לכל איבר x, מתקיים: $x\in A\cup B$ אם ורק אם $x\in A$ או $x\in B$. בניסוח מתמטי: $A\cup B = \{x|x\in A \vee x\in B\}$.

מעצם ההגדרה, ברור כי אין חשיבות לסדר הקבוצות. כלומר, $A\cup B = B\cup A$.

משפט 1.3: תהיינה A,B קבוצות כלשהן. מתקיים: $A\subseteq A\cup B$ וגם $B\subseteq A\cup B$.

הוכחה 1.3: נחזור להגדרה של הכלה (הגדרה 1.1). עלינו להראות שלכל x, אם $x\in A$ אז $x\in A\cup B$. אך טענה זו נובעת ישירות מההגדרה של איחוד, ולכן $A\subseteq A\cup B$. ההוכחה עבור B זהה.

משפט 1.4: תהיינה A,B קבוצות כלשהן, המקיימות $A\subseteq B$. מתקיים: $A \cup B = B$.

הוכחה 1.4: על מנת להוכיח שוויון בין קבוצות, עלינו להראות הכלה משני הכיוונים, כלומר $B\subseteq A\cup B$ וגם $A\cup B\subseteq B$. הכיוון הראשון נובע ממשפט 1.3. על מנת להוכיח את הכיוון השני, יהי איבר x המקיים $x\in A\cup B$. לפי הגדרת האיחוד (הגדרה 1.5), מתקיים $x\in A$ או $x\in B$. כיוון ש-$A\subseteq B$, אם $x\in A$ אז $x\in B$, ולכן בשני המקרים $x\in B$. לכן $A\cup B\subseteq B$.

מסקנה 1.5: לכל קבוצה A, מתקיים: $A\cup A = A\cup \emptyset = A$.

הוכחה 1.5: ממשפט 1.2 מתקיים $\emptyset \subseteq A$, ולכן לפי משפט 1.4 מתקיים $A\cup \emptyset = A$. ממשפט 1.1 מתקיים $A\subseteq A$, ולכן שוב לפי משפט 1.4 מתקיים $A\cup A = A$.

איחוד מורחב

כפי שהגדרנו איחוד של שתי קבוצות, נוכל גם להגדיר איחוד של שלוש קבוצות: $A\cup B\cup C = (A\cup B) \cup C = \{x|x\in A \vee x\in B\vee x\in C\}$. באופן זה ניתן להרחיב את ההגדרה גם לאיחוד של 4 קבוצות, 5 קבוצות וכן הלאה.

בהינתן אוסף של קבוצות $\mathfrak{F}$, נגדיר את האיחוד של הקבוצות כקבוצת האיברים שמופיעים באחת מהקבוצות. כלומר: $\bigcup_{A \in \mathfrak{F}} A = \{x : \exists A\in\mathfrak{F}: x\in A\}$.

חיתוך קבוצות

דיאגרמת ון של החיתוך של A ו-B

תהיינה A,B קבוצות כלשהן. החיתוך של A ו-B הוא הקבוצה המכילה את כל האיברים שמוכלים גם ב-A וגם ב-B, ורק אותם. קבוצה זו מסומנת $A\cap B$. באופן פורמלי נגדיר:

הגדרה 1.6: תהיינה A,B קבוצות כלשהן. לכל איבר x, מתקיים: $x\in A\cap B$ אם ורק אם $x\in A$ וגם $x\in B$. בניסוח מתמטי: $A\cap B = \{x|x\in A \wedge x\in B\}$.

מעצם ההגדרה, ברור כי אין חשיבות לסדר הקבוצות. כלומר, $A\cap B = B\cap A$.

משפט 1.6: תהיינה A,B קבוצות כלשהן. מתקיים: $A\cap B\subseteq A$ וגם $A\cap B\subseteq B$.

הוכחה 1.6: נחזור להגדרה של הכלה (הגדרה 1.1). עלינו להראות שלכל x, אם $x\in A\cap B$ אז $x\in A$. טענה זו נובעת ישירות מההגדרה של חיתוך, ולכן $A\cap B\subseteq A$. ההוכחה עבור B זהה.

משפט 1.7: תהיינה A,B קבוצות כלשהן, המקיימות $A\subseteq B$. מתקיים: $A \cup B = A$.

הוכחה 1.7: על מנת להוכיח שוויון בין קבוצות, עלינו להראות הכלה משני הכיוונים, כלומר $A\subseteq A\cap B$ וגם $A\cap B\subseteq A$. הכיוון השני נובע ממשפט 1.6. על מנת להוכיח את הכיוון הראשון, יהי איבר $x\in A$. כיוון ש-$A\subseteq B$, מתקיים $x\in B$, ולכן לפי הגדרת האיחוד $x\in A\cap B$.

מסקנה 1.8: לכל קבוצה A, מתקיים: $A\cap \emptyset = \emptyset, A\cap A = A$.

הוכחה 1.8: ממשפט 1.2 מתקיים $\emptyset \subseteq A$, ולכן לפי משפט 1.7 מתקיים $A\cap \emptyset = \emptyset$. ממשפט 1.1 מתקיים $A\subseteq A$, ולכן שוב לפי משפט 1.7 מתקיים $A\cap A = A$.

חיתוך מורחב

כפי שהגדרנו חיתוך של שתי קבוצות, נוכל גם להגדיר חיתוך של שלוש קבוצות: $A\cap B\cap C = (A\cap B) \cap C = \{x|x\in A \wedge x\in B\wedge x\in C\}$. באופן זה ניתן להרחיב את ההגדרה גם לחיתוך של 4 קבוצות, 5 קבוצות וכן הלאה.

בהינתן אוסף של קבוצות $\mathfrak{F}$, נגדיר את החיתוך של הקבוצות כקבוצת האיברים שמופיעים בכל אחת מהקבוצות. כלומר: $\bigcup_{A \in \mathfrak{F}} A = \{x : \forall A\in\mathfrak{F}: x\in A\}$.

הפרש בין קבוצות

דיאגרמת ון של ההפרש בין שתי קבוצות

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

$\ A\setminus B =\left\{ x\in A\vert x\notin B\right\} = A\cap \overline{B}$

הערה: למרות שנהוג היום יותר להשתמש ב$\setminus$, עדיין נהוג לעיתים בספרות ובמאמרים מסוימים בויקיפדיה השימוש בסימן - בשביל ההפרש בין קבוצות.

הפרש סימטרי

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

$\ A\Delta B=\left( A\setminus B\right) \cup \left( B\setminus A\right)$

דיאגרמת ון של ההפרש הסימטרי של A ו-B

תכונות מעניינות שמקיים ההפרש הסימטרי:

• הפעולה היא פעולה קומוטטיבית, כלומר: $\ A \Delta B = B \Delta A$
• זוהי פעולה אסוציאטיבית, כלומר: $\ (A \Delta B)\Delta C = A \Delta (B \Delta C)$

הוכחת העובדות האלה ניתנת כתרגיל לקורא.

כללי דה מורגן

חוקי דה-מורגן הינם חוקים אשר מטרתם ל"הפוך" חיתוך באיחוד. זה נעשה על ידי שימוש במשלים. חוקי דה-מורגן קובעים שלכל שתי קבוצות $\;A$ ו-$\;B$ מתקיים:

$\overline{A\cap {B}}=\overline{A}\cup\overline{B}$
$\overline{A\cup {B}}=\overline{A}\cap\overline{B}$

הוכחת חוקי דה-מורגן

כעת נדגים הוכחה בתורת הקבוצות, ובד בבד, גם נוכיח את הכללים החשובים של דה-מורגן.
הוכחה: נתחיל בחוק הראשון. נבחר אבר כלשהו, $x\in \overline{A\cap{B}}$ (כלומר איבר במשלים של קבוצת החיתוך). לפי ההגדרה, $\;x$ אינו בד-בבד ב-$\;A$ וב-$\;B$ (כי הוא במשלים) אז יש רק 3 אופציות.

1. יתכן ש-$\;x\in {A}$ וגם $\;x\not\in {B}$.
2. יתכן ש-$\;x\in {B}$ וגם $\;x\not\in {A}$.
3. יתכן ש-$\;x\not\in {A}$ וגם $\;x\not\in {B}$.

מתוך 1 נובע ש-$\;x \in \overline{B}$ ולכן בפרט גם באיחוד $\overline{A}\cup{\overline{B}}$.
מתוך 2 נובע ש-$\;x\in {\overline{A}}$ ולכן בפרט גם באיחוד $\overline{A}\cup{\overline{B}}$.
מתוך 3 ברור ש -$x\in\overline{A}\cup{\overline{B}}$ ממש מתוך ההגדרה.
מה שקיבלנו זה ש-$\overline{A \cap{B}}\subseteq{\overline{A}\cup\overline{B}}$. לא נותר אלא להראות את ההכלה בכיוון השני.
נבחר אבר כלשהו, $x\in \overline{A}\cup\overline{B}$. לפי ההגדרה, $x\in \overline{A}$ או $x\in \overline{B}$ (או שניהם) ולכן יש 3 אופציות:

1. יתכן ש-$\;x\in \overline{A}$.
2. יתכן ש-$\;x\in \overline{B}$.
3. יתכן ש-1 וגם 2 מתקיימים בו-זמנית.

אם מתקיים 1, אז בהכרח $\;x\not\in A$ מכאן בפרט, $\;x\not\in A\cap{B}$ (למה?). לכן ברור ש-$x\in \overline{A\cap{B}}$. באופן סימטרי גם עבור 2 ו-3 $x\in \overline{A\cap{B}}$ מאותם שיקולים. הראנו הכלה בכיוון ההפוך כלומר, $\overline{A\cap{B}}\supseteq{\overline{A}\cup{\overline{B}}}$ ולכן לפי ההגדרה גם $\overline{A\cap{B}}=\overline{A}\cup{\overline{B}}$ כנדרש.

כללי דה-מורגן המוכללים

בהינתן אוסף של קבוצות $\mathfrak{F}$, מתקיים:

$\overline{\bigcap_{A\in \mathfrak{F} } A} = \bigcup_{A\in \mathfrak{F}} \overline{A}$

$\overline{\bigcup_{A\in \mathfrak{F} } A} = \bigcap_{A\in \mathfrak{F}} \overline{A}$

ההוכחה כמעט זהה לחלוטין להוכחה של חוקי דה-מורגן, ועל כן, היא מושארת כתרגיל לקורא.

הפרק הקודם: יחסים בין קבוצות

פעולות על קבוצות

הפרק הבא: מכפלה קרטזית