מי אני ומי אתם מפת דרכים רשימת ציוד
מהות שיטת הלמידה המיטבית סוגי השאלות
טענות כללי היסק
הוכחות לפי הגדרה הוכחות בעזרת הגדרה הוכחות בעזרת משפטים סיכום
רציפות במידה שווה פולינומי טיילור קמירות
אובדן התמימות שלוש אבני היסוד רעיונות למימוש משפרי ביצועים סיכום
תוספות ☰
cover image

חדו"א 1
יד ביד

כתיבת הוכחות - חלק 2

הוכחות בעזרת הגדרה

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

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

דוגמה – שימוש בהגדרת הגבול

הוכיחו כי אם ana_{n} סדרה אי-שלילית (an≥0)\left(a_{n}\ge0\right) המקיימת lim⁡n→∞an=L\lim_{n\to\infty}a_{n}=L כאשר L>0L>0, אזי lim⁡n→∞an=L\lim_{n\to\infty}\sqrt{a_{n}}=\sqrt{L}

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

תכנית משחק

אנחנו יודעים לפי כלל הברזל שנפתח את ההוכחה ב”יהי ε>0\varepsilon>0”. למה? כי אנחנו צריכים להוכיח שתופעה מסוימת מתקיימת לכל ε>0\varepsilon>0. בשלב הבא צריך למצוא את ה-NN שהחל ממנו (כלומר n>Nn>N) מתקיימת התופעה. מה עשינו עד כה? מחקר.

מחקר

על מנת למצוא את ה-NN הדרוש, נסתכל על המסקנה המתבקשת ∣an−L∣<ε\left|\sqrt{a_{n}}-\sqrt{L}\right|<\varepsilon כמו בתרגיל הקודם, פתרון אי-שיווין כזה עלול להיות מייגע עד כדי בלתי-אפשרי. לכן נשתמש שוב ב”טיפול שורש” ∣an−L∣=∣an−Lan+L∣=∣an−L∣an+L\left|\sqrt{a_{n}}-\sqrt{L}\right|=\left|\frac{a_{n}-L}{\sqrt{a_{n}}+\sqrt{L}}\right|=\frac{\left|a_{n}-L\right|}{\sqrt{a_{n}}+\sqrt{L}} על מנת לפשט את הביטוי הימני אפילו יותר, אפשר להשתמש בעובדה ש-an≥0a_{n}\ge0 ולכן an≥0\sqrt{a_{n}}\ge0 ∣an−L∣=∣an−L∣an+L<∣an−L∣L\left|\sqrt{a_{n}}-\sqrt{L}\right|=\frac{\left|a_{n}-L\right|}{\sqrt{a_{n}}+\sqrt{L}}<\frac{\left|a_{n}-L\right|}{\sqrt{L}} וכמובן אנו רוצים כי המרחק בין הסדרה an\sqrt{a_{n}} לגבול שלה L\sqrt{L} יהיה קטן מ-ε\varepsilon ועל כן נדרוש ∣an−L∣L<ε⟺∣an−L∣<L⋅ε\frac{\left|a_{n}-L\right|}{\sqrt{L}}<\varepsilon\Longleftrightarrow\left|a_{n}-L\right|<\sqrt{L}\cdot\varepsilon אבל רגע, למה שבכלל אי-השיוויון מימין יתקיים?

מהמחקר הקטן שערכנו (וטרם סיימנו) אנו רואים שכדי לדאוג ש-∣an−L∣\left|\sqrt{a_{n}}-\sqrt{L}\right| יהיה קטן מ-ε\varepsilon אז צריך לדאוג ש-∣an−L∣\left|a_{n}-L\right| יהיה קטן מ-ε⋅L\varepsilon\cdot\sqrt{L}. ואיך בדיוק נדאג לכך? הרי אנחנו לא באמת יודעים מה היא הסדרה שלנו ana_{n}, או בכלל מה הוא הגבול LL.

