6.1: Порівняння геометрії та арифметики

Last updated
Save as PDF

Page ID: 65921

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Коли студенти вперше зустрічаються «доказ шляхом індукції», це часто пояснюється таким чином, що залишає їх почуттям виразно нелегко, оскільки, здається, порушує фундаментальне табу:

ніколи не припускайте, що ви намагаєтеся довести.

Це, як правило, залишає новачка в положенні, описаному цитатою д'Аламбера на початку глави: вони можуть «натиснути» в надії, що «розуміння піде», але сумніви часто залишаються. Тому ми закликаємо читачів, які вже зустріли докази за допомогою індукції, зробити крок назад і спробувати знову зрозуміти, як це насправді працює. Це може зажадати від вас вивчення рішень (Розділ 6.10), і бути готовим навчитися виписувати докази ретельніше, ніж, і зовсім інакше від того, до чого ви звикли.

Коли ми хочемо довести загальний результат, який включає в себе параметр n, де n може бути будь-яке натуральне число, ми дійсно намагаємося довести нескінченно багато результатів все відразу. Якби ми спробували довести таку колекцію результатів по черзі «по одному», ми б не тільки ніколи не закінчили, ми б ледве розпочали (оскільки завершення першого мільйона, або мільярда, справ залишає стільки ж скасованих, як і на старті). Тож наша єдина надія:

думати про послідовність тверджень єдиним способом, як складається з нескінченно багатьох різних, але схожих на вигляд тверджень P (n), по одному для кожного n окремо (з кожним твердженням залежно від конкретного n); і
визнати, що загальний результат, який підлягає доведенню, є не просто єдиним твердженням P (n), а складним твердженням про те, що «P (n) вірно, для всіх $п \geq 1$ ».

Після того, як результат, який потрібно довести, буде сформульований таким чином, ми можемо

голими руками перевірити, чи вірно найперше твердження (зазвичай P (1)); і
спробувати знайти якийсь спосіб продемонструвати це,

— як тільки ми дізнаємося, що «P (k) вірно, для деяких (конкретних, але невизначених) $к \geq 1$ »,

— ми можемо єдиним чином довести, що наступний результат $Р (к + 1)$ потім автоматично істинно.

Реалізувавши перший з двох етапів індукції, ми знаємо, що P (1) вірно.

Другий пункт кулі вище тоді вступає в гру і запевняє нас, що (оскільки ми знаємо, що P (1) є істинним), P (2) повинен бути істинним.

І як тільки ми дізнаємося, що P (2) вірно, друга точка кулі запевняє нас, що P (3) також вірно.

І як тільки ми дізнаємося, що P (3) є істинним, друга точка кулі запевняє нас, що P (4) також вірно.

І так на віки віків.

Потім ми можемо зробити висновок, що вся послідовність нескінченно багатьох тверджень вірна, а саме:

«кожне твердження P (n) вірно»,

або що

«P (n) вірно, для всіх $п \geq 1$ .»

Іншими словами, якщо ми визначимо S бути множиною натуральних чисел n, для яких твердження P (n) істинно, то S містить елемент «1», і всякий раз, коли k знаходиться в S, так $к + 1$ ; отже, за принципом математичної індукції ми знаємо, що S містить всі натуральні числа.

На цьому етапі ми повинні визнати важливий дидактичний (а не математичний) хід у нашому рекомендованому макеті тут. Важливо підкреслити відмінність між

(i) окремі твердження P (n), які є окремими інгредієнтами загального твердження, що підлягають доведенню, а саме:

«P (n) вірно, для всіх $п \geq 1$ »,

де нескінченно багато окремих тверджень були стиснуті в єдине складне твердження, і

(ii) крок індукції, де ми

— припустити, що деякі конкретні P (k), як відомо, є істинним, і

— показати, що наступне твердження $Р (к + 1)$ потім автоматично істинно.

Щоб підкреслити цю відмінність, ми послідовно використовуємо іншу «фіктивну змінну» (а саме «k») в останньому випадку. Ця відмінність є швидше психологічним прийомом, ніж логічною необхідністю. Однак ми рекомендуємо читачам наслідувати цю відмінність (принаймні спочатку).