יחידה 12: משפט קש"ב, פעולות עוצמות¶

משפט קנטור-שרדר-ברנשטיין¶

הגדרות¶

הגדרה: סדר על עוצמות

אם קיימת פונקציה חח"ע $f \in A \to B$ אז נאמר ש-$|A| \leq |B|$.

הגדרה: סדר חזק

נסמן $|A| < |B|$ אם מתקיים $|A| \leq |B|$ וגם לא מתקיים $|A| = |B|$.

המשפט¶

משפט קנטור-שרדר-ברנשטיין (קש\"ב)

אם $|A| \leq |B|$ וגם $|B| \leq |A|$ אזי $|A| = |B|$.

במילים: אם קיימת פונקציה חח"ע מ-$A$ ל-$B$ וגם קיימת פונקציה חח"ע מ-$B$ ל-$A$, אז קיים זיווג בין $A$ ל-$B$.

טכניקת סנדוויץ'

נרצה להוכיח ש-$|X| = a$. נמצא קבוצות $Y, Z$ עבורן קל להוכיח ש-$|Y| = |Z| = a$, נוכיח שמתקיים $|Y| \leq |X| \leq |Z|$ ונקבל ש-$|X| = a$.

קשר בין חח"ע לעל¶

טענה

נניח $A \neq \emptyset, B$ קבוצות. אזי:

קיימת פונקציה חח"ע $f \in A \to B$ אם ורק אם קיימת פונקציה $g \in B \to A$ על.

דוגמאות לשימוש בקש"ב¶

דוגמה 1: קטעים¶

הוכחה: $|[0,1)| = |[0,1]|$

צריך להוכיח: $|[0,1)| \leq |[0,1]|$ וגם $|[0,1]| \leq |[0,1)|$.

$|[0,1)| \leq |[0,1]|$: הפונקציה $f_1 = \lambda x \in [0,1). x$ היא חח"ע מ-$[0,1)$ ל-$[0,1]$.

$|[0,1]| \leq |[0,1)|$: הפונקציה $f_2 = \lambda x \in [0,1]. \frac{x}{2}$ היא חח"ע מ-$[0,1]$ ל-$[0,1)$.

מקש"ב: $|[0,1)| = |[0,1]|$. ∎

הערה

באופן דומה ניתן להראות שכל קטע הוא מעוצמה $\aleph$: $$|[a,b]| = |[a,b)| = |(a,b]| = |(a,b)| = \aleph$$

דוגמה 2: יחסים רפלקסיביים¶

מצאו את עוצמת היחסים הרפלקסיביים ב-$\mathbb{R}$

נסמן קבוצה זו ב-$A$.

חסם עליון: $A \subseteq \mathcal{P}(\mathbb{R} \times \mathbb{R})$ ולכן: $$|A| \leq |\mathcal{P}(\mathbb{R} \times \mathbb{R})| = 2^{|\mathbb{R} \times \mathbb{R}|} = 2^{\aleph \cdot \aleph} = 2^{\aleph}$$

חסם תחתון: נגדיר $f \in \mathcal{P}([0,1]) \to A$ ע"י: $$f = \lambda X \in \mathcal{P}([0,1]). I_{\mathbb{R}} \cup (X \times \{7\})$$

$f$ חח"ע, לכן $|A| \geq |\mathcal{P}([0,1])| = 2^{\aleph}$.

מקש"ב: $|A| = 2^{\aleph}$.

פעולות על עוצמות¶

הגדרות¶

הגדרה: פעולות על עוצמות

לכל שתי קבוצות $A, B$:

חיבור: $|A| + |B| = |A \cup B|$ עבור $A$ ו-$B$ זרות.
עבור קבוצות לא זרות: $|A| + |B| = |(A \times \{0\}) \cup (B \times \{1\})|$
כפל: $|A| \cdot |B| = |A \times B|$
חזקה: $|A|^{|B|} = |B \to A|$

קבוצת החזקה¶

משפט

עבור קבוצה $A$: $$|\mathcal{P}(A)| = |A \to \{0,1\}| = 2^{|A|}$$

בפרט: $$\aleph = |\mathcal{P}(\mathbb{N})| = 2^{|\mathbb{N}|} = 2^{\aleph_0}$$

תכונות הפעולות¶

תכונות בסיסיות¶

משפט: תכונות הפעולות על עוצמות

לכל שלוש עוצמות $a, b, c$ מתקיים:

1. שימור סדר:

$a \leq b \Rightarrow a + c \leq b + c$
$a \leq b \Rightarrow a \cdot c \leq b \cdot c$
$a \leq b \Rightarrow a^c \leq b^c$
$a \leq b \land \neg(a = c = 0 \land b \neq 0) \Rightarrow c^a \leq c^b$

2. קומוטטיביות:

$a + b = b + a$
$a \cdot b = b \cdot a$

3. אסוציאטיביות:

$(a + b) + c = a + (b + c)$
$(a \cdot b) \cdot c = a \cdot (b \cdot c)$

4. דיסטריביוטיביות:

$a \cdot (b + c) = a \cdot b + a \cdot c$

חוקים מיוחדים¶

חוקי 0 ו-1

$a + 0 = a$
$a \cdot 0 = 0$
$a \cdot 1 = a$
$a^0 = 1$
$1^a = 1$
$0^a = \begin{cases} 1 & a = 0 \\ 0 & \text{אחרת} \end{cases}$

חוקי חזקות¶

חוקי חזקות

$(a \cdot b)^c = a^c \cdot b^c$
$a^{b+c} = a^b \cdot a^c$
$(a^b)^c = a^{b \cdot c}$

טענות חשובות¶

טענה: קבוצת מנה

אם $T$ יחס שקילות על $A$, אז $|A/T| \leq |A|$.

הוכחה: הפונקציה $g = \lambda x \in A. [x]_T$ היא על מ-$A$ ל-$A/T$, ולכן $|A/T| \leq |A|$.

הערה חשובה

אם $A \subseteq B$ אז $|A| \leq |B|$, אבל כאשר $A \not\subseteq B$ לא בהכרח $|A| < |B|$.

תרגילים¶

תרגיל 1

הוכיחו שעוצמת המחרוזות הבינאריות האינסופיות בהן 1 לא מופיע פעמיים ברצף היא $2^{\aleph_0}$.

תרגיל 2

מצאו את עוצמת הקבוצה: $$A = \{f \in \mathbb{N} \to \mathcal{P}(\mathbb{N}) \mid (\forall n \in \mathbb{N}. |f(n)| = \aleph_0) \land (\forall m,k \in \mathbb{N}. f(m) = f(k) \to m = k)\}$$

מקורות¶

מקורות היחידה

ספר הקורס: פרק ג.4 - קש"ב ופעולות עוצמות
תרגול 12 - משפט קש"ב, פעולות עוצמות