אבל… אנחנו כן יודעים עליה משהו. אנחנו יודעים שהסדרה שלנו ana_{n} שואפת למספר LL, ולכן אנחנו יכולים לדאוג שהיא תהיה קרובה למספר LL כמה שאנחנו רוצים, החל מאינדקס מסוים. כלומר אנחנו יכולים לדאוג שהביטוי ∣an−L∣\left|a_{n}-L\right| יהיה קטן מכל מה שנרצה החל ממקום מסוים. בפרט, אם נרצה שהוא יהיה קטן מ-ε⋅L\varepsilon\cdot\sqrt{L} אז אנו יודעים שקיים איזה NN חביב שלכל האינדקסים שגדולים ממנו יתקיים ∣an−L∣<ε⋅L\left|a_{n}-L\right|<\varepsilon\cdot\sqrt{L} ואם אי-השיוויון לעיל מתקיים, אז גם אי-השיוויון שאנו רוצים – ∣an−L∣<ε\left|\sqrt{a_{n}}-\sqrt{L}\right|<\varepsilon – יתקיים (לפי המחקר). אולי ריבוי האפסילונים פה קצת מבלבל. תשארו איתי בדוגמה הזו ובדוגמה הבאה, מבטיח שזה נהיה ברור יותר :)

שמתם לב מה קרה פה? כדי להוכיח את ההגדרה שלנו על an\sqrt{a_{n}} נאלצנו להעזר בהגדרת הגבול שאנחנו יודעים על הסדרה ana_{n}. על כן שאלה זו היא לא רק הוכחה לפי הגדרה, אלא גם בעזרת הגדרה.

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

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

מתכון הסילוגיזם לשימוש בהגדרות

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

  1. נרשום תחילה סילוגיזם: הטענה הראשית לסילוגיזם שלנו תהיה ההגדרה בה אנו רוצים להשתמש.
  2. לאחר מכן נרכיב בעצמנו טענה משנית שיכולה להתאים לסילוגיזם. הטענה המשנית יכולה להיות כללית (בצורת “יהי משהו”) או ספציפית (בצורת “עבור המשהו הספציפי”).
  3. נרכיב גם מסקנה מתאימה לסילוגיזם.

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

טענה משנית. לכן לפי שם הטענה הראשית מתקיים מסקנה.

קצת באוויר, אני יודע. בואו ניישם את מתכון הסילוגיזם להגדרות על המקרה שלנו. במקרה שלנו אנו רוצים להשתמש בעובדה lim⁡n→∞an=L\lim_{n\to\infty}a_{n}=L על מנת להסיק כי קיים NN כך שלכל n>Nn>N מתקיים ∣an−L∣<L⋅ε\left|a_{n}-L\right|<\sqrt{L}\cdot\varepsilon. לכן הטענה הראשית בסילוגיזם שלנו תהיה הגדרת הגבול של ana_{n}.

עתה עלינו לבנות טענה משנית ומסקנה שמתאימים לטענה הראשית. אם הגדרת הגבול היא הטענה הראשית, מה יכולה להיות טענה משנית? הסוד לפתירת החידה הוא לשמור על טכניות ולהקטין ראש. כשהטענה הראשית בפרק הלוגיקה הייתה “לכל בעל רכב קיים ביטוח חובה לרכב” הטענה המשנית הציגה לנו בעל רכב. לפיכך, אם הטענה הראשית שלנו עכשיו היא “לכל ε>0\varepsilon>0 קיים NN שעושה א’,ב’,ג’,…” הטענה המשנית שלנו צריכה להציג אפסילון חיובי. במילים אחרות, אנחנו צריכים להציג הגבלת מרחק. אבל איזו הגבלה נבחר? זה כבר הבנו מהמחקר: L⋅ε\sqrt{L}\cdot\varepsilon. לכן הטענה המשנית שלנו תהיה מהצורה “עבור 0<L⋅ε0<\sqrt{L}\cdot\varepsilon”3.

לבסוף, בהניתן הטענה הראשית והטענה המשנית שלנו, אנחנו צריכים לחשוב מה תהיה המסקנה. קביעת המסקנה בסילוגיזם היא החלק הקל כי בדרך כלל פשוט מעתיקים את המסקנה מההגדרה (הטענה הראשית). המסקנה תהיה “קיים NN כך שלכל n>Nn>N מתקיים ∣an−L∣<L⋅ε\left|a_{n}-L\right|<\sqrt{L}\cdot\varepsilon”. שימו לב שהמסקנה היא קיום של NN ספציפי. (המסקנה גם מתארת מה מקיים אותו ה-NN.)

