משפט קנטור

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Nuvola apps edu mathematics blue-p.svg

בערך זה
נעשה שימוש
בסימנים מוסכמים
מתחום המתמטיקה.
להבהרת הסימנים
ראו סימון מתמטי.

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

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

מושגים[עריכת קוד מקור | עריכה]

קבוצה היא עצם יסודי במתמטיקה שניתן לתארו כאוסף כלשהו של איברים.‏[1] לגבי כל איבר וכל קבוצה ייתכנו שתי אפשרויות: האיבר שייך לקבוצה או שאינו שייך לקבוצה.

פונקציות[עריכת קוד מקור | עריכה]

דוגמה לפונקציה חד-חד-ערכית ועל מקבוצה X לקבוצה Y. קיומה של הפונקציה מעיד על כך שבשתי הקבוצות אותו מספר של איברים.

פונקציה מקבוצה A לקבוצה B מתאימה לכל איבר ב-A איבר יחיד ב-B. ייתכן שלכמה איברים ב-A מותאם אותו איבר ב-B, וייתכן שיש איברים של B שאף איבר של A אינו מותאם להם.

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

השוואת גודלן של קבוצות[עריכת קוד מקור | עריכה]

קיומה של פונקציה חד-חד-ערכית ועל מקבוצה סופית A לקבוצה B מראה שלשתי הקבוצות יש אותו מספר איברים, משום שלכל איבר מכל אחת מן הקבוצות יש בן זוג יחיד שהותאם לו מהקבוצה השנייה. אפשר לספור את איברי שתי הקבוצות יחד. קנטור הבין שניתן להשתמש ברעיון הזה כדי להשוות גם בקבוצות אינסופיות בגודלן. נניח ש-A ו-B הן קבוצות כלשהן (אולי אינסופיות). אם קיימת פונקציה חד-חד-ערכית ועל מ-A ל-B נאמר שהקבוצות האלו שקולות, ונסמן  A\sim B[2] השקילות בין הקבוצות מבטאת, על-פי קנטור, את הרעיון שיש להן אותו מספר של איברים. אם שתי קבוצות \ A,B הן שקולות, מסמנים |A|=|B|. על הסימן |A| חושבים כאילו הוא מסמן את מספר האיברים בקבוצה A, שיכול להיות אינסופי. זוהי העוצמה של A.

מן המקרה של קבוצות סופיות ידוע לנו שהעוצמה של קבוצה אחת יכולה להיות גדולה מן העוצמה של קבוצה אחרת. למשל, בקבוצה עם ארבעה איברים יש יותר איברים מאשר בקבוצה עם איבר אחד. רעיון זה מתבטא בעובדה שקיימת פונקציה חד-חד-ערכית שאינה על מהקבוצה השנייה לראשונה. באופן כללי לכל שתי קבוצות A ו-B נאמר ש-|A|\le |B|, אם קיימת פונקציה חד-חד ערכית (שאינה בהכרח על) מ-A ל-B[3] כלומר B גדולה (או שווה) מ-A אם אפשר להתאים לכל איבר ב-A בן זוג יחיד ב-B, גם אם נשארים איברים של B שלא הותאם להם בן זוג. אם מתקיים |A|\le |B| וגם |A|\ne |B|, אז נאמר ש- |A|<|B|. משפט קנטור-שרדר-ברנשטיין קובע שאם |A|\le |B| וגם |A|\ge |B|, אז |A|=|B| (המשפט אינו מובן מאליו: הוא טוען שאם יש פונקציה חד-חד-ערכית מ-A ל-B, ופונקציה על מ-A ל-B, אז יש גם פונקציה שהיא בו-זמנית חד-חד-ערכית ועל).

סימונים[עריכת קוד מקור | עריכה]

קבוצה C תקרא תת-קבוצה של A, אם כל איבר של C הוא גם איבר של A. קבוצת כל התת-קבוצות של A נקראת קבוצת החזקה של A, ומסמנים אותה בסימון  \mathcal{P}(A).

קבוצה מסמנים על פי רוב באות לטינית גדולה. אם רוצים לפרט את איברי הקבוצה כותבים אותם בתוך סוגריים מסולסלים, כשהם מופרדים בפסיקים. למשל \{a, b, c\} היא קבוצה שאיבריה הם a, b ו-c. דרך נוספת לציון קבוצה היא ציון תנאי שאיברי הקבוצה מקיימים. למשל \{x \mid 1<x<3\} היא קבוצת המספרים שבין 1 ל-3, ואילו \{p^2 \mid  p \text{ is prime}\} היא קבוצת המספרים שהם ריבועים של המספרים הראשוניים.

  • אם a הוא איבר של הקבוצה A מסמנים זאת a\in A, ואם הוא אינו איבר של A מסמנים זאת a\not\in A.
  • פונקציה מ-A ל-B מסמנים f: A \to B. את האיבר ב-B שהפונקציה מתאימה לאיבר a ב-A מסמנים f(a). למשל הפונקציה f שמתאימה לכל מספר טבעי את העוקב שלו מוגדרת לפי החוק f(n) = n+1, אבל יש פונקציות מסובכות, שלא ניתן לכתוב להן חוקים מסוג זה.
  • אם C תת-קבוצה של A, כלומר כל איבר של C הוא גם איבר של A, מסמנים C \subseteq A.
  • לפי הסימונים שהצגנו עתה, ניתן להגדיר את קבוצת החזקה של A כך:  \mathcal{P}(A) = \{C \mid  C\subseteq A\}.

נוסח המשפט[עריכת קוד מקור | עריכה]

משפט קנטור. לכל קבוצה A (סופית או אינסופית), מתקיים |A|<|\mathcal{P}(A)|.

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

