הצגת המקור של הדף "הוכחת האי-מנייה הראשונה של קנטור"

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

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

קנטור פרסם את ממצאיו ב-1874 במאמר ב[[גרמנית]] בשם ''Über eine Eigenschaft des Ingebriffes aller reelen algebraischen Zahlen'' שניתן לתרגמו "על תכונות אופייניות של מספרים אלגבראיים ממשיים".{{הערה|1=[[חיים שפירא (מתמטיקאי)|חיים שפירא]], אינסוף, עמ' 259}}

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

===המספרים האלגבריים בני מנייה===
ראשית קנטור מגדיר את ה"גובה" של [[פולינום]] כלשהו עם מקדמים [[מספר שלם|שלמים]] ומעלה חיובית להיות הסכום של [[מעלה (פולינום)|מעלת]] הפולינום עם הערכים המוחלטים של מקדמיו, פחות אחד:
:<math>\ \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</math> 

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

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

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

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

ייתכנו שתי תוצאות לתהליך: אפשרות ראשונה היא כי בשלב כלשהו התהליך ייעצר כי לא יימצאו בסדרה שני מספרים ששייכים לפנימו של קטע מסדרת הקטעים. במקרה כזה מתקבל קטע אחרון <math>\ (a_N, b_N)</math> שאין בו אף איבר של סדרה, מלבד אולי איבר אחד, וכל מספר בפנים הקטע מלבדו בהכרח לא מופיע בסדרה.

אפשרות שנייה היא כי התהליך לא ייעצר לעולם. במקרה כזה קיים [[גבול של סדרה|גבול]]: <math> A = \lim_{n \to \infty}a_n</math> כי זוהי [[סדרה מונוטונית]] עולה ו[[סדרה חסומה|חסומה]]. בשלב זה יכול היה קנטור לסיים את ההוכחה בהבחנה כי לכל n, <math>\ A</math> נמצא בקטע <math>\ (a_n,b_n)</math> בעוד ש-<math>\ x_n</math> אינו בקטע זה, ולכן <math>\ A \neq x_n</math>. במקום זאת מפצל קנטור את המקרה הזה לשני תת-מקרים:

קנטור מגדיר את <math> B = \lim_{n \to \infty}b_n</math>.
* אם <math>\ B=A</math> אז הוא נמצא כאמור בכל קטע ולכן לא מופיע בסדרה. קנטור מבחין כי זה מה שמתרחש במקרה בו <math>\left\{x_n\right\}</math> היא סדרת האלגבריים אותה הגדיר בחלק הראשון בהוכחה.
* אם <math>\ B>A</math> הרי שכל איבר בקטע <math>\ (A,B)</math> לא מופיע בסדרה.

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

==בניית מספר טרנסצנדנטי==
הוכחת קנטור מספקת דרך לבנות מספר טרנסצנדנטי בכל קטע שהוא. לשם כך בונים סדרה של כל המספרים האלגבריים בקטע (החלק הראשון של ההוכחה מדגים דרך אחת לעשות זאת). כעת עוקבים אחר התהליך בהוכחת קנטור, ולפיה הגבול <math>\ A</math> המתקבל הוא בהכרח מספר טרנסצנדנטי (לא ייתכן המקרה הראשון בשל [[קבוצה צפופה|צפיפות]] האלגבריים). על ידי בחינת איברים הולכים וגדלים בסדרה נוכל לחשב את <math>\ A</math> בכל רמת דיוק שנרצה.

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

==ראו גם==
*[[משפט קנטור]]

==קישורים חיצוניים==
*[http://www.digizeitschriften.de/main/dms/img/?PPN=GDZPPN002155583 מאמרו המקורי של קנטור] {{גרמנית}}

==הערות שוליים==
{{הערות שוליים|יישור=ימין}}

[[קטגוריה:תורת הקבוצות]]
[[קטגוריה:אינסוף]]
[[קטגוריה:הוכחות]]
[[קטגוריה:מספרים טרנסצנדנטיים]]
[[קטגוריה:משפטים בתורת הקבוצות|אי-מנייה הראשונה של קנטור]]