B.3: Сильна індукція

Last updated
Save as PDF

Page ID: 52747

\( \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}}\)

Template:MathJaxZach

У розглянутому вище принципі індукції ми доводимо\(P(0)\) і теж якщо\(P(k)\), то\(P(k+1)\). У другій частині ми припускаємо, що\(P(k)\) це правда і використовуємо це припущення для доведення\(P(k+1)\). В еквіваленті, звичайно, ми могли б припустити\(P(k-1)\) і використовувати його для доведення\(P(k)\) - важливою частиною є те, що ми зможемо здійснити висновок з будь-якого числа до його наступника; що ми можемо довести відповідну претензію для будь-якого числа за припущенням, яке воно має за своє попередник.

Існує варіант принципу індукції, в якому ми не просто припускаємо, що претензія стосується попередника\(k-1\)\(k\), але для всіх чисел менше\(k\), ніж, і використовуємо це припущення для встановлення претензії\(k\). Це також дає нам претензії\(P(n)\) для всіх\(n \in \Nat\). Після того, як ми встановили\(P(0)\), ми тим самим встановили, що\(P\) утримує для всіх чисел менше, ніж\(1\). І якщо ми знаємо, що якщо\(P(l)\) для всіх\(l<k\), то\(P(k)\), ми знаємо це зокрема для\(k=1\). Таким чином, можна зробити висновок\(P(1)\). Цим ми довели\(P(0)\) і\(P(1)\), тобто\(P(l)\) для всіх\(l<2\), а так як маємо ще й умовне, якщо\(P(l)\) для всіх\(l<2\), то\(P(2)\), можна зробити висновок \(P(2)\), і так далі.

Насправді, якщо ми можемо встановити загальний умовний «для всіх\(k\), якщо\(P(l)\) для всіх\(l<k\)\(P(k)\), то» нам\(P(0)\) більше не доведеться встановлювати, так як це випливає з нього. Бо пам'ятайте, що загальна претензія на кшталт «для всіх\(P(l)\)»\(l<k\), вірна, якщо їх немає\(l<k\). Це випадок вакуумного кількісного визначення: «всі\(A\) s є\(B\) s» вірно, якщо немає\(A\) s,\(\lforall{x}{(A(x) \lif B(x))}\) є істинним, якщо не\(x\) задовольняє\(A(x)\). У цьому випадку формалізованою версією буде «\(\lforall{l}{(l < k \lif P(l))}\)» - і це правда, якщо їх немає\(l < k\). І якщо\(k=0\) це точно так: ні\(l<0\), отже, «для всіх\(P(0)\)»\(l<0\), правда, що б там\(P\) не було. Доказ «якщо\(P(l)\) для всіх\(l<k\), то\(P(k)\)» таким чином автоматично встановлює\(P(0)\).

Цей варіант корисний, якщо встановлення претензії не\(k\) може бути зроблено, щоб просто покладатися на претензію,\(k-1\) але може вимагати припущення, що це вірно для одного або декількох\(l<k\).