אם A אינסופית, קל לבנות קבוצה המכילה אותה (שיש בה איברים חדשים), אבל בדרך כלל הקבוצה החדשה תהיה בעלת אותה עוצמה. למשל, אם נוסיף איבר אחד לקבוצה אינסופית A, העוצמה תשאר בעינה‏[4]. אם ניקח שתי קבוצות אינסופיות מעוצמה זהה, ונאחד אותן, עוצמת האיחוד תהיה שווה לעוצמה של כל אחת מהקבוצות בנפרד. אפילו עוצמתה של קבוצת המספרים הרציונלים (הכוללת את כל השברים) זהה לעוצמת קבוצת המספרים הטבעיים לבדם (להוכחה ראו כאן וכאן).

הוכחת המשפט[עריכת קוד מקור | עריכה]

תהא \ A קבוצה כלשהי. הפונקציה g(a) = \{a\} לכל a\in A היא פונקציה חד-חד ערכית מ-A ל- \mathcal{P}(A), ולכן |A|\le |\mathcal{P}(A)|.

נותר אם כך להוכיח כי |A| \ne |\mathcal{P}(A)|. נניח בשלילה את ההיפך, כלומר, ש-|A| = |\mathcal{P}(A)|, ונראה כי הדבר מוביל לסתירה.

אם |A| = |\mathcal{P}(A)|, הרי שקיימת פונקציה חד-חד-ערכית ועל f: A \to \mathcal{P}(A) (למעשה אין צורך בהנחה שהפונקציה חד-חד-ערכית; ההוכחה מראה שאפילו פונקציה על, סתם, אינה אפשרית). הפונקציה f מתאימה לכל איבר של A תת-קבוצה של A, ומכסה באופן הזה את כל התת-קבוצות. לכן לגבי כל איבר של A ייתכנו שתי אפשרויות: או שהוא איבר של התת-קבוצה המתאימה לו, או שהוא אינו איבר שלה. נגדיר קבוצה D, כך: D = \{a\in A \mid  a\not\in f(a)\}. הקבוצה D מורכבת מכל אותם איברים של A שאינם איברים של התת-קבוצה המתאימה להם. D מורכבת מאיברים של A בלבד, ולכן היא תת-קבוצה של A. לפי ההנחה, שהפונקציה f היא על, קיים ב-A איבר d כך ש-f(d) = D.‏[5]

עתה נשאלת השאלה האם d הוא בעצמו איבר של D? אם נניח ש-d \in D, הרי ש-d איבר בקבוצה שהותאמה לעצמו, ולכן לפי הגדרת D מקבלים שדווקא d \not\in D. אם נניח ש-d\not\in D נקבל ש-d אינו איבר בקבוצה שהותאמה לעצמו, ולכן לפי הגדרת D מתקיים d \in D.

בשני המקרים הגענו לסתירה, ולכן ההנחה שלנו חייבת להיות שגויה. מכאן ש-|A| \ne |\mathcal{P}(A)|, ולכן |A| < |\mathcal{P}(A)|.

הסבר אינטואיטיבי[עריכת קוד מקור | עריכה]

הפילוסוף והחידונאי ריימונד סמוליאן, בספרו "מה שמו של ספר זה?", מציג גרסה אינטואיטיבית להוכחה. הגרסה המופיעה כאן מבוססת על גרסה זו. כל קבוצה אפשרית של תושבים ביקום (שגודלו עשוי להיות אינסופי) יוצרת לה מועדון (התושבים הם איברי A, והמועדונים הם איברי \mathcal{P}(A)). נניח שכל מועדון נקרא על-שם אחד התושבים (זוהי ההנחה שקיימת פונקציה על בין הקבוצות). נקים את המועדון שחבריו הם כל התושבים שאינם חברים במועדון הקרוי על שמם. מועדון זה, ככל מועדון אחר, חייב להיקרא על שם אחד התושבים - למשל גראוצ'ו.‏[6] אם גראוצ'ו חבר במועדון, הרי שהוא חבר במועדון הקרוי על שמו, בסתירה להגדרת המועדון; אבל אם הוא לא חבר במועדון, הרי שהוא מקיים את תנאי הקבלה היחיד למועדון, ונעשה בו חבר באופן אוטומטי. סתירה זו מעידה כי ההנחה שאפשר לקרוא כל מועדון על שם תושב, מוטעית. האינסוף של המועדונים גדול יותר מן האינסוף של התושבים.

נוסח שקול[עריכת קוד מקור | עריכה]

לפונקציה f: A \to \{0,1\} (כלומר פונקציה שמתאימה לכל איבר ב-A את המספר 0 או 1) קוראים פונקציה מציינת. מקובל לסמן את קבוצת כל הפונקציות מ-A ל-B בסימון B^A. על כן קבוצת הפונקציות המציינות של קבוצה A היא \{0,1\}^A.

נשים לב כי \{0,1\}^A \sim \mathcal{P}(A). זאת משום שלכל פונקציה מציינת ניתן להתאים את התת-קבוצה של A שהפונקציה המציינת מתאימה לאיבריה (ורק לאיבריה) את המספר 1, ולשאר האיברים היא מתאימה 0. לכן משפט קנטור קובע כי |A| < |\{0,1\}^A| (למעשה זהו הנוסח של קנטור במקור).

מגדירים את פעולת החזקה בין עוצמות באופן הבא: |B|^{|A|} = |B^A|. הגדרה זו מכלילה את ההגדרה הרגילה לחזקה בין מספרים טבעיים, ומתלכדת עימה כאשר היא מופעלת על טבעיים (ראו חזקה: קבוצות ועצמות). בהתאם להגדרה זו:  |\{0,1\}^A| = |\{0,1\}|^{|A|} = 2^{|A|}.

על כן נוכל לנסח את משפט קנטור גם באופן הבא: לכל עוצמה |A| מתקיים: |A|<2^{|A|}.

מקרים פרטיים[עריכת קוד מקור | עריכה]

A=\{1,2,3\}

|A|=3

\mathcal{P}(A) = \{\{\},\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}

 |\mathcal{P}(A)| = 8 = 2^3

קבוצות סופיות[עריכת קוד מקור | עריכה]

