מתמטיקה בדידה: תורת הקבוצות, קומבינטוריקה ותורת הגרפים

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

מהי קבוצה?

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

קבוצה (Set): אוסף מוגדר היטב של אובייקטים מובחנים.

איבר (Element/Member): אובייקט השייך לקבוצה. הסימון $x \in A$ מציין ש-$x$ הוא איבר בקבוצה $A$.

דרכים להצגת קבוצות

רישום מפורש (Roster Method): רשימת כל האיברים בסוגריים מסולסלים, למשל $A = \{1, 2, 3\}$.
הגדרה באמצעות תכונה (Set-Builder Notation): תיאור תכונה המאפיינת את כל איברי הקבוצה, למשל $B = \{x \mid x \text{ הוא מספר שלם זוגי}\}$.

שוויון קבוצות

שתי קבוצות $A$ ו-$B$ שוות אם ורק אם הן מכילות בדיוק את אותם איברים. כלומר, $A = B$ אם לכל איבר $x$, מתקיים $x \in A \iff x \in B$.

יחסים בין קבוצות

הבנת היחסים בין קבוצות חיונית לניתוח מבנים קבוצתיים ולביצוע הוכחות.

תת-קבוצה (Subset): קבוצה $A$ היא תת-קבוצה של קבוצה $B$ (מסומן $A \subseteq B$) אם כל איבר של $A$ הוא גם איבר של $B$. פורמלית: $\forall x (x \in A \implies x \in B)$.

תת-קבוצה ממש (Proper Subset): קבוצה $A$ היא תת-קבוצה ממש של קבוצה $B$ (מסומן $A \subset B$) אם $A \subseteq B$ וגם $A \ne B$. כלומר, $B$ מכילה לפחות איבר אחד שאינו ב-$A$.

קבוצה ריקה (Empty Set): הקבוצה היחידה שאינה מכילה אף איבר. מסומנת $\emptyset$ או $\{\}$. הקבוצה הריקה היא תת-קבוצה של כל קבוצה.

עוצמה (Cardinality): מספר האיברים בקבוצה סופית $A$, מסומן $|A|$.

קבוצת החזקה (Power Set): קבוצת כל תת-הקבוצות של קבוצה נתונה $A$, מסומנת $\mathcal{P}(A)$ או $2^A$. אם $|A|=n$, אז $|\mathcal{P}(A)| = 2^n$.

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

פעולות אלו מאפשרות לנו לבנות קבוצות חדשות מקבוצות קיימות.

איחוד (Union)

הקבוצה המכילה את כל האיברים הנמצאים ב-$A$ או ב-$B$ (או בשניהם). מסומן $A \cup B = \{x \mid x \in A \text{ או } x \in B\}$.

חיתוך (Intersection)

הקבוצה המכילה את כל האיברים הנמצאים גם ב-$A$ וגם ב-$B$. מסומן $A \cap B = \{x \mid x \in A \text{ וגם } x \in B\}$.

הפרש (Difference)

הקבוצה המכילה את כל האיברים הנמצאים ב-$A$ אך לא ב-$B$. מסומן $A \setminus B = \{x \mid x \in A \text{ וגם } x \notin B\}$.

משלים (Complement)

בהינתן קבוצה אוניברסלית $U$, המשלים של $A$ הוא קבוצת כל האיברים ב-$U$ שאינם ב-$A$. מסומן $A^c$ או $\bar{A} = \{x \mid x \in U \text{ וגם } x \notin A\}$.

מכפלה קרטזית (Cartesian Product): קבוצת כל הזוגות הסדורים $(a, b)$ כאשר $a \in A$ ו-$b \in B$. מסומנת $A \times B = \{(a, b) \mid a \in A \text{ וגם } b \in B\}$. אם $|A|=m$ ו-$|B|=n$, אז $|A \times B| = mn$.

הוכחות וטעויות נפוצות

בטכניון, היכולת להוכיח טענות על קבוצות היא מיומנות יסוד. הוכחות אלו מתבצעות לרוב בשיטת "הוכחה איבר-איבר" (element-wise proof).

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

דוגמה להוכחה איבר-איבר:

נוכיח את חוק דה-מורגן: $(A \cup B)^c = A^c \cap B^c$.

