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

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

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

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

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

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

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

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

נגדיר את הגובה של מספר אלגברי בתור הגובה של הפולינום המינימלי שלו.

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

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

בחלק זה מראה קנטור שלכל סדרה של מספרים ממשיים בקטע נתון ניתן למצוא מספר בקטע שלא נמצא בסדרה ולכן לא קיימת סדרה של כל הממשיים בקטע. לכל סדרה נתונה שכזו ${\displaystyle \left\{x_{n}\right\}}$ בקטע ${\displaystyle \ [a,b]}$ מגדיר קנטור סדרת קטעים באופן הבא: נסמן ב-${\displaystyle \ a_{1}}$ וב-${\displaystyle \ b_{1}}$ את שני המספרים הראשונים בסדרה שנמצאים בקטע הפתוח ${\displaystyle \ (a,b)}$, כך ש-${\displaystyle a_{1}<b_{1}}$. המספרים ${\displaystyle \ a_{2},b_{2}}$ יהיו המספרים הבאים בסדרה שנמצאים בקטע ${\displaystyle \ (a_{1},b_{1})}$ ומקיימים ${\displaystyle a_{2}<b_{2}}$. ממשיכים בתהליך הזה עד אינסוף באינדוקציה: ${\displaystyle \ a_{n+1},b_{n+1}}$ הם המספרים הבאים בסדרה הנמצאים בקטע ${\displaystyle \ (a_{n},b_{n})}$ ומקיימים ${\displaystyle a_{n+1}<b_{n+1}}$.

ייתכנו שתי תוצאות לתהליך: אפשרות ראשונה היא כי בשלב כלשהו התהליך ייעצר כי לא יימצאו בסדרה שני מספרים ששייכים לפנימו של קטע מסדרת הקטעים. במקרה כזה מתקבל קטע אחרון ${\displaystyle \ (a_{N},b_{N})}$ שאין בו אף איבר של סדרה, מלבד אולי איבר אחד, וכל מספר בפנים הקטע מלבדו בהכרח לא מופיע בסדרה.

אפשרות שנייה היא כי התהליך לא ייעצר לעולם. במקרה כזה קיים גבול: ${\displaystyle A=\lim _{n\to \infty }a_{n}}$ כי זוהי סדרה מונוטונית עולה וחסומה. בשלב זה יכול היה קנטור לסיים את ההוכחה בהבחנה כי לכל n, ${\displaystyle \ A}$ נמצא בקטע ${\displaystyle \ (a_{n},b_{n})}$ בעוד ש-${\displaystyle \ x_{n}}$ אינו בקטע זה, ולכן ${\displaystyle \ A\neq x_{n}}$. במקום זאת מפצל קנטור את המקרה הזה לשני תת-מקרים:

קנטור מגדיר את ${\displaystyle B=\lim _{n\to \infty }b_{n}}$.

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

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

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

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

• משפט קנטור

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