אם A היא קבוצה סופית בעלת n איברים (|A|=n), אז |\mathcal{P}(A)| = 2^n. תוצאה זו מתקבלת משיקול קומבינטורי פשוט: בהינתן תת-קבוצה שרירותית של A, לגבי כל איבר ב-A יש שתי אפשרויות: או שהוא איבר של התת-קבוצה או שהוא לא. מעקרון הכפל מקבלים שיש: 2\cdot 2\cdots 2 = 2^n אפשרויות לכל n האיברים יחדיו, ולכן זהו מספר התת-קבוצות (כאמור בפרק הקודם, תוצאה זו נכונה אפילו לעוצמות אינסופיות).

לכן משפט קנטור לקבוצות סופיות קובע את האי-שוויון הידוע \ n<2^n, לכל n טבעי. אי-שוויון זה ניתן להוכחה בפשטות באינדוקציה, ולכן עיקר העניין במשפט קנטור הוא בהשלכותיו לגבי קבוצות אינסופיות.

קבוצת המספרים הטבעיים והאלכסון של קנטור[עריכת קוד מקור | עריכה]

ישנו עניין מיוחד במשפט קנטור כאשר הוא מופעל על קבוצת המספרים הטבעיים, \{0,1,2,3,\ldots\}.‏[7] הסימון לקבוצת המספרים הטבעיים הוא \mathbb{N}. קנטור בחר לסמן את העוצמה של \mathbb{N}, שהיא העוצמה האינסופית הקטנה ביותר, בסימון אלף אפס: |\mathbb{N}| = \aleph_0. משפט קנטור מראה כי  |\mathbb{N}|<|\mathcal{P}(\mathbb{N})|, או באופן שקול: \aleph_0<2^{\aleph_0}.

במקרה הזה ניתן להציג את הוכחת משפט קנטור באופן מוחשי יותר, שממנו גם ברור השם "לכסון". הוכחת המשפט נפתחת בהנחה שקיימת פונקציה f: \mathbb{N} \to \mathcal{P}(\mathbb{N}). ניתן להציג פונקציה שכזו כסדרה אינסופית של איברי \mathcal{P}(\mathbb{N}), כך: A_0, A_1, A_2,\ldots. כאשר מוסכם ש-f(n) = A_n (למעשה זוהי ההגדרה הפורמלית של סדרה). כעת מגדירים את הקבוצה הבעייתית D = \{n \in \mathbb{N} \mid  n \not\in A_n \}. לפי ההנחה קיים m כך ש-A_m = D, אך זה לא ייתכן, כי כזכור, נובע מכך שמתקיים בו זמנית m \in A_m ו-m \not\in A_m.

את הטיעון הנ"ל ניתן גם להציג כך: נציג כל A שהוא איבר של \mathcal{P}(\mathbb{N}) כסדרה אינסופית של ספרות באופן הבא: הספרה ה-n בסדרה (החל מ-0) תהיה 1 אם n \in A, ואילו אם n \not\in A היא תהיה 0. למשל הקבוצה \{0,1,2,4,8,\ldots\} תוצג בצורה: 1\ 1\ 1\ 0\ 1\ 0\ 0\ 0\ 1\ldots.

את הסדרה A_0, A_1, A_2,\ldots ניתן להציג כרשימה אינסופית של הייצוגים של כל אחד מאיברי הסדרה כסדרת ספרות. למשל את:

A_0 = \{1\}, A_1 = \{1,3,\ldots\}, A_2 = \{0,1,2,3,4,\ldots\}, A_3 = \{2,4\}, A_4 = \{0,4\},\ldots

נציג בצורה:

\begin{matrix}
 A_n & \text{Representation} \\
 \hline
 A_0 & 0\ 1\ 0\ 0\ 0\ldots \\
 A_1 & 0\ 1\ 0\ 1\ 0\ldots \\
 A_2 & 1\ 1\ 1\ 1\ 1\ldots \\
 A_3 & 0\ 0\ 1\ 0\ 1\ldots \\
 A_4 & 1\ 0\ 0\ 0\ 1\ldots \\
 \vdots & \vdots
\end{matrix}

כעת נשים לב כיצד נבנה D. לפי ההגדרה, אם n \not\in A_n, אז הספרה ה-n בייצוג של D היא 1. ואילו אם n \in A_n אז הספרה ה-n בייצוג של D היא אפס. במילים אחרות, הספרה ה-n של D היא בדיוק ההיפך מהספרה ה-n של A_n. במסגרת הדוגמה שלנו נוכל להמחיש זאת כך:

\begin{matrix}
 A_n & \text{Representation} \\
 \hline
 A_0 & {\color{Red}0}\ 1\ 0\ 0\ 0\ldots \\
 A_1 & 0\ {\color{Red}1}\ 0\ 1\ 0\ldots \\
 A_2 & 1\ 1\ {\color{Red}1}\ 1\ 1\ldots \\
 A_3 & 0\ 0\ 1\ {\color{Red}0}\ 1\ldots \\
 A_4 & 1\ 0\ 0\ 0\ {\color{Red}1}\ldots \\
 \vdots & \vdots \\
 \hline
 D & {\color{blue}1\ 0\ 0\ 1\ 0\ldots} \\
\end{matrix}

לא ייתכן כי קיים A_m כך ש-A_m = D, כי D בהכרח נבדל מ-A_m בספרה ה-m בייצוג שלו.

טיעון האלכסון שהצוג זה עתה קרוי האלכסון של קנטור. הוא הוצג על ידי קנטור באותו מאמר בו הציג את משפט קנטור, וחשיבותו חורגת מהיותו מקרה פרטי של משפט קנטור. זאת משום שהסדרות של הספרות המייצגות כאן תת-קבוצות של \mathbb{N}, יכולות באותה מידה לייצג מספרים ממשיים בין 0 ל-1, שסדרת הספרות היא הכתיב הבינארי (אחרי הנקודה) שלהם (למשל 10000\ldots מייצג את 0.1 שהוא חצי בכתיב בינארי). כאשר מציגים את האלכסון של קנטור כהוכחה לאי-שקילות קבוצת המספרים הטבעיים \mathbb{N} לקבוצת המספרים הממשיים \mathbb{R} (עובדה שיכולה להפתיע, שכן \mathbb{N} שקולה ל-\mathbb{Q}, שהיא קבוצת המספרים הרציונליים) נהוג, לשם הנוחות, להשתמש בהצגה של המספרים בבסיס עשרוני (מבחינה היסטורית, קנטור הוכיח לראשונה את האי-שקילות של הטבעיים והממשיים 17 שנה קודם, בשיטה מוכרת פחות).

