B.5: Структурна індукція

Last updated
Save as PDF

Page ID: 52710

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

Поки що ми використовували індукцію для встановлення результатів щодо всіх натуральних чисел. Але відповідний принцип може бути використаний безпосередньо для доведення результатів про всі елементи індуктивно визначеної множини. Це часто називають структурною індукцією, оскільки вона залежить від структури індуктивно визначених об'єктів.

Як правило, індуктивне визначення задається (а) списком «початкових» елементів множини та (b) списком операцій, які виробляють нові елементи множини зі старих. Наприклад, у випадку приємних термінів початковими об'єктами є літери. У нас є лише одна операція: операції є\[\begin{aligned} o(s_1, s_2) = & [s_1 \circ s_2]\end{aligned}\] Ви навіть можете думати про\(\Nat\) самі натуральні числа як дані індуктивним визначенням: початковий об'єкт є\(0\), а операція є функцією-наступником\(x + 1\).

Для того, щоб довести щось про всі елементи індуктивно визначеного множини, тобто, що кожен елемент множини має властивість\(P\), ми повинні:

Доведіть, що початкові об'єкти мають\(P\)
Доведіть, що для кожної операції\(o\), якщо аргументи є\(P\), так робить результат.

Наприклад, для того, щоб довести щось про всі приємні терміни, ми доведемо, що це правда щодо всіх листів, і що це правда за\([s_1 \circ s_2]\) умови, що це\(s_2\) вірно\(s_1\) і індивідуально.

Пропозиція\(\PageIndex{1}\)

Число\([\) дорівнює числу\(]\) в будь-якому приємному терміні\(t\).

Доказ. Використовуємо структурну індукцію. Приємні терміни індуктивно визначаються, з літерами як початковими об'єктами та операціями\(o\) побудови нових приємних термінів із старих.

Претензія вірна для кожної літери, так як число\([\) в листі само по собі є\(0\) і число\(]\) в ньому теж\(0\).
Припустимо, що число\([\) в\(s_1\) дорівнює числу\(]\), і те ж саме вірно для\(s_2\). Число\([\) в\(o(s_1, s_2)\), тобто в\([s_1 \circ s_2]\), - це сума числа\([\) в\(s_1\) і\(s_2\). Число\(]\) in\(o(s_1, s_2)\) - це сума числа\(]\) в\(s_1\) і\(s_2\). Таким чином, число\([\) in\(o(s_1, s_2)\) дорівнює числу\(]\) in\(o(s_1,s_2)\).

◻

Проблема\(\PageIndex{1}\)

Доведіть структурною індукцією, що жоден хороший термін не починається з\(]\).

Наведемо ще один доказ структурної індукції: правильний початковий відрізок\(t\) рядка символів - це будь-який рядок,\(s\) який узгоджується з\(t\) символом за символом,\(t\) зчитується зліва, але довший. Отже, наприклад,\([a \circ {}\) є правильним початковим сегментом\([a \circ b]\), але ні\([b \circ {}\) (вони не згодні на другому символі), ні\([a \circ b]\) (вони мають однакову довжину).

Пропозиція\(\PageIndex{2}\)

Кожен належний початковий сегмент приємного терміну\(t\) має більше\([\), ніж\(]\) у.

Доказ. За індукцією на\(t\):

\(t\)це буква сама по собі: Тоді не\(t\) має належних початкових сегментів.
\(t = [s_1 \circ s_2]\)для деяких приємних умов\(s_1\) і\(s_2\). Якщо\(r\) це правильний початковий сегмент\(t\), існує ряд можливостей:
1. \(r\)це просто\([\): Тоді\(r\) має ще один\([\), ніж це робить\(]\).
2. \(r\)\([r_1\)де\(r_1\) є правильним початковим сегментом\(s_1\): Оскільки\(s_1\) це хороший термін, за індукційною гіпотезою,\(r_1\) має більше,\([\) ніж\(]\) і те ж вірно для\([r_1\).
3. \(r\)is\([s_1\) or\([s_1 \circ {}\): За попереднім результатом кількість\([\) і\(]\) в\(s_1\) рівні; тому число\([\) в\([s_1\) або\([s_1 \circ {}\) є на один більше, ніж число\(]\).
4. \(r\)\([s_1 \circ r_2\)де\(r_2\) є правильним початковим сегментом\(s_2\): За індукційною гіпотезою,\(r_2\) містить більше,\([\) ніж\(]\). За попереднім результатом число\([\) і\(]\) в\(s_1\) рівні. Таким чином, число\([\)\([s_1 \circ r_2\) в більше, ніж число\(]\).
5. \(r\)is\([s_1 \circ s_2\): За попереднім результатом кількість\([\) і\(]\) в\(s_1\) рівні, і однакові для\(s_2\). Так що є ще один\([\) в\([s_1 \circ s_2\), ніж є\(]\).

◻