לכסון (שיטת הוכחה)

Nuvola apps edu mathematics blue-p.svg

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

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

אופן ההוכחהעריכה

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

1.נניח בשלילה ש  בת מנייה, זאת אומרת שקיימת לקבוצה מנייה (פונקציה מהטבעיים ל ). נסמן מנייה זו  .

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

3.נוכיח שאכן מתקיים .

4.נשים לב שלכל  , מתקיים   (כפי שבנינו את  ).

5. מכאן יש איבר ב-  שאינו במנייה, אך זוהי סתירה להגדרת האחרונה. לכן  לא בת מנייה, קרי,  <  , כנדרש.

האלכסון של קנטורעריכה

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

ההוכחה מתחילה בהנחה בשלילה שהקבוצה   היא בת מנייה, זאת אומרת שקיימת לה מנייה  .

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

קנטור יצר מספר   בקטע   ששונה מכל המספרים במנייה של  , באופן הבא:  

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

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

קישורים חיצונייםעריכה