עוצמת המספרים הממשיים (השווה גם לעוצמת הממשיים שבין 0 ל-1 בלבד) קרויה עוצמת הרצף, ומקובל לסמנה \aleph. העובדה שהן את הממשיים והן את התת-קבוצות של \mathbb{N} ניתן לבטא כרצפי ספרות אינסופיים, מעידה כי \mathbb{R} ו-\mathcal{P}(\mathbb{N}) שקולות.‏[8] לכן 2^{\aleph_0} = \aleph.

קבוצת כל הקבוצות[עריכת קוד מקור | עריכה]

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

שני הפרדוקסים הידועים ביותר הם:

  • הפרדוקס של קנטור, שהתגלה על ידי קנטור עצמו מעט לאחר שפרסם את משפט קנטור. הפרדוקס נוצר מנסיון להפעיל את משפט קנטור על U.
    הקבוצה \mathcal{P}(U) היא קבוצה שכל איבריה הם קבוצות. בפרט היא תת-קבוצה של U. לכן הפונקציה החד-חד-ערכית f: \mathcal{P}(U) \to U המוגדרת f(A)=A קיימת ומוגדרת היטב. מכאן ש-|P(U)| \le |U|. מצד שני, לפי משפט קנטור מתקיים להיפך |P(U)|>|U|.
  • הפרדוקס של ראסל, שהוצג על ידי המתמטיקאי ברטראנד ראסל בשנת 1901 ושואב השראה מהוכחת משפט קנטור. ואכן, ניתן לראות בפרדוקס של ראסל מקרה פרטי של הוכחת משפט קנטור לגבי הקבוצה U. כאמור, הפונקציה f(A)=A היא פונקציה חד-חד-ערכית מ-\mathcal{P}(U) ל-U. אולם מעקב אחרי שלבי הוכחת קנטור יוביל אותנו למסקנה שפונקציה שכזו לא תתכן. נגדיר את D = \{a \in U \mid  a \not\in f(a)\} = \{a \mid  a\not\in a\}. כעת נקבל שאם D \in D אז D \not\in D, ואילו אם D \not\in D אז D \in D.

מסקנות והשלכות[עריכת קוד מקור | עריכה]

שימושים[עריכת קוד מקור | עריכה]

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

בעיות הכרעה[עריכת קוד מקור | עריכה]

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

כל קלט (סופי) אפשרי הנתון בשפה כלשהי ניתן לקודד (לייצג) כמספר טבעי. קידוד שכזה נקרא מספור גדל ומחשבים מודרניים מיישמים אותו על ידי קידוד בינארי.‏[9] בהינתן קידוד שכזה, לכל בעיית הכרעה ניתן להגדיר את הקבוצה A הכוללת את כל המספרים הטבעיים שמקודדים קלטים שלגביהם התשובה לבעיה היא "כן". ולהיפך, לכל קבוצה של מספרים טבעיים A ניתן להגדיר בעיית הכרעה שמשיבה "כן" על כל הקלטים המקודדים על ידי מספר טבעי שנמצא ב-A. במילים אחרות, את קבוצת כל בעיות ההכרעה ניתן לזהות עם קבוצת כל התת-קבוצות של הטבעיים, \mathcal{P}(\mathbb{N}).

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

משפט קנטור קובע ש- |\mathbb{N}|<|\mathcal{P}(\mathbb{N})|, ולכן יש הרבה יותר בעיות הכרעה מאשר תוכניות מחשב. מכאן שישנן בעיות הכרעה (ולמעשה, כמעט כל בעיות ההכרעה) שאינן ניתנות לפתרון על ידי אף תוכנית מחשב. הדוגמה המוכרת ביותר לבעיית הכרעה שאין תוכנית הפותרת אותה היא בעיית העצירה. אלן טיורינג הוכיח זאת בשנת 1936 בשיטת הלכסון. דוגמאות רבות נוספות מגיעות ממשפט רייס.

טיעון דומה קובע שמרבית המספרים הממשיים אינם ניתנים לחישוב. זאת מכיוון שעוצמת החישובים האפשריים היא |\mathbb{N}| (שכן כל חישוב יכול להעשות על ידי תוכנית מחשב), ואילו לפי האלכסון של קנטור, עוצמה זו קטנה מעוצמת הממשיים.

פונקציות רציפות[עריכת קוד מקור | עריכה]

פונקציה רציפה היא פונקציה ממשית f: \mathbb{R} \to \mathbb{R} (פונקציה מקבוצת המספרים הממשיים לעצמה) שיש לה את התכונה שככל שמתקרבים לנקודה (מספר ממשי) כלשהי x, ערכי הפונקציה הולכים וקרבים ל-f(x), שהוא ערך הפונקציה בנקודה xגרף של פונקציות רציפות הוא קו רציף, ומכאן שמן). את קבוצת הפונקציות הרציפות מקובל לסמן C, ואילו קבוצת הפונקציות הממשיות כולן היא \mathbb{R}^{\mathbb{R}}. נראה כי |C|<|\mathbb{R}^{\mathbb{R}}|, כלומר כמעט כל הפונקציות הממשיות אינן רציפות.