דבר אחד נותר להבהיר על מנת להשתמש במתכון: מה זה שם הטענת הראשית? האמת שזה די אינטואיטיבי. שם הטענה הראשית הוא השם שאתם והבוחנים שלכם מכנים את הטענה בה אנו משתמשים. במקרה שלנו שם הטענה הראשית הוא “הגדרת הגבול” או “הגדרת הגבול של ana_{n}” ליתר דיוק.

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

“עבור 0<L⋅ε0<\sqrt{L}\cdot\varepsilon, לפי הגדרת הגבול של ana_{n}, קיים NN כך שלכל n>Nn>N מתקיים ∣an−L∣<L⋅ε\left|a_{n}-L\right|<\sqrt{L}\cdot\varepsilon”

ומאותו רגע, ה-NN שקיבלנו מהמסקנה הופך להיות מוחשי ואמיתי, ואנחנו יכולים להשתמש בו כדי להוכיח כל מה שנרצה.

ואיך יראה המשך ההוכחה? זו עדיין הוכחה לפי הגדרה, ולכן נעקוב אחרי ההגדרה. ראשית נגדיר ε\varepsilon חיובי כלשהו לפי כלל הברזל. לאחר מכן, נשתמש במתכון הסילוגיזם כדי למצוא את ה-NN הגדול. נגדיר שוב, לפי כלל הברזל, איזה אינדקס n>Nn>N. לבסוף, נראה כי עבור אינדקס כזה מתקיימת המסקנה הדרושה ∣an−L∣<ε\left|\sqrt{a_{n}}-\sqrt{L}\right|<\varepsilon.

הוכחה
  1. יהי ε>0\varepsilon>0.
  2. עבור 0<L⋅ε0<\sqrt{L}\cdot\varepsilon, לפי הגדרת הגבול של ana_{n}, קיים NN כך שלכל n>Nn>N מתקיים ∣an−L∣<L⋅ε\left|a_{n}-L\right|<\sqrt{L}\cdot\varepsilon
  3. יהי n>Nn>N.
  4. מתקיים ∣an−L∣=∣an−Lan+L∣=∣an−L∣an+L<⏟an≥0∣an−L∣L<L⋅εL=ε\left|\sqrt{a_{n}}-\sqrt{L}\right|=\left|\frac{a_{n}-L}{\sqrt{a_{n}}+\sqrt{L}}\right|=\frac{\left|a_{n}-L\right|}{\sqrt{a_{n}}+\sqrt{L}}\underbrace{<}_{\mathclap{a_{n}\ge0}}\frac{\color{orange}\left|a_{n}-L\right|}{\sqrt{L}}<\frac{\color{orange}\sqrt{L}\cdot\varepsilon}{\sqrt{L}}=\varepsilon
  5. לכן lim⁡n→∞an=L\lim_{n\to\infty}\sqrt{a_{n}}=\sqrt{L}.
ניתוח ההוכחה

משפט 1 הוא בדיוק כלל הברזל. (שכחתם? הפרק הקודם לרשותכם.) משפט 2 הוא הסילוגזים על הגדרת הגבול של ana_{n} לפיו מוצאים את ה-NN. משפט 3 הוא כלל הברזל, הפעם על n>Nn>N. ומשפט 4 הוא המסקנה של ההגדרה. משפט 5, כמו מקודם, חותם את ההוכחה ואין לו משמעות לוגית.

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

לכל ε>0\varepsilon>0, קיים NN כך שלכל n>Nn>N מתקיים ∣an−L∣<ε\left|\sqrt{a_{n}}-\sqrt{L}\right|<\varepsilon

וההתאמה להוכחה שלנו היא:

לכל ε>0\varepsilon>0 ↔\leftrightarrow משפט 1

קיים NN ↔\leftrightarrow משפט 2

לכל n>Nn>N ↔\leftrightarrow משפט 3

∣an−L∣<ε\left|\sqrt{a_{n}}-\sqrt{L}\right|<\varepsilon ↔\leftrightarrow משפט 4

עכשיו, כדי לחזק את ההבנה, נראה עוד מספר דוגמאות.

דוגמה – שימוש בהגדרת הגבול 2