הוכחה ש-$(A \cup B)^c \subseteq A^c \cap B^c$:
- יהי $x \in (A \cup B)^c$.
- לפי הגדרת משלים, $x \notin (A \cup B)$.
- לפי הגדרת איחוד, $x \notin A$ וגם $x \notin B$.
- לפי הגדרת משלים, $x \in A^c$ וגם $x \in B^c$.
- לפי הגדרת חיתוך, $x \in A^c \cap B^c$.
הוכחה ש-$A^c \cap B^c \subseteq (A \cup B)^c$:
- יהי $x \in A^c \cap B^c$.
- לפי הגדרת חיתוך, $x \in A^c$ וגם $x \in B^c$.
- לפי הגדרת משלים, $x \notin A$ וגם $x \notin B$.
- לכן, $x$ אינו נמצא לא ב-$A$ ולא ב-$B$.
- לפי הגדרת איחוד, $x \notin (A \cup B)$.
- לפי הגדרת משלים, $x \in (A \cup B)^c$.

מכיוון שהוכחנו את שני הכיוונים, נובע ש-$(A \cup B)^c = A^c \cap B^c$.

שאלות לדיון

כיצד נבחין בין תת-קבוצה לבין איבר בקבוצה, ומדוע הבחנה זו קריטית בהוכחות?
בהינתן קבוצה $A = \{1, \{2,3\}, 4\}$, מהי עוצמתה? רשמו את קבוצת החזקה שלה.
הסבירו את ההבדל בין $A \setminus B$ לבין $A^c$ והדגימו באמצעות דוגמה מספרית.
הוכיחו או הפריכו: לכל קבוצות $A, B, C$, אם $A \subseteq B$ וגם $B \subseteq C$, אז $A \subseteq C$.

נקודות לתשובת מודל

הבחנה בין תת-קבוצה לאיבר: איבר הוא אובייקט בתוך הקבוצה (מסומן $\in$), בעוד שתת-קבוצה היא קבוצה שכל איבריה נמצאים בקבוצה אחרת (מסומן $\subseteq$). לדוגמה, $1 \in \{1,2\}$ אך $\{1\} \subseteq \{1,2\}$. הבחנה זו קריטית למניעת טעויות לוגיות בהוכחות.
עוצמה וקבוצת חזקה:
- עוצמת הקבוצה $A = \{1, \{2,3\}, 4\}$ היא 3, שכן יש לה שלושה איברים מובחנים: 1, הקבוצה $\{2,3\}$, והמספר 4.
- קבוצת החזקה $\mathcal{P}(A)$ תכיל $2^3 = 8$ תת-קבוצות: $\emptyset$, $\{1\}$, $\{\{2,3\}\}$, $\{4\}$, $\{1, \{2,3\}\}$, $\{1, 4\}$, $\{\{2,3\}, 4\}$, $\{1, \{2,3\}, 4\}$.
הבדל בין $A \setminus B$ ל-$A^c$:
- $A \setminus B$ (הפרש) כולל את האיברים שנמצאים ב-$A$ אך לא ב-$B$. זוהי פעולה יחסית בין שתי קבוצות ספציפיות.
- $A^c$ (משלים) כולל את כל האיברים שאינם ב-$A$ מתוך קבוצה אוניברסלית $U$ מוגדרת מראש. זוהי פעולה יחסית לקבוצה אוניברסלית.
- דוגמה: אם $U = \{1,2,3,4,5\}$, $A = \{1,2,3\}$, $B = \{2,4\}$. אז $A \setminus B = \{1,3\}$. ואילו $A^c = \{4,5\}$.
הוכחה של טרנזיטיביות יחס ההכלה:
- נניח ש-$A \subseteq B$ וגם $B \subseteq C$.
- צריך להוכיח ש-$A \subseteq C$.
- יהי $x \in A$.
- מכיוון ש-$A \subseteq B$, לפי הגדרת תת-קבוצה, נובע ש-$x \in B$.
- מכיוון ש-$B \subseteq C$, ולפי מה שהוכחנו $x \in B$, נובע ש-$x \in C$.
- לכן, אם $x \in A$ אז $x \in C$, ומכאן ש-$A \subseteq C$. הטענה נכונה.

מצאתם טעות או שחסר משהו?