ראשית נמצא את |C|. הערכים שפונקציה רציפה מקבלת בכל נקודה בישר הממשי נקבעים על ידי הערכים שהיא מקבלת בנקודות הרציונליות. זאת משום שהמספרים הרציונליים צפופים בישר, ולכן ניתן לקבל את הערך בכל נקודה אי-רציונלית כגבול של סדרת הערכים בנקודות רציונליות המתקרבת לנקודה (פורמלית: לכל a ממשי, בהינתן סדרת רציונליים x_n \to a, מתקיים f(a) = \lim_{n \to \infty} f(x_n)). מכאן שיש פונקציה חד-חד-ערכית מ-C לקבוצת הפונקציות מהרציונליים לממשיים \mathbb{R}^{\mathbb{Q}}, ולכן |C| \le |\mathbb{R}^{\mathbb{Q}}|. קבוצת הרציונליים שקולה לקבוצת הטבעיים, ולכן בעזרת כללי אריתמטיקה של עוצמות (ומהזהות \aleph_0\cdot\aleph_0=\aleph_0 הנובעת מפונקציית הזיווג של קנטור) נקבל:

|C| \le |\mathbb{R}^{\mathbb{Q}}| = \aleph^{\aleph_0} = \left(2^{\aleph_0}\right)^{\aleph_0} = 2^{\aleph_0\cdot\aleph_0} = 2^{\aleph_0} = \aleph

מצד שני, לכל מספר ממשי a ניתן להתאים את הפונקציה הקבועה f(x) = a שהיא רציפה. מכאן ש-|C| \ge |\mathbb{R}| = \aleph. ממשפט קנטור-שרדר-ברנשטיין נקבל |C| = \aleph.

נעבור ל- \mathbb{R}^{\mathbb{R}}. קבוצה זו כוללת בין השאר כל פונקציה מציינת של \mathbb{R}. קבענו כבר כי עוצמת קבוצת הפונקציות המציינות של \mathbb{R} היא 2^{|\mathbb{R}|} = 2^{\aleph}. לכן  |\mathbb{R}^{\mathbb{R}}|\ge 2^{\aleph} (למעשה מתקיים  |\mathbb{R}^{\mathbb{R}}| = 2^{\aleph}[10]).

לפי משפט קנטור \aleph<2^{\aleph}, ולכן |C|<|\mathbb{R}^{\mathbb{R}}|.

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

מספרי ב'[עריכת קוד מקור | עריכה]

ממשפט קנטור מגיעה המוטיבציה להגדרת סדרה של עוצמות הקרויה מספרי ב'. איברי הסדרה הם:

\ \beth_0 = \aleph_0, \ \beth_1 = 2^{\aleph_0} = \aleph, \ \beth_2 = 2^{2^{\aleph_0}}, \ \beth_3 = 2^{2^{2^{\aleph_0}}},\ \ldots

כלומר זוהי סדרת העוצמות:

|\mathbb{N}|,\ |P(\mathbb{N})|,\ |P(P(\mathbb{N}))|,\ |P(P(P(\mathbb{N})))|,\ \ldots

משפט קנטור מבטיח כי כל העוצמות הללו שונות.

בהגדרה רקורסיבית, מספרי ב' מוגדרים:

 \beth_0 = \aleph_0\ ;\ \beth_{\alpha+1} = 2^{\beth_{\alpha}}

מספרי ב' מוגדרים גם לאינדקסים סודרים, ולא רק טבעיים. לשם כך יש להוסיף להגדרה הרקורסיבית את המקרה של סודר גבולי:

\beth_{\lambda}=\sup\{ \beth_{\alpha}\mid  \alpha<\lambda \}

למשל \beth_{\omega} הוא העוצמה הקטנה ביותר שגדולה מכל העוצמות  \beth_n לכל n טבעי.

בנוסף קנטור הגדיר את הסדרה (המוכללת) \aleph_{\alpha} כסדרת כל העוצמות (\aleph_{\alpha} הוא העוצמה ה-\alpha בגודלה). קנטור שיער ש- \beth_1 = \aleph_1 (כלומר שאין עוצמה בין עוצמת הטבעיים לעוצמת הממשיים). ובאופן כללי יותר ש- \beth_\alpha = \aleph_\alpha. השערות אלו ידועות כהשערת הרצף והשערת הרצף המוכללת בהתאמה.

חרף מאמציו הרבים, קנטור מעולם לא הצליח להוכיח או להפריך את ההשערה עד יום מותו. התקדמות ראשונה בנושא הושגה על ידי קורט גדל שהוכיח בשנת 1937 כי השערת הרצף אינה סותרת את האקסיומות המקובלות של תורת הקבוצות. גורלה של ההשערה הוכרע סופית בשנת 1963 כאשר פול כהן הוכיח כי גם שלילתה של השערת הרצף אינה סותרת את האקסיומות של תורת הקבוצות. מכאן שהשערת הרצף היא טענה עצמאית (והיא הדוגמה המפורסמת ביותר לטענה שכזו), שאין אפשרות להוכיחה או להפריכה.

שיטת הלכסון[עריכת קוד מקור | עריכה]

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

הרעיון הכללי בשיטת הלכסון הוא לבנות אובייקט מתמטי קביל המתייחס לעצמו באופן עקיף. אופי ההתייחסות תלוי בטענה שאותה רוצים להוכיח. הוכחה כללית בלכסון בנויה כך: בהינתן אוסף של איברים \Lambda ואוסף של אובייקטים מהצורה \phi_\alpha, לכל \alpha \in \Lambda. נניח שכל אובייקט \phi_\alpha פועל בצורה כלשהי על איברי \Lambda. נסמן את הפעולה של \phi_\alpha על \beta \in \Lambda כ- \phi_\alpha(\beta) (ניתן לחשוב על \phi_\alpha כפונקציה של איברי \Lambda). מגדירים אובייקט \phi_D שנקרא ה"אלכסון", כך שתוצאת הפעולה \phi_D(\beta) נקבעת על פי תוצאת הפעולה \phi_{\beta}(\beta). אם קיים \gamma \in \Lambda כך ש- \phi_\gamma = \phi_D, אז הכרח שהוא מתייחס לעצמו, שכן לפי ההגדרה, \phi_D(\gamma) נקבע על פי \phi_\gamma(\gamma), כלומר על פי עצמו.

