פרק 1: תורת הקבוצות

קבוצה היא אוסף של אובייקטים הנקראים איברים. נסמן $x \in A$ אם $x$ איבר ב-$A$.

$A \subseteq B$ אם לכל $x \in A$ מתקיים $x \in B$.

$A = B$ אם $A \subseteq B$ וגם $B \subseteq A$.

• איחוד: $A \cup B = \{x : x \in A \text{ או } x \in B\}$
• חיתוך: $A \cap B = \{x : x \in A \text{ וגם } x \in B\}$
• הפרש: $A \setminus B = \{x : x \in A \text{ וגם } x \notin B\}$
• משלים: $A^c = U \setminus A$ (כאשר $U$ הקבוצה האוניברסלית)

פונקציה $f : A \to B$ היא התאמה שלכל $a \in A$ מתאימה איבר יחיד $f(a) \in B$.

• $A$ נקרא תחום ההגדרה
• $B$ נקרא הטווח

פונקציה $f : A \to B$ נקראת:

• חד-חד-ערכית (חח"ע): $f(x_1) = f(x_2) \Rightarrow x_1 = x_2$
• על: לכל $b \in B$ קיים $a \in A$ כך ש-$f(a) = b$
• הפיכה: אם היא חח"ע ועל

שתי קבוצות $A, B$ הן שוות עוצמה אם קיימת פונקציה חח"ע ועל $f : A \to B$.

• קבוצה בת-מנייה אם היא שווה עוצמה ל-$\mathbb{N}$
• קבוצה ניתנת לספירה אם היא סופית או בת-מנייה