לכסון (שיטת הוכחה)
בערך זה |
לכסון הוא כלי הוכחה נפוץ בתורת הקבוצות אשר השימוש העיקרי שנעשה בו הוא הפרכת היותן של קבוצות בנות מנייה, זאת אומרת הוכחה שעוצמתן גדולה ממש מ$ \!\ \aleph _{0} $ . השימוש המפורסם ביותר של השיטה הוא באלכסון של קנטור, אך יש לציין שפול דו בואה ריימון עשה בה שימוש כבר ב1875.
אופן ההוכחה
תהי$ \!\ X $ קבוצה. מטרתנו להוכיח ש$ \aleph _{0} $ < $ |X| $.
1.נניח בשלילה ש$ \!\ X $ בת מנייה, זאת אומרת שקיימת לקבוצה מנייה (פונקציה מהטבעיים ל$ \!\ X $). נסמן מנייה זו $ \!\ \langle x_{n}\mid n\in \mathbb {N} \rangle $.
2.נבנה איבר $ \!\ x $ מתוך איברי המנייה כך שהוא שונה מכל איבר בה. באלכסון של קנטור, למשל, בונים מספר $ \!\ r $ ב קטע הפתוח $ \!\ (0,1) $, כך שלכל $ \!\ n\in \mathbb {N} $, הספרה באינקדס $ \!\ n $ אחרי הנקודה מוגדרת להיות שונה מהספרה באינדקס ה-$ \!\ n $ של$ \!\ r_{n} $ במנייה (לכאורה) של $ \!\ (0,1) $.
3.נוכיח שאכן מתקיים$ \!\ x\in X $.
4.נשים לב שלכל $ \!\ n\in \mathbb {N} $, מתקיים $ \!\ x\neq x_{n} $ (כפי שבנינו את $ \!\ x $).
5. מכאן יש איבר ב-$ \!\ X $ שאינו במנייה, אך זוהי סתירה להגדרת האחרונה. לכן לא קיימת מנייה של $ \!\ X $, זאת אומרת,$ \aleph _{0} $ < $ |X| $ כנדרש.
האלכסון של קנטור
הדוגמה המפורסמת ביותר לשימוש בלכסון היא האלכסון של קנטור, המשמש להוכחה שעוצמת המספרים הממשיים גדול ממש מעוצמת המספרים הטבעיים. קנטור הוכיח זאת בהתבסס על כך ש$ \!\ |\mathbb {R} |=|(0,1)| $ (למשל, הפונקציה $ \!\ f:(0,1)\rightarrow \mathbb {R} ,x\mapsto tan(\pi \cdot x-{\frac {\pi }{2}})) $ היא חד חד ערכית ועל ולכן מתקיים השוויון).
ההוכחה מתחילה בהנחה בשלילה שהקבוצה $ \!\ (0,1) $ היא בת מנייה, זאת אומרת שקיימת לה מנייה $ \!\ \langle x_{n}\mid n\in \mathbb {N} \rangle $.
ידוע שלכל מספר יש פיתוח עשרוני יחיד (עד כדי החלפת זנב של תשיעיות בזנב של אפסים), ולכן עבור $ \!\ r\in (0,1) $ נסמן $ \!\ r=0.r^{(0)}r^{(1)}... $.
קנטור יצר מספר $ \!\ r=0.r^{(0)}r^{(1)}r^{(2)}... $ בקטע $ \!\ (0,1) $ ששונה מכל המספרים במנייה של $ \!\ (0,1) $, באופן הבא: $ \forall n\in \mathbb {N} ~r^{(n)}=\left\{{\begin{matrix}1&r_{n}^{(n)}=7\\7&r_{n}^{(n)}\neq 7\end{matrix}}\right. $
כאשר $ \!\ r_{n}^{(n)} $ היא הספרה באינדקס ה$ \!\ n $ אחרי הנקודה ב$ \!\ r_{n} $ (למשל, אם נניח $ \!\ r_{3}=0.672... $ אז $ \!\ r_{3}^{(0)}=6,r_{3}^{(1)}=7,r_{3}^{(2)}=2 $ וכן הלאה. למעשה, 'סידרנו' את המנייה בשורות ויצרנו את $ \!\ r $ בעזרת האלכסון שהתקבל בסידור זה, ומכאן שם השיטה.)
בבירור $ \!\ r\in (0,1) $, אך היות שבהכרח $ \!\ \forall n\in \mathbb {N} ~r^{(n)}\neq r_{n}^{(n)} $ מתקבל $ \!\ \forall n\in \mathbb {N} ~r\neq r_{n} $ ומכאן $ \!\ r $ לא במנייה. זו סתירה, ולכן מנייה כזו לא קיימת. מכאן $ \!\ |(0,1)|\neq \aleph _{0} $, זאת אומרת $ \!\ |\mathbb {R} |\neq \aleph _{0} $.
לכסון (שיטת הוכחה)34587125