Додаток B: Індукція

$\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}}$

B.1: Вступ
Індукція є важливою технікою доказів, яка використовується в різних формах майже у всіх областях логіки, теоретичної інформатики та математики. Він часто протиставляється дедукції і характеризується як висновок від конкретного до загального.
B.2: Індукція на
У найпростішому вигляді індукція - це техніка, яка використовується для доведення результатів для всіх натуральних чисел. Ми встановлюємо, що щось вірно $0$ і показуємо, що всякий раз, коли це вірно для числа $n$ , це також вірно для наступного числа $n+1$ .
B.3: Сильна індукція
Існує варіант принципу індукції, в якому ми не просто припускаємо, що претензія стосується попередника $k-1$ $k$ , але для всіх чисел менше $k$ , ніж, і використовуємо це припущення для встановлення претензії $k$ .
B.4: Індуктивні визначення
У логіці ми дуже часто визначаємо види об'єктів індуктивно, тобто вказуючи правила для того, що вважається об'єктом такого роду, який потрібно визначити, які пояснюють, як отримати нові об'єкти такого роду зі старих об'єктів такого роду.
B.5: Структурна індукція
Поки що ми використовували індукцію для встановлення результатів щодо всіх натуральних чисел. Але відповідний принцип може бути використаний безпосередньо для доведення результатів про всі елементи індуктивно визначеної множини. Це часто називають структурною індукцією, оскільки вона залежить від структури індуктивно визначених об'єктів.
B.6: Відносини та функції
Коли ми визначили набір об'єктів індуктивно, ми також можемо визначити відносини на цих об'єктах шляхом індукції, і дати індуктивні визначення функцій.