השם "לכסון" מקורו בהמחשה הוויזואלית של שיטת ההוכחה, כפי שהיא מודגמת בטיעון האלכסון של קנטור. הרעיון הוא לדמיין טבלה (אינסופית לרוב) שכל שורה בה מייצגת איבר \alpha וכל עמודה בה מייצגת אובייקט \phi_\alpha (באותו הסדר). בהצטלבות בין השורה של \beta לעמודה של \phi_\alpha מופיע \phi_\alpha(\beta). אובייקט ה"אלכסון" \phi_D נבנה על סמך התאים בטבלה שהם מהצורה \phi_{\beta}(\beta), שמסודרים בקו אלכסוני לאורך ורוחב הטבלה.

להלן דוגמאות חשובות להוכחה בלכסון:

  • הוכחת משפט קנטור היא מקרה כללי של הוכחה בלכסון. נדגים זאת עם נוסח ההוכחה לפונקציות מציינות, שנוח יותר לשימוש במקרה הזה. האוסף \Lambda הוא הקבוצה A. מניחים בשלילה כי לכל פונקציה מציינת של A ניתן להתאים איבר של A. האובייקט \phi_\alpha הוא הפונקציה המציינת שהותאמה לאיבר \alpha \in A. הפעולה  \phi_\alpha(\beta) היא פשוט הפעולה הרגילה של הפונקציה \phi_\alpha על האיבר  \beta. אובייקט האלכסון \phi_D הוא פונקציה מציינת כך ש-\phi_D(\beta) מוגדר כהיפך מ-\phi_{\beta}(\beta) (0 אם הוא 1, ו-1 אם הוא 0). לפי ההנחה קיים \gamma \in A כך ש- \phi_\gamma = \phi_D, ולכן \phi_\gamma(\gamma) \ne \phi_D(\gamma) = \phi_\gamma(\gamma). זוהי סתירה, ולכן ההנחה שגויה ומשפט קנטור נכון.
  • כאמור, אלן טיורינג הוכיח בלכסון כי בעיית העצירה אינה ניתנת להכרעה. כלומר לא קיימת תוכנית מחשב שבהינתן כל תוכנית מחשב וקלט אפשרי, תכריע האם התוכנית הנתונה תסיים את פועלה על הקלט הנתון, או שתכנס ללולאה אינסופית. במקרה הזה \Lambda היא קבוצת כל תוכניות המחשב (בשפה כלשהי). נניח שקיימת תוכנית \phi שבהינתן תוכנית \alpha וקלט \beta מכריעה האם \alpha עוצרת על \beta. הביטוי \phi_\alpha(\beta) יהיה "כן" אם \alpha עוצרת על \beta, ו"לא" אם \alpha נכנסת ללואה אינסופית בהינתן \beta. נגדיר תוכנית D שבהינתן קלט \beta, מריצה את  \phi כדי לגלות מהו \phi_\beta(\beta) (תוכנית יכולה לקבל כקלט את עצמה, שכן כל תוכנית היא בסך הכל רצף של סימנים בשפה) - אם \phi_\beta(\beta) הוא "לא" אז D משיבה "כן", ואם \phi_\beta(\beta) הוא "לא", אז D לא עוצרת. מכאן ש-\phi_D(\beta) הוא "כן" אם \phi_\beta(\beta) הוא "לא", והוא "לא" אם \phi_\beta(\beta) הוא "כן". כמסקנה נקבל ש-\phi_D(D) הוא ההיפך מעצמו. סתירה זו מראה כי ההנחה שלנו כי קיימת תוכנית \phi שמסוגלת להכריע את בעיית העצירה היא שגויה.
  • משפט האי-שלמות הראשון, שהוכח על ידי קורט גדל בשנת 1931, הוא משפט מרכזי בלוגיקה מתמטית. המשפט קובע שבכל תורה העונה לתנאים מסוימים, קיימות טענות עצמאיות שלא ניתנות להוכחה או להפרכה. השלב העיקרי בהוכחת גדל מתבצע בלכסון. במסגרת ההוכחה מתעניינים בכל התכונות שניתן לנסח בתורה הנוגעות למספרים טבעיים. את התכונה שמספרה הוא n (מספור גדל מראה כיצד להצמיד לכל תכונה מספר משלה) נסמן \phi_n. הביטוי \phi_n(k) הוא הטענה שהמספר k מקיים את התכונה \phi (הטענה עשויה להיות נכונה או שגויה). גדל הראה כיצד ניתן לבנות בשפה תכונה \phi_m (זוהי \phi_D) שמתקיימת רק לאותם מספרים טבעיים שלגביהם לא קיימת הוכחה לטענה \phi_n(n). כלומר הטענה \phi_m(n) נכונה אם ורק אם אין הוכחה לטענה \phi_n(n). כעת נפרש את המשמעות של הטענה \phi_m(m). לפי הבניה, זוהי טענה שנכונה אם ורק אם אין הוכחה ל-\phi_m(m). כלומר זוהי טענה שאומרת "אני נכונה אם ורק אם אי אפשר להוכיח אותי".

משפט קנטור בתורת הקבוצות האקסיומטית ותורות חלופיות[עריכת קוד מקור | עריכה]

הפרדוקסים שנתגלו בגישתו של קנטור לתורת הקבוצות, הקרויה כיום תורת הקבוצות הנאיבית, הביאו לפיתוחה של תורת הקבוצות האקסיומטית. התורה האקסיומטית מסתמכת על מערכת של אקסיומות בסיסיות ומוגדרות היטב, כדי למנוע את הופעתם של פרדוקסים. המערכת המקובלת היא מערכת האקסיומות צרמלו-פרנקל (ZF).‏‏[11] במערכת זו משפט קנטור תקף לגבי כל קבוצה. אקסיומת קבוצת החזקה מבטיחה את קיומה של קבוצת החזקה ואקסיומת ההחלפה מבטיחה את קיומה של הקבוצה D הנדרשת בהוכחה. אקסיומת האינסוף קובעת את קיומה של קבוצה אינסופית, ולכן המסקנה ממשפט קנטור כי יש אינסוף עוצמות אינסופיות שונות, אף היא תקפה. הפרדוקסים אינם מופיעים ב-ZF, כי במערכת זו אוסף כל הקבוצות ואוספים דומים לו אינם קבוצות.