תהי ana_{n} סדרה ו-L∈RL\in\mathbb{R}. הוכיחו כי אם קיימת סדרה bnb_{n} אי-שלילית השואפת לאפס ומקיימת לכל n∈Nn\in\mathbb{N} ∣an−L∣<bn\left|a_{n}-L\right|<b_{n}, אזי lim⁡n→∞an=L\lim_{n\to\infty}a_{n}=L.

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

תכנית משחק

אנחנו מוכיחים כאן את הגבול של ana_{n} לפי הגדרת הגבול. ולכן נפתח את ההוכחה לפי כלל הברזל ב”יהי ε>0\varepsilon>0”. ואז נחפש את ה-NN הגדול בעזרת מחקר.

מחקר

כמו תמיד נסתכל על הפאנצ’ של ההגדרה (מה שצריך להוכיח): ∣an−L∣<ε\left|a_{n}-L\right|<\varepsilon טוב את אי-השיוויון הזה ככה סתם אין לנו סיכוי לפתור. אנחנו לא יודעים שום דבר ספציפית על ana_{n} שיאפשר לפתור את האי-שיוויון במתכונת הנוכחית. אבל, אנחנו כן יודע את העובדה הבאה ∣an−L∣<bn\left|a_{n}-L\right|<b_{n} ואם נדרוש ש-bnb_{n} תהיה קטנה מ-ε\varepsilon החל ממקום מסויים, אז ∣an−L∣\left|a_{n}-L\right| יהיה קטן מ-ε\varepsilon. אך למה ש-bnb_{n} תהיה קטנה מ-ε\varepsilon אם אנחנו אפילו לא יודעים מה היא? ובכן גבירותיי ורבותיי, זה עלול לקרות כי bnb_{n} שואפת ל-0. כלומר אנחנו רוצים להשתמש בהגדרת הגבול של bnb_{n}, וכשאנחנו אומרים את המילים “שימוש בהגדרה” אנחנו אומרים “סילוגיזם”.

בואו נזכר מה הוא מתכון הסילוגיזם, הפעם בקצרה.

מתכון הסילוגיזם לשימוש בהגדרות (בקצרה)

טענה משנית. לכן לפי שם הטענה הראשית מתקיים מסקנה.

הטענה הראשית שלנו, היא כאמור ההגדרה שאנו רוצים להשתשמש בה. במקרה הזה מדובר בהגדרת הגבול של bnb_{n}. הטענה המשנית, בהתאם לטענה הראשית, צריכה להציג לנו הגבלת מרחק (מסומן בהגדרה ב-ε\varepsilon). ובאיזו הגבלת מרחק נבחר? ובכן, הגדרת הגבול של bnb_{n} מגבילה לנו את המרחק של bnb_{n} באופן הבא: ∣bn−0∣<ε\left|b_{n}-0\right|<\varepsilon, וזה בדיוק מה שאנחנו צריכים.

איבדתי אותך, על איזה אפסילון אנחנו מדברים?

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

עכשיו שימו לב שאנחנו מוכיחים את הגבול של ana_{n} בעזרת הגדרת הגבול, ולכן אנחנו צריכים לדאוג שלכל הגבלת מרחק על איברי הסדרה ana_{n} מהגבול שלה LL נמצא מקום מסוים בסדרה שהחל ממנו מתקיימת ההגבלה. אבל, אנחנו מוכיחים את זה בעזרת הגדרת הגבול של bnb_{n}, וכטענה משנית אנחנו מציגים ל-bnb_{n} הגבלת מרחק.

את הגבלת המרחק עבור ana_{n} אנחנו מכנים באופן כללי ε>0\varepsilon>0 כי ככה נהוג. מה שלא טריוויאלי כאן, זה שהגבלת המרחק שאנחנו רוצים לבקש מ-bnb_{n} זה בדיוק אותו ה-ε\varepsilon שאמור להגביל את המרחק של ana_{n} מהגבול.

תשוו את המצב הזה לשאלה הקודמת. גם שם הוכחנו את הגבול של an\sqrt{a_{n}} לפי הגדרת הגבול, וגם נעזרנו בהגדרת הגבול של ana_{n}. רק ששם, הגבלת המרחק על an\sqrt{a_{n}} הייתה ε\varepsilon, והגבלת המרחק שאנחנו הצגנו ל-ana_{n} הייתה L⋅ε\sqrt{L}\cdot\varepsilon.

בחזרה לתכנית

