משפט קנטור (תורת הקבוצות)

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

בתורת הקבוצות, משפט קנטור קובע שלכל קבוצה X, עוצמתה של קבוצת תת-הקבוצות שלה, גדולה ממנה. בפרט, לכל עוצמה, יש עוצמה גדולה ממנה, ולכן לא תיתכן עוצמה גדולה ביותר.

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

[עריכה] הוכחה

תהא $\ X$ קבוצה כלשהי. הפונקציה $\ f:X \rarr P(X)$ המקיימת $f(x)=\left\{x\right\}$ היא התאמה חד-חד ערכית, ולכן $\left|X\right| \le \left|P(X)\right|$ . כדי לסיים את הוכחת המשפט, די להוכיח שלא קיימת פונקציה $\ f:X \rarr P(X)$ המכסה את כל אברי $\ P(X)$ .

ההוכחה היא בדרך השלילה. נניח שקיימת פונקציה כנזכר לעיל, ונגדיר את הקבוצה $A=\left\{x \isin X|x \not\in f(x) \right\}$ . זוהי בוודאי תת קבוצה של $\!\, X$ , כלומר $\ A\isin P(X)$ . על-פי ההנחה, הפונקציה f מכסה את כל תת-הקבוצות של $\ X$ , ולכן קיים $x_0 \isin X$ כך ש $f\left(x_0\right)=A$ .

כעת ישנן שתי אפשרויות: האיבר $\ x_0$ שייך ל- $\ A$ , או שאינו שייך לה. אם הוא שייך לה, אז על-פי הבניה של $A$ , מוכרחים להסיק כי $x_0 \not\in f(x_0)=A$ . אבל אם $\ x_0$ אינו שייך לקבוצה $\ A$ , הרי ש- $x_0 \isin f(x_0)=A$ . שתי ההנחות מובילות, אם-כן, לסתירה. אנו מוכרחים להסיק שהפונקציה $\ f$ שאת קיומה הנחנו, אינה קיימת.

[עריכה] תוצאות

עבור קבוצות סופיות, המשפט חוזר על אי-השוויון הידוע $\ 2^n>n$ , ותו לא. אולם, כבר עבור הקבוצה $\ X=\mathbb{N}$ , קבוצת המספרים הטבעיים, שאת עוצמתה מקובל לסמן באלף אפס, המשפט מראה כי $\ 2^{\aleph_0}>\aleph_0$ ; כלומר, לא ניתן לסדר את כל תת-הקבוצות של המספרים הטבעיים בסדרה, מבלי להחסיר רבות מהן.

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