בגישות חלופיות לתורת הקבוצות משפט קנטור עשוי שלא להיות תקף. בתורות טיפוסים שונות להוכחת משפט קנטור אין משמעות, כי לא ניתן להשוות בין A ל- \mathcal{P}(A) שלהן טיפוסים שונים. כדי להתגבר על כך מגדירים קבוצה  \mathcal{P}_1(A) = \{\{a\}\mid  a\in A\} שיש לה טיפוס זהה ל- \mathcal{P}(A), ולגביה אכן מתקיים  |\mathcal{P}_1(A)| < |\mathcal{P}(A)| בהתאם למשפט קנטור. לאור העובדה שבתורת הטיפוסים קיימת קבוצת כל הקבוצות U, נשאלת השאלה כיצד בתורה זו נמנעים הפרדוקסים של קנטור ושל ראסל. התשובה היא שבתורת הטיפוסים הפונקציה f: \mathcal{P}(U) \to U המוגדרת f(A)=A אינה קיימת. למעשה בתורה זו  |\mathcal{P}_1(A)| < |\mathcal{P}(U)| < |U|. בתורת הטיפוסים, כאשר מתקיים |\mathcal{P}_1(A)|=|A|, הקבוצה נקראת "קבוצה קנטורית" ולגביה מתקיים משפט קנטור במובנו הרגיל.‏[12]

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

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

הכללות[עריכת קוד מקור | עריכה]

משפט קניג, שהוכח על ידי המתמטיקאי ההונגרי גיולה קניג (נודע גם כיוליוס קניג; 1849-1913) הוא הכללה מרחיקת לכת של משפט קנטור. המשפט קובע שלכל קבוצה A, אם לכל i \in A נתונות זוג עוצמות \kappa_i ו-\mu_i, כך שמתקיים  \kappa_i < \mu_i, אז:

\sum_{i\in A}\kappa_i<\prod_{i\in A}\mu_i

אגף שמאל הוא סכום העוצמות \kappa_i, ואילו אגף ימין הוא מכפלת העוצמות \mu_i. האי-שוויון טריוויאלי כאשר העוצמות והקבוצה סופיים, אבל כלל אינו ברור מאליו למקרים אינסופיים. אם למשל תוחלף המכפלה באגף ימין בסכום, עשוי להתקיים שוויון (מה שבוודאי לא נכון במקרה הסופי).

משפט קנטור מתקבל כמקרה פרטי של משפט קניג. אם לכל i \in A בוחרים  \kappa_i = 1 ו- \mu_i = 2, אז ממשפט קניג נקבל:

|A| = \sum_{i\in A} 1<\prod_{i\in A} 2 = 2^{|A|}

משפט קניג מניח את אקסיומת הבחירה, ולמעשה שקול לה.

מגדירים את הקופינליות של עוצמה \kappa בתור העוצמה הקטנה ביותר |I| שמקיימת את התנאי הבא: לכל i \in I קיימת עוצמה \lambda_i < \kappa כך שמתקיים: \kappa = \sum_{i \in I} \lambda_i. מסמנים את הקופינליות של \kappa בסימון \mathrm{cf}(\kappa). נשים לב שתמיד ניתן לבחור |I| = \kappa, ואז \kappa = \sum_{i \in I} 1. לכן תמיד מתקיים \mathrm{cf}(\kappa) \le \kappa.

ממשפט קניג נובע מיד ש- \kappa < \kappa^{\mathrm{cf}(\kappa)} (בוחרים את A ממשפט קניג להיות I מהגדרת הקופינליות). מהזהות האחרונה נקבל שלכל קבוצה אינסופית A מתקיים |A|<\mathrm{cf}\left(2^{|A|}\right). ההוכחה נעשית בדרך השלילה:

נניח בשלילה |A|\ge\mathrm{cf}\left(2^{|A|}\right). אז לפי הזהות האחרונה נקבל את הסתירה:
2^{|A|}<\left(2^{|A|}\right)^{cf\left(2^{|A|}\right)}\le\left(2^{|A|}\right)^{|A|}=2^{|A|\cdot|A|}=2^{|A|}

קיבלנו שלקבוצות אינסופיות מתקיים האי-שוויון החזק |A|<\mathrm{cf}\left(2^{|A|}\right). זהו אי-שוויון חזק יותר מאשר משפט קנטור משום ש-\mathrm{cf}\left(2^{|A|}\right)\le 2^{|A|}, וייתכנו מקרים בהם \mathrm{cf}\left(2^{|A|}\right)<2^{|A|}.

תוצאות אנלוגיות למשפט קנטור מראות אי קיום איזומורפיזם בין מבנים מסוימים לבין מבנים המורכבים מתת-מבנים שלהם (למשל קבוצות סדורות[13][14]). משפט קנטור מתקבל לעתים כמקרה פרטי של משפטים כאלה, כאשר נבחר מבנה טריוויאלי, כך שאוסף התת-מבנים הוא קבוצת החזקה וכל פונקציה חד-חד-ערכית ועל היא איזומורפיזם.

היסטוריה[עריכת קוד מקור | עריכה]

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

ב-1891 פרסם קנטור מאמר בגרמנית בשם "Über eine elementare Frage der Mannigfaltigkeitslehre" ("על שאלה אלמנטרית בתורת הקבוצות").‏[15] במאמר מופיע האלכסון של קנטור, ומיד לאחריו כתב קנטור:‏[16][17]

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

