תורת הקבוצות — יסודות

שבוע 1 | מתמטיקה דיסקרטית — HUJI | ספר: ליניאל ופרנס

מהי קבוצה?

קבוצה היא אוסף של אובייקטים (שנקראים איברים). סימון: אותיות גדולות ( $A, B, C$ ).

$a \in A$ — " $a$ שייך ל- $A$ "
$a \notin A$ — " $a$ לא שייך ל- $A$ "

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

צורה	דוגמה
רשימה	$A = \{1, 2, 3\}$
תנאי	$B = \{x \in \mathbb{N} \mid x > 5\}$

שים לב

הסדר לא חשוב: $\{1,2,3\} = \{3,1,2\}$ . גם כפילויות לא משנות: $\{1,1,2\} = \{1,2\}$ .

הכלה (Subset)

$A \subseteq B$ אם כל איבר של $A$ נמצא גם ב- $B$ .

$A \subseteq B \iff \forall a \in A: a \in B$

$A = B$ אמ"מ $A \subseteq B$ וגם $B \subseteq A$
הקבוצה הריקה $\emptyset$ מוכלת בכל קבוצה: $\emptyset \subseteq A$

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

פעולה	סימון	הגדרה
איחוד	$A \cup B$	$\{x \mid x \in A \text{ או } x \in B\}$
חיתוך	$A \cap B$	$\{x \mid x \in A \text{ וגם } x \in B\}$
הפרש	$A \setminus B$	$\{x \mid x \in A \text{ ו-} x \notin B\}$
משלים	$\overline{A}$	$U \setminus A$ (כש- $U$ = קבוצה אוניברסלית)
מכפלה קרטזית	$A \times B$	$\{(a,b) \mid a \in A, b \in B\}$

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

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

טריק להוכחה

כדי להוכיח שוויון קבוצות $X = Y$ , מוכיחים הכלה דו-כיוונית: $X \subseteq Y$ וגם $Y \subseteq X$ .

דיאגרמות ון

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

מלכודת נפוצה

$A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$ — נראה מפתיע? ציירו ון ותראו שזה עובד!

קבוצת החזקה

קבוצת החזקה $\mathcal{P}(A)$ היא קבוצת כל תתי-הקבוצות של $A$ .

אם $|A| = n$ אז $|\mathcal{P}(A)| = 2^n$
$\emptyset \in \mathcal{P}(A)$ תמיד
$A \in \mathcal{P}(A)$ תמיד

דוגמה: $A = \{1,2\}$ אז $\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}$

תורת הקבוצות — יסודות

שבוע 1 | מתמטיקה דיסקרטית — HUJI | ספר: ליניאל ופרנס

מהי קבוצה?

קבוצה היא אוסף של אובייקטים (שנקראים איברים). סימון: אותיות גדולות ( $A, B, C$ ).

$a \in A$ — " $a$ שייך ל- $A$ "
$a \notin A$ — " $a$ לא שייך ל- $A$ "

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

צורה	דוגמה
רשימה	$A = \{1, 2, 3\}$
תנאי	$B = \{x \in \mathbb{N} \mid x > 5\}$

שים לב

הסדר לא חשוב: $\{1,2,3\} = \{3,1,2\}$ . גם כפילויות לא משנות: $\{1,1,2\} = \{1,2\}$ .

הכלה (Subset)

$A \subseteq B$ אם כל איבר של $A$ נמצא גם ב- $B$ .

$A \subseteq B \iff \forall a \in A: a \in B$

$A = B$ אמ"מ $A \subseteq B$ וגם $B \subseteq A$
הקבוצה הריקה $\emptyset$ מוכלת בכל קבוצה: $\emptyset \subseteq A$

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

פעולה	סימון	הגדרה
איחוד	$A \cup B$	$\{x \mid x \in A \text{ או } x \in B\}$
חיתוך	$A \cap B$	$\{x \mid x \in A \text{ וגם } x \in B\}$
הפרש	$A \setminus B$	$\{x \mid x \in A \text{ ו-} x \notin B\}$
משלים	$\overline{A}$	$U \setminus A$ (כש- $U$ = קבוצה אוניברסלית)
מכפלה קרטזית	$A \times B$	$\{(a,b) \mid a \in A, b \in B\}$

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

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

טריק להוכחה

כדי להוכיח שוויון קבוצות $X = Y$ , מוכיחים הכלה דו-כיוונית: $X \subseteq Y$ וגם $Y \subseteq X$ .

דיאגרמות ון

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

מלכודת נפוצה

$A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$ — נראה מפתיע? ציירו ון ותראו שזה עובד!

קבוצת החזקה

קבוצת החזקה $\mathcal{P}(A)$ היא קבוצת כל תתי-הקבוצות של $A$ .

אם $|A| = n$ אז $|\mathcal{P}(A)| = 2^n$
$\emptyset \in \mathcal{P}(A)$ תמיד
$A \in \mathcal{P}(A)$ תמיד

דוגמה: $A = \{1,2\}$ אז $\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}$