B.4: Індуктивні визначення

У логіці ми дуже часто визначаємо види об'єктів індуктивно, тобто вказуючи правила для того, що вважається об'єктом такого роду, який потрібно визначити, які пояснюють, як отримати нові об'єкти такого роду зі старих об'єктів такого роду. Наприклад, ми часто визначаємо спеціальні види послідовностей символів, таких як терміни та формули мови, шляхом індукції. Для простого прикладу розглянемо рядки, що складаються з букв\(\mathrm{a}\)\(\mathrm{b}\),\(\mathrm{c}\),\(\mathrm{d}\),\(\circ\), символ і дужки\([\) і\(]\), такі як «\([[\mathrm{c} \circ \mathrm{d}][\)»,» \([\mathrm{a}[]\circ]\)», «\(\mathrm{a}\)» або «\([[\mathrm{a} \circ \mathrm{b}]\circ \mathrm{d}]\)». Ви, напевно, відчуваєте, що є щось «неправильне» з першими двома рядками: дужки взагалі не «балансують» в першому, і ви можете відчути, що «\(\circ\)» повинні «з'єднувати» вирази, які самі мають сенс. Третя і четверта рядки виглядають краще: для кожного «\([\)» є закриття «\(]\)» (якщо такі є взагалі), і для будь-якого\(\circ\) ми можемо знайти «приємні» вирази з обох боків, оточені парою дужок.

Ми хотіли б точно вказати, що вважається «приємним терміном». Перш за все, кожна буква сама по собі приємна. Все, що не просто буква сама по собі має бути форми «\([t \circ s]\)» де\(s\) і самі по собі\(t\) приємні. І навпаки, якщо\(t\) і\(s\) приємні, то ми можемо сформувати новий приємний термін, поставивши\(\circ\) між ними і оточити їх парою дужок. Ми можемо використовувати ці операції для визначення набору приємних термінів. Це індуктивне визначення.

Це визначення говорить нам, що щось вважається приємним терміном, якщо його можна побудувати відповідно до двох умов (1) та (2) за деяку кінцеву кількість кроків. На першому кроці ми будуємо всі приємні терміни, що складаються з букв самі по собі, тобто,\[\mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{d}\nonumber\] На другому кроці ми застосовуємо (2) до побудованих нами термінів. Ми отримаємо\[[\mathrm{a} \circ \mathrm{a}], [\mathrm{a} \circ \mathrm{b}], [\mathrm{b} \circ \mathrm{a}], \dots, [\mathrm{d} \circ \mathrm{d}]\nonumber\] для всіх комбінацій двох букв. На третьому кроці ми знову застосовуємо (2) до будь-яких двох приємних термінів, які ми побудували до цих пір. Ми отримуємо новий приємний термін, такий як\([\mathrm{a} \circ [\mathrm{a} \circ \mathrm{a}]]\) —де\(t\)\(\mathrm{a}\) з кроку 1 і\(s\) є\([\mathrm{a} \circ \mathrm{a}]\) з кроку 2 - і\([[\mathrm{b} \circ \mathrm{c}] \circ [\mathrm{d} \circ \mathrm{b}]]\) побудовано з двох термінів\([\mathrm{b} \circ \mathrm{c}]\) і\([\mathrm{d} \circ \mathrm{b}]\) з кроку 2. І так далі. Пункт (3) виключає, що все, що не побудовано таким чином, пробирається до набору приємних термінів.

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

Ключовою особливістю індуктивних визначень є те, що якщо ви хочете довести щось про всі приємні терміни, визначення говорить вам, які випадки ви повинні розглянути. Наприклад, якщо вам кажуть, що\(t\) це хороший термін, індуктивне визначення говорить вам, як\(t\) може виглядати:\(t\) може бути буквою, або це може бути\([s_1 \circ s_2]\) для деякої пари приємних термінів\(s_1\) і\(s_2\) . Через пункт (3) це єдині можливості.

При доведенні тверджень про всі індуктивно визначені множини, сильна форма індукції стає особливо важливою. Наприклад, припустимо, ми хочемо довести, що для кожного приємного терміну довжини\(n\) число\([\) в ньому є\(< n/2\). Це можна розглядати як претензію про всіх\(n\): для кожного\(n\) кількість\([\) у будь-якому приємному терміні довжини\(n\) є\(< n/2\).