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

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

הגדרות יסוד והשוואת עוצמות

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

פונקציה חד-חד-ערכית (חח"ע) / אינג'קציה: פונקציה $f: A \to B$ כך שלכל $x_1, x_2 \in A$, אם $x_1 \neq x_2$ אז $f(x_1) \neq f(x_2)$. כלומר, כל איבר ב-$A$ ממופה לאיבר יחיד ושונה ב-$B$.

פונקציה על / סורג'קציה: פונקציה $f: A \to B$ כך שלכל $y \in B$ קיים $x \in A$ עבורו $f(x) = y$. כלומר, כל איבר ב-$B$ הוא תמונה של לפחות איבר אחד ב-$A$.

פונקציה חד-חד-ערכית ועל (חח"ע ועל) / ביג'קציה: פונקציה שהיא גם חח"ע וגם על. פונקציה כזו יוצרת התאמה מושלמת "אחד לאחד" בין איברי $A$ ו-$B$.

השוואת עוצמות

עוצמות שוות: נאמר שלקבוצות $A$ ו-$B$ יש אותה עוצמה, ונסמן $|A| = |B|$, אם קיימת ביג'קציה $f: A \to B$.
עוצמה קטנה או שווה: נאמר שעוצמת $A$ קטנה או שווה לעוצמת $B$, ונסמן $|A| \le |B|$, אם קיימת אינג'קציה $f: A \to B$.

משפט קנטור-ברנשטיין (Schröder-Bernstein Theorem): אם קיימת אינג'קציה מ-$A$ ל-$B$ וקיימת אינג'קציה מ-$B$ ל-$A$, אז קיימת ביג'קציה מ-$A$ ל-$B$. כלומר, אם $|A| \le |B|$ וגם $|B| \le |A|$, אז $|A| = |B|$. משפט זה הוא כלי רב עוצמה להוכחת שוויון עוצמות מבלי לבנות ביג'קציה מפורשת.

עוצמות בנות מנייה: אלף אפס ($\aleph_0$)

המושג "בת מנייה" מתאר קבוצות שניתן "לספור" את איבריהן, גם אם הספירה אינה נגמרת.

קבוצה סופית: קבוצה $A$ היא סופית אם קיימת ביג'קציה בין $A$ לקבוצה $\{1, 2, \dots, n\}$ עבור $n \in \mathbb{N} \cup \{0\}$ כלשהו.

קבוצה בת מנייה: קבוצה $A$ היא בת מנייה אם היא סופית, או אם קיימת ביג'קציה בין $A$ לקבוצת המספרים הטבעיים $\mathbb{N} = \{1, 2, 3, \dots\}$. עוצמת קבוצה אינסופית בת מנייה מסומנת ב-$\aleph_0$ (אלף אפס).

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

המספרים הטבעיים ($\mathbb{N}$): זוהי ההגדרה עצמה. $|\mathbb{N}| = \aleph_0$.
המספרים השלמים ($\mathbb{Z}$): ניתן למנות אותם: $0, 1, -1, 2, -2, \dots$. ניתן לבנות ביג'קציה $f: \mathbb{N} \to \mathbb{Z}$.
המספרים הרציונליים ($\mathbb{Q}$): למרות שהם "צפופים" על ציר המספרים, קנטור הראה שניתן למנות אותם. ניתן לבנות ביג'קציה מ-$\mathbb{N}$ ל-$\mathbb{Q}$ (למשל, באמצעות שיטת האלכסון למניית שברים).
מכפלה קרטזית של קבוצות בנות מנייה: לדוגמה, $|\mathbb{N} \times \mathbb{N}| = \aleph_0$.

הוכחת מנייה: שאלה נפוצה במבחנים היא להוכיח שקבוצה נתונה היא בת מנייה. הדרך המקובלת היא לבנות ביג'קציה מפורשת ל-$\mathbb{N}$ (או ל-$\mathbb{Z}$ או ל-$\mathbb{N} \times \mathbb{N}$), או להראות שקיימת אינג'קציה מהקבוצה ל-$\mathbb{N}$ וגם אינג'קציה מ-$\mathbb{N}$ לקבוצה (ואז להשתמש במשפט קנטור-ברנשטיין). שימו לב לדייק בהגדרת הפונקציה ובהוכחת היותה חח"ע ועל.

עוצמות שאינן בנות מנייה: עוצמת הרצף ($c$)

לא כל הקבוצות האינסופיות ניתנות למנייה. קיימות "רמות" שונות של אינסוף.

משפט קנטור: לכל קבוצה $A$, עוצמת קבוצת החזקה שלה $P(A)$ גדולה ממש מעוצמת $A$. כלומר, $|A| < |P(A)|$. משפט זה מוכיח קיום של אינסוף רמות של אינסוף.

האלכסון של קנטור והוכחת אי-מנייה

קנטור השתמש בטיעון האלכסון המפורסם כדי להוכיח שקבוצת המספרים הממשיים $\mathbb{R}$ אינה בת מנייה. הוא הראה שגם אם ננסה לרשום את כל המספרים הממשיים ברשימה ממוספרת, תמיד נוכל לבנות מספר ממשי שאינו מופיע ברשימה.

עוצמת הרצף ($c$): עוצמת קבוצת המספרים הממשיים $\mathbb{R}$. הוכח ש-$c = |P(\mathbb{N})| = 2^{\aleph_0}$.

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

המספרים הממשיים ($\mathbb{R}$): $| \mathbb{R} | = c$.
כל קטע פתוח או סגור על ציר המספרים (למשל, $[0,1]$ או $(0,1)$): עוצמתם שווה לעוצמת $\mathbb{R}$, כלומר $c$.
קבוצת החזקה של המספרים הטבעיים ($P(\mathbb{N})$): עוצמתה $2^{\aleph_0} = c$.
קבוצת הפונקציות מ-$\mathbb{N}$ ל-$\{0,1\}$: עוצמתה $2^{\aleph_0} = c$.

$\aleph_0$ (אלף אפס)

עוצמת הקבוצות האינסופיות הקטנות ביותר, בנות המנייה. דוגמאות: $\mathbb{N}, \mathbb{Z}, \mathbb{Q}$.

$c$ (עוצמת הרצף)

עוצמת קבוצת המספרים הממשיים $\mathbb{R}$. שווה ל-$2^{\aleph_0}$. קבוצות אלו אינן בנות מנייה.

$2^c$

עוצמת קבוצת החזקה של $\mathbb{R}$, כלומר $P(\mathbb{R})$. גדולה ממש מ-$c$ לפי משפט קנטור.

שאלות לדיון

האם קיימת קבוצה $A$ כך ש-$|A| < \aleph_0$ ו-$A$ אינסופית? נמקו.
הוכיחו באמצעות בניית פונקציה מפורשת ש-$|\mathbb{N} \times \mathbb{N}| = \aleph_0$.
הסבירו במילים שלכם מדוע טיעון האלכסון של קנטור מוכיח ש-$[0,1]$ אינה בת מנייה.
האם קיימת קבוצה $A$ כך ש-$|A| = |P(A)|$? נמקו.

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

הגדרות מדויקות: בכל הוכחה או דיון, יש להשתמש בהגדרות הפורמליות של חח"ע, על, ביג'קציה, עוצמה שווה/קטנה-שווה.
בניית פונקציות: כאשר נדרשת הוכחת שוויון עוצמות, יש לבנות פונקציה מפורשת (אינג'קציה או ביג'קציה) ולהוכיח שהיא אכן חח"ע ו/או על.
שימוש במשפטים: הכירו את משפט קנטור-ברנשטיין ומשפט קנטור, ודעו מתי וכיצד ליישם אותם. לדוגמה, כדי להוכיח ש-$|A|=|B|$, מספיק למצוא אינג'קציה מ-$A$ ל-$B$ ואינג'קציה מ-$B$ ל-$A$.
הבנת רמות האינסוף: הפנימו את ההבדל בין קבוצות בנות מנייה לקבוצות שאינן בנות מנייה, ואת המשמעות של $2^{\aleph_0} = c$.
בהירות ונימוק: כל שלב בהוכחה או בתשובה חייב להיות מנומק היטב ומוצג בצורה ברורה והגיונית.

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