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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

תורת הקבוצות