לאחר מכן פונה קנטור להוכחת המשפט. ההוכחה המקורית של קנטור זהה במהותה להוכחה המוכרת כיום, אך היא נוסחה בצורה שונה במעט. במקור קנטור הראה שאין התאמה חד-חד-ערכית ועל בין A לבין קבוצת הפונקציות המציינות של A (כאמור נוסח זה שקול לנוסח על קבוצת החזקה). קנטור טען שאילו הייתה התאמה כזו, הרי שהייתה קיימת פונקציה דו-מקומית \phi(a,x), כך שלכל פונקציה מציינת f(x) שהותאם לה האיבר a מתקיים: \phi(a,x) = f(x). כעת קנטור בונה פונקציה מציינת g(x) שמוגדרת כהיפך מ-\phi(x,x) (ניתן להגדיר כך: g(x) = 1-\phi(x,x)). לפי ההנחה קיים d \in A כך ש-\phi(d,x) = g(x), ולכן מקבלים סתירה: \phi(d,d) = g(d) \ne \phi(d,d).‏‏[16][17]

לנוסח המודרני של ההוכחה אחראי ארנסט צרמלו. משפט קנטור והוכחתו מופיעים במאמר של צרמלו משנת 1908 שבו ייסד את תורת הקבוצות האקסיומטית.‏[18][19] צרמלו הוא גם זה שקרא למשפט על שמו של קנטור.

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]

  • Nikolai Konstantinovich Vereshchagin, Alexander Shen, Basic set theory, p. 24-30, American Mathematical Soc., 2002, ISBN 0821827316
  • Robert Lawson Vaught, Set theory: an introduction, p. 53-54, Springer, 2001, ISBN 0817642560

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ ההגדרה המעורפלת של קבוצה בערך זה שייכת לתורת הקבוצות הנאיבית. הגדרה זו בעייתית (כמוסבר בהמשך הערך), והיא הוחלפה בהגדרה מדויקת במסגרת תורת הקבוצות האקסיומטית. בכל זאת, בערך זה נשתמש בגישה הנאיבית משום שהיא פשוטה יותר להבנה. כל התוצאות בערך זה נכונות גם בתורת הקבוצות האקסיומטית, למעט דקויות שידונו במהלך הערך.
  2. ^ שקילות היא תכונה רפלקסיבית, סימטרית, וטרנזיטיבית, אבל מסיבות פורמליות שלא נכנס אליהן כאן, היא אינה יחס שקילות (או יחס בכלל).
  3. ^ כמקודם, תכונה זו מקיימת את האקסיומות המגדירות יחס סדר, אבל פורמלית היא אינה יחס.
  4. ^ למעשה זו אחת ההגדרות למושג "קבוצה אינסופית"; ראו אינסופיות לפי דדקינד.
  5. ^ כבר בשלב הזה מתקבלת סתירה במקרה שבו A היא הקבוצה הריקה, שכן לא ייתכן שהאיבר d קיים. ואכן קבוצת החזקה של הקבוצה הריקה כוללת איבר אחד (הקבוצה הריקה עצמה), בעוד הקבוצה הריקה לא כוללת איברים כלל.
  6. ^ על שם גראוצ'ו מרקס, שאמר "אני לא מוכן להיות חבר במועדון המוכן לקבל אנשים כמוני".
  7. ^ המספר 0 נחשב למספר טבעי במסגרת ערך זה.
  8. ^ ישנו קושי אחד המעיב על ההתאמה הזו: אמנם כל סדרת ספרות בינאריות מייצגת תת-קבוצה אחת ויחידה של \mathbb{N}, אולם בממשיים המצב מעט שונה. לכל מספר ממשי שיש לו פיתוח סופי בבסיס בינארי, ישנם שני ייצוגים שונים כסדרות של ספרות. אחד הנגמר באינסוף אפסים, ואחר הנגמר באינסוף אחדות (ראו 0.999... להסבר התופעה). קושי זה אינו מהווה מכשול אמיתי שכן הופעות כפולות הן זניחות בהתאמות אינסופיות (אם |A| עוצמה אינסופית, אז 2|A|=|A|).
  9. ^ קיומו של הקידוד נובע למעשה מהעובדה שקבוצת המילים האפשריות בשפה כלשהי היא קבוצה בת-מנייה.
  10. ^ ניתן להראות זאת בעזרת אריתמטיקה של עוצמות בצורה דומה למקרה |\mathbb{R}^{\mathbb{Q}}| = 2^{\aleph_0}. דרך אחרת היא להבחין כי הגרף הקרטזי של כל פונקציה f: \mathbb{R} \to \mathbb{R} הוא תת-קבוצה של המישור האוקלידי \mathbb{R}^2, ולכן  |\mathbb{R}^{\mathbb{R}}| \le |\mathcal{P}(\mathbb{R}^2)| = 2^{\aleph}.
  11. ^ לרוב מוסיפים למערכת גם את אקסיומת הבחירה, אך זו אינה רלוונטית לדיוננו.
  12. ^ M. Randall Holmes, Elementary Set Theory with a Universal Set
  13. ^ A generalized Cantor theorem
  14. ^ Complete Lattices and the Generalized Cantor Theorem
  15. ^ מילולית, המילה "Mannigfaltigkeitslehre" שבה משתמש קנטור במובן של "תורת הקבוצות" משמעה "תורת היריעות". השימוש של קנטור במונח מעיד ככל הנראה על ההשראה ששאב מעבודתו של ברנהרד רימן. קנטור מתחיל להשתמש במונח "Mengenlehre" שמשמעו "קבוצה" רק ב-1895. להרחבה ראו Labyrinth of thought: a history of set theory and its role in modern mathematics, עמודים 39 ו-72, ISBN 3764383496.
  16. ^ 16.0 16.1 גאורג קנטור, "Über eine elementare Frage der Mannigfaltigkeitslehre"‏, Jahresbericht der Deutschen Math. Vereinigung I, 278-281, 1891
  17. ^ 17.0 17.1 הקטע הרלוונטי מתוך המאמר
  18. ^ ארנסט צרמלו,‏ "Untersuchungen über die Grundlagen der Mengenlehre I",‏ Mathematische Annalen 65 (2), 276,‏ 1908
  19. ^ הקטע הרלוונטי מתוך המאמר
ערך מומלץ
Article MediumPurple.svg