B.1: Вступ

Last updated
Save as PDF

Page ID: 52712

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

Індукція є важливою технікою доказів, яка використовується в різних формах майже у всіх областях логіки, теоретичної інформатики та математики. Він потрібен, щоб довести багато результатів в логіці.

Індукція часто протиставляється дедукції і характеризується як висновок від конкретного до загального. Наприклад, якщо ми спостерігаємо багато зелених смарагдів, і нічого, що ми б назвали смарагдом, який не зелений, ми можемо зробити висновок, що всі смарагди зелені. Це індуктивний висновок, в тому, що він виходить з багатьох конкретних випадків (цей смарагд зелений, що смарагд зелений і т.д.) до загальної претензії (всі смарагди зелені). Математична індукція - це також висновок, який укладає загальну претензію, але вона має зовсім інший вид, ніж ця «проста індукція».

Дуже грубо індуктивний доказ в математиці робить висновок про те, що всі математичні об'єкти певного роду мають певну властивість. У найпростішому випадку математичні об'єкти, з якими займається індуктивне доказ, є натуральними числами. У цьому випадку індуктивний доказ використовується для встановлення того, що всі натуральні числа мають певну властивість, і він робить це, показуючи, що

\(0\)має майно, і (2)
всякий раз, коли число\(k\) має властивість, так і робить\(k+1\).

Індукція на натуральні числа потім також часто може бути використана для доведення загального про математичні об'єкти, яким можуть бути присвоєні числа. Наприклад, скінченні множини кожен мають кінцеву\(n\) кількість елементів, і якщо ми можемо використовувати індукцію, щоб показати, що кожне число\(n\) має властивість «всі\(n\) кінцеві набори розміру...», то ми показуємо щось про всі скінченні множини.

Індукція також може бути узагальнена до математичних об'єктів, які індуктивно визначені. Наприклад, вирази формальної мови, такі як логіка першого порядку, визначаються індуктивно. Структурна індукція - це спосіб довести результати щодо всіх таких виразів. Структурна індукція, зокрема, дуже корисна і широко використовується - в логіці.