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

איחוד קבוצות

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

הגדרה 1.3: איחוד קבוצות תהיינה $A,B$ קבוצות. לכל אבר $x$ מתקיים: $x\in A\cup B$ אם ורק אם $x\in A$ או $x\in B$ . $A\cup B={\Big \{}x:x\in A\lor x\in B{\Big \}}$ במלים אחרות: האיחוד שלהם הוא הקבוצה המכילה את כל אברי $A$ ואת כל אברי $B$ , ורק אותם.

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

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

משפט 15: תהיינה $A,B$ קבוצות המקיימות $A\subseteq B$ . מתקיים: $A\cup B=B$ . הוכחה על-מנת להוכיח שוויון בין קבוצות, עלינו להראות הכלה משני הכיוונים, כלומר $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.6: לכל קבוצה $A$ מתקיים: $A\cup A=A\cup \varnothing =A$ . הוכחה ממשפט 1.3 מתקיים $\varnothing \subseteq A$ , ולכן לפי משפט 1.4 מתקיים $A\cup \varnothing =A$ . ממשפט 1.1 מתקיים $A\subseteq A$ , ולכן שוב לפי משפט 1.4 מתקיים $A\cup A=A$ .

הגדרה 1.4: המספרים הטבעיים נגדיר את המספרים הטבעיים באופן הבא: $0=\varnothing$ $n+1=n\cup \{n\}$ כלומר, 0 מוגדר בתור הקבוצה הריקה, וכל מספר טבעי מוגדר באמצעות קבוצת הטבעיים הקטנים ממנו.

איחוד מורחב

כפי שהגדרנו איחוד של שתי קבוצות, נוכל גם להגדיר איחוד של שלוש קבוצות:

$A\cup B\cup C=(A\cup B)\cup C={\Big \{}x:x\in A\lor x\in B\lor x\in C{\Big \}}$

באופן זה ניתן להרחיב את ההגדרה גם לאיחוד של 4 קבוצות, 5 קבוצות וכן הלאה.

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

$\bigcup _{A\in {\mathfrak {F}}}A={\Big \{}x:\exists A\in {\mathfrak {F}}:x\in A{\Big \}}$

חיתוך קבוצות

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

הגדרה 1.5: חיתוך קבוצות תהיינה $A,B$ קבוצות. לכל אבר $x$ מתקיים: $x\in A\cap B$ אם ורק אם $x\in A$ וגם $x\in B$ . $A\cap B={\Big \{}x:x\in A\land x\in B{\Big \}}$ במלים אחרות: החיתוך שלהם הוא הקבוצה המכילה את כל האברים המשותפים גם ל־$A$ וגם ל־$B$ , ורק אותם.

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

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

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

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

חיתוך מורחב

כפי שהגדרנו חיתוך של שתי קבוצות, נוכל גם להגדיר חיתוך של שלוש קבוצות:

$A\cap B\cap C=(A\cap B)\cap C={\Big \{}x{\Big |}x\in A\land x\in B\land x\in C{\Big \}}$

באופן זה ניתן להרחיב את ההגדרה גם לחיתוך של 4 קבוצות, 5 קבוצות וכן הלאה.

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

$\bigcap _{A\in {\mathfrak {F}}}A=\{x|\forall A\in {\mathfrak {F}}:x\in A\}$

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

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

הגדרה 1.6: הפרש בין קבוצות תהיינה $A,B$ קבוצות. לכל אבר $x$ מתקיים: $x\in A\setminus B$ אם ורק אם $x\in A$ אך $x\notin B$ . $A\setminus B={\Big \{}x\in A:x\notin B{\Big \}}=A\cap {\overline {B}}$ במלים אחרות: ההפרש שלהם הוא הקבוצה המכילה את אברי $A$ שאינם שייכים ל־$B$ , ורק אותם.

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

הפרש סימטרי

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

הגדרה 1.7: הפרש סימטרי תהיינה $A,B$ קבוצות. לכל אבר $x$ מתקיים: $x\in A\Delta B$ אם ורק אם $x\notin A\cap B$ . $A\Delta B=(A\setminus B)\cup (B\setminus A)=(A\cup B)\setminus (A\cap B)$ במלים אחרות: ההפרש הסימטרי שלהם הוא הקבוצה המכילה את כל האברים שאינם שייכים לחיתוך שלהם, ורק אותם.

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

• קומוטאטיביות $A\Delta B=B\Delta A$
• אסוציאטיביות $(A\Delta B)\Delta C=A\Delta (B\Delta C)$

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

כללי דה־מורגן

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

$${\begin{aligned}(A\cap B)^{c}&=A^{c}\cup B^{c}\\(A\cup B)^{c}&=A^{c}\cap B^{c}\end{aligned}}$$

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

כעת נדגים הוכחה בתורת הקבוצות, ובד בבד, גם נוכיח את הכללים החשובים של דה־מורגן.

הוכחה

נפתח בחוק הראשון.

$${\begin{aligned}x\in (A\cap B)^{c}&\iff x\notin A\cap B\\&\iff \neg (x\in A\cap B)\\&\iff \neg (x\in A\land x\in B)\\&\iff (x\notin A)\lor (x\notin B)\\&\iff (x\in A^{c})\lor (x\in B^{c})\\&\iff x\in A^{c}\cup B^{c}\end{aligned}}$$

בצורה דומה מוכח גם המשפט השני.

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

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

$${\begin{aligned}\left(\bigcap _{A\in {\mathfrak {F}}}A\right)^{c}&=\bigcup _{A\in {\mathfrak {F}}}A^{c}\\\left(\bigcup _{A\in {\mathfrak {F}}}A\right)^{c}&=\bigcap _{A\in {\mathfrak {F}}}{\bar {A}}\end{aligned}}$$

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

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

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

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