יחידה 10: עוצמות¶

מושגי יסוד¶

שוויון עוצמות¶

הגדרה: שוויון עוצמות

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

סימון: $|A| = |B|$ או $A \sim B$

טענה: יחס שקילות

היחס $\sim$ (שוויון עוצמות) מתנהג כיחס שקילות:

רפלקסיביות: $|A| = |A|$ (פונקציית הזהות היא זיווג)
סימטריות: $|A| = |B| \Rightarrow |B| = |A|$ (הפונקציה ההפוכה היא זיווג)
טרנזיטיביות: $|A| = |B| \land |B| = |C| \Rightarrow |A| = |C|$ (הרכבת זיווגים)

סימונים מיוחדים¶

הגדרה: $\aleph_0$ (אלף-אפס)

\[\aleph_0 = |\mathbb{N}|\]

קבוצה $A$ נקראת בת-מניה (countable) אם $|A| = \aleph_0$.

הגדרה: $\aleph$ (עוצמת הרצף)

\[\aleph = |\mathbb{R}|\]

קבוצה בעוצמה $\aleph$ נקראת בעוצמת הרצף (continuum).

קבוצות בנות-מניה¶

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

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

$|\mathbb{N}^k| = |\mathbb{N} \times \mathbb{N}| = |\mathbb{N}| = \aleph_0$ לכל $k > 0$
$|\mathbb{Q}| = |\mathbb{Z}| = \aleph_0$
תת-קבוצה אינסופית של קבוצה בת-מניה היא בת-מניה
איחוד בן-מניה של קבוצות בנות-מניה הוא בן-מניה

דוגמאות לקבוצות בנות-מניה

$\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$
$\mathbb{N} \times \mathbb{N}$
קבוצת כל המחרוזות הסופיות מעל א"ב סופי
קבוצת כל הפולינומים עם מקדמים רציונליים

טכניקות להוכחת שוויון עוצמות¶

שיטה: בניית זיווג

כדי להוכיח $|A| = |B|$, בונים פונקציה $f: A \to B$ ומוכיחים:

$f$ מוגדרת היטב (לכל $a \in A$ יש ערך $f(a) \in B$)
$f$ חח"ע (אם $f(a_1) = f(a_2)$ אז $a_1 = a_2$)
$f$ על (לכל $b \in B$ קיים $a \in A$ כך ש-$f(a) = b$)

דוגמה: $|\mathbb{Z}| = |\mathbb{N}|$

נבנה זיווג $f: \mathbb{N} \to \mathbb{Z}$:

\[f(n) = \begin{cases} \frac{n}{2} & n \text{ זוגי} \\ -\frac{n+1}{2} & n \text{ אי-זוגי} \end{cases}\]

הסדרה: $0, -1, 1, -2, 2, -3, 3, \ldots$

עוצמת הרצף¶

קבוצות בעוצמת הרצף¶

טענה: עוצמת קטעים

לכל $a < b$ ממשיים: $$|[a,b]| = |[a,b)| = |(a,b]| = |(a,b)| = \aleph$$

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

$|\mathbb{R}| = \aleph$
$|[0,1]| = \aleph$
$|\mathbb{R}^n| = \aleph$ לכל $n \geq 1$
$|\mathcal{P}(\mathbb{N})| = \aleph$
$|\mathbb{N} \to \{0,1\}| = \aleph$

הקשר בין $\aleph_0$ ל-$\aleph$¶

משפט קנטור

$\aleph_0 < \aleph$

כלומר: $\mathbb{R}$ אינה בת-מניה.

המלון של הילברט¶

המלון של הילברט (Hilbert's Hotel)

הרעיון: מלון עם אינסוף חדרים, ממוספרים $0, 1, 2, 3, \ldots$

תרחיש 1: המלון מלא, מגיע אורח אחד חדש.

פתרון: כל אורח עובר לחדר הבא ($n \to n+1$)
החדר 0 מתפנה לאורח החדש
זיווג: $f(n) = n+1$ הוא חח"ע מ-$\mathbb{N}$ ל-$\mathbb{N} \setminus \{0\}$

תרחיש 2: מגיעים אינסוף אורחים חדשים.

פתרון: כל אורח עובר לחדר הזוגי ($n \to 2n$)
החדרים האי-זוגיים מתפנים לאורחים החדשים
זיווג: $\mathbb{N} \cup \mathbb{N} \sim \mathbb{N}$

מסקנה

$\aleph_0 + 1 = \aleph_0$ וגם $\aleph_0 + \aleph_0 = \aleph_0$

קבוצה אינסופית יכולה להיות שווה בעוצמה לתת-קבוצה ממש שלה!

סדר על עוצמות¶

הגדרה: $|A| \leq |B|$

$|A| \leq |B|$ אם קיימת פונקציה חח"ע $f: A \to B$.

שקול: קיימת פונקציה על $g: B \to A$.

הגדרה: $|A| < |B|$

$|A| < |B|$ אם $|A| \leq |B|$ וגם $|A| \neq |B|$.

טבלת סיכום: עוצמות נפוצות¶

קבוצה	עוצמה	הערות
$\emptyset$	$0$	הקבוצה הריקה
$\{a\}$	$1$	סינגלטון
$\{1, \ldots, n\}$	$n$	קבוצה סופית
$\mathbb{N}$	$\aleph_0$	בת-מניה
$\mathbb{Z}$	$\aleph_0$	בת-מניה
$\mathbb{Q}$	$\aleph_0$	בת-מניה
$\mathbb{R}$	$\aleph = 2^{\aleph_0}$	עוצמת הרצף
$\mathcal{P}(\mathbb{N})$	$\aleph = 2^{\aleph_0}$	עוצמת הרצף

תרגילים¶

תרגיל 1

הוכיחו: $|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|$

תרגיל 2

הוכיחו: $|(0,1)| = |\mathbb{R}|$ (רמז: $\tan$)

תרגיל 3

הוכיחו שקבוצת כל הפולינומים עם מקדמים שלמים היא בת-מניה.

מקורות¶

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

ספר הקורס: פרק ג.1-ג.2 - עוצמות
תרגול 10 - עוצמות

קבוצה	עוצמה	הערות
\(\emptyset\)	\(0\)	הקבוצה הריקה
\(\{a\}\)	\(1\)	סינגלטון
\(\{1, \ldots, n\}\)	\(n\)	קבוצה סופית
\(\mathbb{N}\)	\(\aleph_0\)	בת-מניה
\(\mathbb{Z}\)	\(\aleph_0\)	בת-מניה
\(\mathbb{Q}\)	\(\aleph_0\)	בת-מניה
\(\mathbb{R}\)	\(\aleph = 2^{\aleph_0}\)	עוצמת הרצף
\(\mathcal{P}(\mathbb{N})\)	\(\aleph = 2^{\aleph_0}\)	עוצמת הרצף