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

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

בתורת הקבוצות, משפט קנטור קובע שלכל קבוצה 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, האתגר הוא להוכיח את נכונות המשפט עבור קבוצות אינסופיות. על פי סמוליאן, ביקום שגודלו אינסופי כל קבוצה אפשרית של תושבים יוצרת לה מועדון. כל מועדון נקרא על שם אחד התושבים (תושב לא חייב להיות חבר במועדון הקרוי על שמו), ועל שם אף תושב לא נקרא יותר ממועדון אחד (זוהי המקבילה לפסוק "עוצמתה של קבוצת החזקה של קבוצת כל התושבים שווה לעוצמתה של קבוצת כל התושבים"). בשלב זה יש לבדוק את המועדון שמכיל את כל התושבים שלא חברים במועדון שקרוי על שמם ורק אותם. קבוצה זו, כמו שאר הקבוצות, חייבת להיקרא על שם אחד התושבים. אם תושב זה חבר במועדון, הרי הוא חבר במועדון הקרוי על שמו, בסתירה להגדרת המועדון; אם הוא לא חבר במועדון זה, הרי הוא אינו חבר במועדון שעל שמו, אך גם לא חבר במועדון שציינו, בסתירה להגדרת המועדון. לפיכך, הנחות היסוד של הבעיה מוטעות, ואין אפשרות להתאים את קבוצת החזקה של קבוצה אינסופית כלשהי לקבוצה עצמה.

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

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

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

[עריכה] ראו גם

מונחים בתורת הקבוצות

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

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

תוכן עניינים

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

[עריכה] הסבר אינטואיטיבי

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

[עריכה] ראו גם

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

שפות אחרות