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

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

גילוי הוכחה

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

קנטור פרסם את ממצאיו ב-1874 במאמר בגרמנית בשם Über eine Eigenschaft des Ingebriffes aller reelen algebraischen Zahlen שניתן לתרגמו "על תכונות אופייניות של מספרים אלגבראיים ממשיים".

ההוכחה

הוכחתו של קנטור נחלקת לשלושה חלקים:

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

המספרים האלגבריים בני מנייה

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

$\ \operatorname{height}(P(x)) = n+|a_n|+|a_{n-1}|+\ldots +|a_0| - 1;\quad P(x) = a_nx^n+a_{n-1}x^{n-1}+\ldots +a_0$

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

המספרים הממשיים אינם בני מנייה

בחלק זה מראה קנטור שלכל סדרה של מספרים ממשיים בקטע נתון ניתן למצוא מספר בקטע שלא נמצא בסדרה ולכן לא קיימת סדרה של כל הממשיים בקטע. לכל סדרה נתונה שכזו $\left\{x_n\right\}$ בקטע $\ [a,b]$ מגדיר קנטור סדרת קטעים באופן הבא: נסמן ב-$\ a_1$ וב-$\ b_1$ את שני המספרים הראשונים בסדרה שנמצאים בפנימו של הקטע $\ [a,b]$ כך שמתקיים $\ a<a_1<b_1<b$. המספרים $\ a_2, b_2$ יהיו המספרים הבאים בסדרה שנמצאים בפנימו של $\ [a_1,b_1]$, כלומר $\ a_1<a_2<b_2<b_1$. ממשיכים בתהליך הזה עד אינסוף באינדוקציה: $\ a_{n+1}, b_{n+1}$ הם המספרים הבאים בסדרה המקיימים $\ a_n<a_{n+1}<b_{n+1}<b_n$.

ייתכנו שתי תוצאות לתהליך: אפשרות ראשונה היא כי בשלב כלשהו התהליך ייעצר כי לא יימצאו בסדרה שני מספרים ששייכים לפנימו של קטע מסדרת הקטעים. במקרה כזה מתקבל קטע סופי $\ [a_N, b_N]$ שאין אף איבר סדרה בפנימו מלבד אולי איבר אחד, וכל מספר בפנים הקטע מלבדו בהכרח לא מופיע בסדרה.

אפשרות שנייה היא כי התהליך לא ייעצר לעולם. במקרה כזה קיים גבול: $A = \lim_{n \to \infty}a_n$ כי זוהי סדרה מונוטונית עולה וחסומה. בשלב זה יכול היה קנטור לסיים את ההוכחה בהבחנה כי לכל n, $\ A$ נמצא בקטע $\ [a_{n+1},b_{n+1}]$ בעוד ש-$\ x_n$ אינו בקטע הזה, ולכן $\ A \neq x_n$. במקום זאת מפצל קנטור את המקרה הזה לשני תת-מקרים:

קנטור מגדיר את $B = \lim_{n \to \infty}b_n$.

• אם $\ B=A$ אז הוא נמצא כאמור בכל קטע ולכן לא מופיע בסדרה. קנטור מבחין כי זה מה שמתרחש במקרה בו $\left\{x_n\right\}$ היא סדרת האלגבריים אותה הגדיר בחלק הראשון בהוכחה.
• אם $\ B>A$ הרי שכל איבר בקטע $\ (A,B)$ לא מופיע בסדרה.

יש דמיון רב בין הוכחה זו לבין הלמה של קנטור.

בניית מספר טרנסצנדנטי

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

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

ראו גם

• משפט קנטור

קישורים חיצוניים

• מאמרו המקורי של קנטור (בגרמנית)