איך נשתמש פה במתכון הסילוגיזם? הטענה המשנית שלנו תציג הגבלת מרחק על הסדרה bnb_{n} מהגבול שלה 00. כפי שראינו במחקר הקצרצר, הגבלת המרחק שנצטרך היא בדיוק זו שאנו רוצים להשתמש על ana_{n}, כלומר מה שמכונה ε\varepsilon. אז בהוכחה ניתן לכתוב בתור טענה משנית “עבור ה-0<ε0<\varepsilon”. שימו לב שאנחנו כבר מניחים שבתחילת השאלה מישהו הצהיר לנו על ε\varepsilon, למשל בפסוק “יהי 0<ε0<\varepsilon” שיהיה לפי כלל הברזל. עוד על הצהרות של משתנים נלמד ב”כלל הקומפיילר” בקרוב. אז יש לנו טענה משנית. מה היא המסקנה? המסקנה היא שקיים NN כך שלכל n>Nn>N מתקיים ∣bn−0∣<ε\left|b_{n}-0\right|<\varepsilon. אבל מאחר ש-bnb_{n} אי-שלילית, זה בדיוק כמו לומר bn<εb_{n}<\varepsilon. לסיכום, כשנידרש בהוכחה להשתמש בסילוגיזם, נכתוב את הפסוק הבא:

“עבור ה-0<ε0<\varepsilon, לפי הגדרת הגבול של bnb_{n}, קיים NN כך שלכל n>Nn>N מתקיים ∣bn−0∣<ε\left|b_{n}-0\right|<\varepsilon. בגלל ש-bnb_{n} אי-שלילית, זה שקול ל-bn<εb_{n}<\varepsilon.”

בואו נסכם את התכנית. נפתח עם כלל הברזל ונצהיר על ε\varepsilon חיובי. נבצע סילוגיזם על ה-ε\varepsilon הזה ונקבל NN גדול. לפי כלל הברזל ניקח n>Nn>N ונראה שהמסקנה הדרושה להגדרת הגבול על ana_{n} מתקיימת. חגיגה.

הוכחה
  1. יהי ε>0\varepsilon>0.
  2. עבור ε>0\varepsilon>0 זה, לפי הגדרת הגבול של bnb_{n}, קיים NN כך שלכל n>Nn>N מתקיים ∣bn−0∣<ε\left|b_{n}-0\right|<\varepsilon. בגלל ש-bnb_{n} אי-שלילית, זה שקול ל-bn<εb_{n}<\varepsilon.
  3. יהי n>Nn>N.
  4. נעזר בנתון על ana_{n} ו-bnb_{n} ונקבל ∣an−L∣<bn<ε\left|a_{n}-L\right|<b_{n}<\varepsilon
  5. ולכן lim⁡n→∞an=L\lim_{n\to\infty}a_{n}=L.
ניתוח ההוכחה

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

התחלנו (משפט 1) את ההוכחה לפי כלל הברזל (בהגדרה רצו להראות משהו לכל אפסילון חיובי, אז הבאנו אחד כזה, ובסטייל). לאחר מכן ההגדרה מבקשת מאיתנו להציג מיהו ה-NN הגדול. לצורך כך (משפט 2) נעזרנו בסילוגיזם על הגדרת הגבול של bnb_{n} וכתבנו לפי מתכון הסילוגיזם. ברגע שיש לנו NN כזה, הגדרת הגבול מבקשת מאיתנו להוכיח את יכולתיו, ובפרט להראות שעבור כל האינדקסים שגדולים ממנו – n>Nn>N – מתקיים תנאי המרחק ל-ana_{n}. אז (משפט 3) לפי כלל הברזל הצהרנו על כזה אינדקס גדול מ-NN, ונעזרנו (משפט 4) בכל מה שאנו יודעים (על הסדרות ובכלל על החיים) על מנת להוכיח את הגבלת המרחק על ana_{n}. בסוף (משפט 5), חתמנו את ההוכחה, בסטייל.

אגב, לא יודע אם שמתם לב, אבל למעשה הטענה שהוכחנו כאן מסבירה למה “שיטת חד-גדיא” עובדת. תחשבו על זה :)

כלל הקומפיילר

אני חושב שזה זמן טוב ללמוד עוד כלל חשוב שיכול לעזור לנו לוודא שההוכחות שלנו תקינות. אני נוהג לקרוא לו – כלל הקומפיילר.

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

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

