ויקיפדיה

לכסון (שיטת הוכחה) – הבדלי גרסאות

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
WilesStan93 (שיחה | תרומות)
13 עריכות
מ החלפות ( היות ש, ]] )
שורה 1:
{{סימון מתמטי}}
לכסון הוא כלי הוכחה נפוץ ב[[תורת הקבוצות]] אשר השימוש העיקרי שנעשה בו הוא הפרכת היותן של קבוצות [[קבוצה בת מנייה | בנות מנייה]], זאת אומרת הוכחה ש[[עוצמה (מתמטיקה) |עוצמתן]] גדולה ממש מ[[אלף אפס|<math> \!\ \aleph_0 </math> ]] . השימוש המפורסם ביותר של השיטה הוא ב[[האלכסון של קנטור |אלכסון של קנטור]], אך יש לציין ש[[פול דו בואה ריימון]] עשה בה שימוש כבר ב[https://gdz.sub.uni-goettingen.de/id/PPN235181684_0008 1875].
 
==אופן ההוכחה==
תהי <math> \!\ X </math> קבוצה. מטרתנו להוכיח ש [[אלף אפס| <math> \aleph_0 </math> ]] < <math> |X| </math>.
 
1.נניח בשלילה ש<math> \!\ X </math> [[קבוצה בת מנייה | בת מנייה]], זאת אומרת שקיימת לקבוצה מנייה (פונקציה מ[[מספרים טבעיים|הטבעיים]] ל<math> \!\ X </math>). נסמן מנייה זו <math> \!\ \langle x_n \mid n \in \mathbb{N} \rangle </math>.
 
2.נבנה איבר <math> \!\ x </math> מתוך איברי המנייה כך שהוא שונה מכל איבר בה. באלכסון של קנטור, למשל, בונים מספר <math> \!\ r </math> ב[[קטע (מתמטיקה) | קטע הפתוח]] <math> \!\ (0,1) </math>, כך שלכל <math> \!\ n \in \mathbb{N} </math>, הספרה באינקדס <math> \!\ n </math> אחרי הנקודה מוגדרת להיות שונה מהספרה באינדקס ה-<math> \!\ n </math> של <math> \!\ r_n </math> במנייה (לכאורה) של <math> \!\ (0,1) </math>.
 
3. נוכיח שאכן מתקיים <math> \!\ x \in X </math>.
 
4.נשים לב שלכל <math> \!\ n \in \mathbb{N} </math>, מתקיים <math> \!\ x \neq x_n </math> (כפי שבנינו את <math> \!\ x </math>).
 
5. מכאן יש איבר ב-<math> \!\ X </math> שאינו במנייה, אך זוהי סתירה להגדרת האחרונה. לכן לא קיימת מנייה של <math> \!\ X </math>, זאת אומרת [[אלף אפס| <math> \aleph_0 </math> ]] < <math> |X| </math> כנדרש.
 
== האלכסון של קנטור ==
שורה 19:
הדוגמה המפורסמת ביותר לשימוש בלכסון היא [[האלכסון של קנטור]], המשמש להוכחה שעוצמת ה[[מספר ממשי |מספרים הממשיים]] גדול ממש מעוצמת ה[[ מספר טבעי |מספרים הטבעיים]]. קנטור הוכיח זאת בהתבסס על כך ש<math> \!\ | \mathbb{R} | = |(0,1)| </math> (למשל, הפונקציה <math> \!\ f: (0,1) \rightarrow \mathbb{R}, x \mapsto tan(\pi \cdot x-\frac{\pi}{2})) </math> היא [[פונקציה חד-חד-ערכית ועל |חד חד ערכית ועל]] ולכן מתקיים השוויון).
 
ההוכחה מתחילה בהנחה בשלילה שהקבוצה <math> \!\ (0,1) </math> היא [[ קבוצה בת מנייה |בת מנייה]] , זאת אומרת שקיימת לה מנייה
<math> \!\ \langle x_n \mid n \in \mathbb{N} \rangle </math>.
 
ידוע שלכל מספר יש פיתוח עשרוני יחיד (עד כדי החלפת זנב של תשיעיות בזנב של אפסים), ולכן עבור <math> \!\ r \in (0,1) </math> נסמן <math> \!\ r = 0.r^{(0)}r^{(1)}... </math>.
 
קנטור יצר מספר <math> \!\ r = 0.r^{(0)}r^{(1)}r^{(2)}... </math> בקטע <math> \!\ (0,1) </math> ששונה מכל המספרים במנייה של <math> \!\ (0,1) </math>, באופן הבא:
<math>\forall n \in \mathbb{N}~ r^{(n)} =\left\{ \begin{matrix} 1 & r_n^{(n)}=7 \\ 7 & r_n^{(n)} \neq 7 \end{matrix} \right.</math>
 
כאשר <math> \!\ r_n^{(n)} </math> היא הספרה באינדקס ה<math> \!\ n </math> אחרי הנקודה ב<math> \!\ r_n </math> (למשל, אם נניח
<math> \!\ r_3=0.672... </math> אז <math> \!\ r_3^{(0)} = 6, r_3^{(1)}=7, r_3^{(2)} =2 </math> וכן הלאה.
למעשה, 'סידרנו' את המנייה בשורות ויצרנו את <math> \!\ r </math> בעזרת האלכסון שהתקבל בסידור זה, ומכאן שם השיטה.
 
בבירור <math> \!\ r \in (0,1) </math>, אך היות ובהכרחשבהכרח <math> \!\ \forall n \in \mathbb{N}~ r^{(n)} \neq r_n^{(n)} </math> מתקבל <math> \!\ \forall n \in \mathbb{N}~ r \neq r_n </math> ומכאן <math> \!\ r </math> לא במנייה. זו סתירה, ולכן מנייה כזו לא קיימת. מכאן <math> \!\ |(0,1)| \neq \aleph_0 </math>, זאת אומרת <math> \!\ |\mathbb{R}| \neq \aleph_0 </math>.
אוחזר מתוך "https://he.wikipedia.org/wiki/לכסון_(שיטת_הוכחה)"