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

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

לכסון הוא כלי הוכחה נפוץ בתורת הקבוצות אשר השימוש העיקרי שנעשה בו הוא הפרכת היותן של קבוצות בנות מנייה, זאת אומרת הוכחה שעוצמתן גדולה ממש מ${\displaystyle \!\ \aleph _{0}}$ . השימוש המפורסם ביותר של השיטה הוא באלכסון של קנטור, אך יש לציין שפול דו בואה ריימון עשה בה שימוש כבר ב1875.

אופן ההוכחה

תהי${\displaystyle \!\ X}$ קבוצה. מטרתנו להוכיח ש${\displaystyle \aleph _{0}}$ < ${\displaystyle |X|}$.

1.נניח בשלילה ש${\displaystyle \!\ X}$ בת מנייה, זאת אומרת שקיימת לקבוצה מנייה (פונקציה מהטבעיים ל${\displaystyle \!\ X}$). נסמן מנייה זו ${\displaystyle \!\ \langle x_{n}\mid n\in \mathbb {N} \rangle }$.

2.נבנה איבר ${\displaystyle \!\ x}$ מתוך איברי המנייה כך שהוא שונה מכל איבר בה. באלכסון של קנטור, למשל, בונים מספר ${\displaystyle \!\ r}$ ב קטע הפתוח ${\displaystyle \!\ (0,1)}$, כך שלכל ${\displaystyle \!\ n\in \mathbb {N} }$, הספרה באינדקס ${\displaystyle \!\ n}$ אחרי הנקודה מוגדרת להיות שונה מהספרה באינדקס ה-${\displaystyle \!\ n}$ של${\displaystyle \!\ r_{n}}$ במנייה (לכאורה) של ${\displaystyle \!\ (0,1)}$.

3.נוכיח שאכן מתקיים${\displaystyle \!\ x\in X}$.

4.נשים לב שלכל ${\displaystyle \!\ n\in \mathbb {N} }$, מתקיים ${\displaystyle \!\ x\neq x_{n}}$ (כפי שבנינו את ${\displaystyle \!\ x}$).

5. מכאן יש איבר ב-${\displaystyle \!\ X}$ שאינו במנייה, אך זוהי סתירה להגדרת האחרונה. לכן${\displaystyle \!\ X}$ לא בת מנייה, קרי,${\displaystyle \aleph _{0}}$ < ${\displaystyle |X|}$, כנדרש.

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

הדוגמה המפורסמת ביותר לשימוש בלכסון היא האלכסון של קנטור, המשמש להוכחה שעוצמת המספרים הממשיים גדול ממש מעוצמת המספרים הטבעיים. קנטור הוכיח זאת בהתבסס על כך ש${\displaystyle \!\ |\mathbb {R} |=|(0,1)|}$ (למשל, הפונקציה ${\displaystyle \!\ f:(0,1)\rightarrow \mathbb {R} ,x\mapsto tan(\pi \cdot x-{\frac {\pi }{2}}))}$ היא חד חד ערכית ועל ולכן מתקיים השוויון).

ההוכחה מתחילה בהנחה בשלילה שהקבוצה ${\displaystyle \!\ (0,1)}$ היא בת מנייה, זאת אומרת שקיימת לה מנייה ${\displaystyle \!\ \langle x_{n}\mid n\in \mathbb {N} \rangle }$.

ידוע שלכל מספר יש פיתוח עשרוני יחיד (עד כדי החלפת זנב של תשיעיות בזנב של אפסים), ולכן עבור ${\displaystyle \!\ r\in (0,1)}$ נסמן ${\displaystyle \!\ r=0.r^{(0)}r^{(1)}...}$.

קנטור יצר מספר ${\displaystyle \!\ r=0.r^{(0)}r^{(1)}r^{(2)}...}$ בקטע ${\displaystyle \!\ (0,1)}$ ששונה מכל המספרים במנייה של ${\displaystyle \!\ (0,1)}$, באופן הבא: ${\displaystyle \forall n\in \mathbb {N} ~r^{(n)}=\left\{{\begin{matrix}1&r_{n}^{(n)}=7\\7&r_{n}^{(n)}\neq 7\end{matrix}}\right.}$

כאשר ${\displaystyle \!\ r_{n}^{(n)}}$ היא הספרה באינדקס ה${\displaystyle \!\ n}$ אחרי הנקודה ב${\displaystyle \!\ r_{n}}$ (למשל, אם נניח ${\displaystyle \!\ r_{3}=0.672...}$ אז ${\displaystyle \!\ r_{3}^{(0)}=6,r_{3}^{(1)}=7,r_{3}^{(2)}=2}$ וכן הלאה. למעשה, 'סידרנו' את המנייה בשורות ויצרנו את ${\displaystyle \!\ r}$ בעזרת האלכסון שהתקבל בסידור זה, ומכאן שם השיטה.)

בבירור ${\displaystyle \!\ r\in (0,1)}$, אך היות שבהכרח ${\displaystyle \!\ \forall n\in \mathbb {N} ~r^{(n)}\neq r_{n}^{(n)}}$ מתקבל ${\displaystyle \!\ \forall n\in \mathbb {N} ~r\neq r_{n}}$ ומכאן ${\displaystyle \!\ r}$ לא במנייה. זו סתירה, ולכן מנייה כזו לא קיימת. מכאן ${\displaystyle \!\ |(0,1)|\neq \aleph _{0}}$, זאת אומרת ${\displaystyle \!\ |\mathbb {R} |\neq \aleph _{0}}$.

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

• גדי אלכסנדרוביץ', אז מדוע קשה להוכיח ש-P שונה מ-NP? (בלכסון), באתר "לא מדויק", 16 באוגוסט 2010