טעות נפוצה בקרב אנשים אשר לומדים תכנות לראשונה, היא שימוש במשתנים שהם לא הגדירו מראש. בשפת C למשל, לפני שניתן לאחסן במשתנה מספר מסוים ולאחר מכן לבצע עליו חישובים, יש קודם להצהיר עליו בקוד. משהו בסגנון “המשתנה בשם i הוא מספר שלם!”. עושים את זה בקצת פחות דרמטיות, אבל זה העיקרון. אם אתה לא עושה את זה, הקומפיילר סוטר לך ומדבר אלייך גסויות.

תופעה דומה להגדרת המשתנים מופיעה גם במתמטיקה. תהיתם למה בהגדרת הגבול קודם אומרים “לכל ε>0\varepsilon>0” ו-”קיים NN” ורק אז טורחים לספר לנו את מה שתכל’ס חשוב (המרחק של איברי הסדרה מהגבול)? הסיבה דומה לדרך שבה קומפיילר עובד. כשאתם רושמים את אי-השיווין המהמם ∣an−L∣<ε\left|a_{n}-L\right|<\varepsilon, לכל אות לטינית פה חייבית להיות משמעות ברורה. במקרה של הסדרה {an}n=1∞\left\{ a_{n}\right\} _{n=1}^{\infty} והגבול LL זה בדרך כלל ברור מי הם. אבל מה שיותר חשוב ומעניין זה מי הוא ε\varepsilon, ועבור אילו ערכים טבעיים nn אי השיוון הזה מתקיים. על כן בתחילת ההגדרה מצהירים ומגדירים מי הוא ε\varepsilon ומי הוא nn. ε\varepsilon הוא מספר חיובי כלשהו, והערכים הטבעיים nn הם כל המספרים הטבעיים אשר גדולים מ-NN – שגם הוגדר לפני שהגדירו את nn!

באופן דומה, גם ההוכחה שלנו צריכה להשתמש רק במשתנים שהצהרנו עליהם, או שהוגדרו כמסקנות בסילוגיזמים. שימו לב נגיד למשפט השני בהוכחה שלנו לעיל. הוא נפתח במילים “עבור ה-ε\varepsilon הזה…”. כשאנחנו מגיעים לשלב הזה בהוכחה, אנחנו חייבים לדעת מי הוא ε\varepsilon. ולא במקרה, מאחר שהוכחנו לפי הגדרה ועקבנו אחרי כלל הברזל, המשפט הראשון בהוכחה כבר הצהיר לנו מי הוא ε\varepsilon.

דוגמה נוספת היא במשפט 3. משפט 3 מצהיר לנו על הערכים הטבעיים nn שיהוו את האינדקסים עבורם אי-שיווין המרחק של הסדרה מהגבול מתקיים. אבל על מנת להצהיר על אותם אינדקסים, אנחנו צריכים לדעת מי הוא בכלל NN. ההגדרה של NN מתרחשת בסוף משפט 2, והיא למעשה המסקנה של הסילוגיזם.

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

לסיכום: כל הוכחה תקינה תעבור את כלל הקומפיילר. אם היא לא עוברת את הקומפיילר, כנראה שיש בעיה5.

כלל הקומפיילר

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

המשיכו לחלק הבא

  1. באופן כללי, הטענה נכונה גם אם הגבול L=0L=0. במקרה זה צריך לטפל בנפרד ולצורך הפשטות לא נתייחס אליו כאן. ↩

  2. למעשה לא חובה לקרוא את כל הפרק, אלא רק את העמודים הראשונים העוסקים בסילוגיזם. ↩

  3. לפעמים הטענה המשנית תהיה משהו מהסגנון “יהי ε>0\varepsilon>0”. יש הבדל בין שני הניסוחים שכן אחד כללי והשני ספציפי. כך או כך, הטענה המשנית מציגה ε\varepsilon חיובי כלשהו. ↩

  4. בונוס: ניתן גם להוכיח בעזרת משפט הסנדוויץ. נגיע לזה בהמשך. ↩

  5. לתשומת ליבכם, זה לא אם ורק אם. ↩

החכמתם? נהנתם? מוזמנים להזמין לי כוס קפה :)