5.4: Унікальна читабельність

Template:MathJaxZach

Те, як ми визначили формули, гарантує, що кожна формула має унікальне читання, тобто є по суті лише один спосіб побудови її за нашими правилами формування формул і лише один спосіб «інтерпретації» її. Якби це було не так, ми мали б неоднозначні формули, тобто формули, які мають більше одного читання або інтерпретації - і це явно те, чого ми хочемо уникати. Але що ще важливіше, без цієї властивості більшість визначень і доказів, які ми збираємося дати, не пройдуть.

Мабуть, найкращий спосіб зрозуміти це - побачити, що станеться, якби ми дали погані правила формування формул, які не гарантували б унікальну читабельність. Наприклад, ми могли б забути дужки в правилах формування зв'язків, наприклад, ми могли б це дозволити:

Якщо\(A\) і\(B\) є формулами, то так і є\(A \lif B\).

Починаючи з атомної формули\(D\), це дозволило б нам сформуватися\(D \lif D\). Від цього, разом з\(D\), ми б і вийшли\(D \lif D \lif D\). Але є два способи зробити це:

1. Ми\(D\) беремо бути\(A\) і\(D \lif D\) бути\(B\).

2. Ми\(A\) беремо бути\(D \lif D\) і\(B\) є\(D\).

Відповідно, існує два способи «прочитати» формулу\(D \lif D \lif D\). Він має форму,\(B \lif C\) де\(B\) є\(D\) і\(C\) є\(D \lif D\), але вона також має форму\(B \lif C\) з\(B\) буття\(D \lif D\) і \(C\)буття\(D\).

Якщо це станеться, наші визначення не завжди будуть працювати. Наприклад, коли ми визначаємо основний оператор формули, ми говоримо: у\(B \lif C\) формулі форми основним оператором є вказане виникнення\(\lif\). Але якщо ми можемо зіставити формулу\(D \lif D \lif D\) з\(B \lif C\) двома різними способами, згаданими вище, то в одному випадку ми отримуємо перше виникнення\(\lif\) як основний оператор, а в другому випадку другий. Але ми маємо намір основний оператор бути функцією формули, тобто кожна формула повинна мати рівно один основний оператор виникнення.

Лемма\(\PageIndex{1}\)

Кількість лівої та правої дужок у\(A\) формулі дорівнює.

Доказ. Доводимо це шляхом індукції на шляху\(A\) побудованого. Для цього потрібні дві речі: (а) Ми повинні спочатку довести, що всі атомні формули мають відповідну властивість (індукційна основа). (b) Тоді ми повинні довести, що коли ми будуємо нові формули з заданих формул, нові формули мають властивість за умови, що старі роблять.

\(l(A)\)Дозволяти кількість лівих дужок, і\(r(A)\) кількість правих дужок в\(A\),\(l(t)\) і\(r(t)\) аналогічно кількість лівої і правої дужок у терміні\(t\). Ми залишаємо доказ того, що на будь-який термін\(t\),\(l(t) = r(t)\) як вправу.

1. \(\indcase{A}{\lfalse}\)\(\indfrm\)має 0 лівих і 0 правих дужок.

2. \(\indcase{A}{\Atom{R}{t_1,\dots,t_n}}\)\(l(\indfrm) = 1 + l(t_1) + \dots + l(t_n) = 1 + r(t_1) + \dots + r(t_n) = r(\indfrm)\). Тут ми використовуємо той факт, що залишився як вправа, що\(l(t) = r(t)\) для будь-якого терміну\(t\).

3. \(\indcase{A}{\eq[t_1][t_2]}\)\(l(\indfrm) = l(t_1) + l(t_2) = r(t_1) + r(t_2) = r(\indfrm)\).

4. \(\indcase{A}{\lnot B}\)За індукційною гіпотезою,\(l(B) = r(B)\). Таким чином\(l(\indfrm) = l(B) = r(B) = r(\indfrm)\).

5. \(\indcase{A}{(B \ast C)}\)За індукційною гіпотезою,\(l(B) = r(B)\) і\(l(C) = r(C)\). Таким чином\(l(\indfrm) = 1 + l(B) + l(C) = 1 + r(B) + r(C) = r(\indfrm)\).

6. \(\indcase{A}{\lforall{x}{B}}\)За індукційною гіпотезою,\(l(B) = r(B)\). Таким чином,\(l(\indfrm) = l(B) = r(B) = r(\indfrm)\).

7. \(\indcase{A}{\lexists{x}{B}}\)Аналогічно.

◻

Визначення\(\PageIndex{1}\): Proper prefix

Рядок символів\(B\) є правильним префіксом рядка символів,\(A\) якщо збігається\(B\) і непорожній рядок символів дає\(A\).

Лемма\(\PageIndex{2}\)

Якщо\(A\) є формулою, і\(B\) є правильним префіксом\(A\), то\(B\) це не формула.

Доказ. Вправа. ◻

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

Доведіть Лемма\(\PageIndex{2}\).

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

Якщо\(A\) атомна формула, то вона задовольняє одному, і тільки одному з наступних умов.

1. \(A \ident \lfalse\).

2. \(A \ident \Atom{R}{t_1,\dots,t_n}\)де\(R\) є символом присудка\(n\) -place\(t_1\),,,,\(t_n\) є термінами, і кожен з\(R\)\(t_1\),,..., однозначно\(t_n\) визначається.

3. \(A \ident \eq[t_1][t_2]\)де\(t_1\) і\(t_2\) є однозначно визначеними термінами.

Доказ. Вправа. ◻

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

Довести пропозицію\(\PageIndex{1}\) (Підказка: Сформулювати і довести версію Лемма\(\PageIndex{2}\) для термінів.)

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

Кожна формула задовольняє одному, і тільки одному з наступних умов.

1. \(A\)є атомним.

2. \(A\)має форму\(\lnot B\).

3. \(A\)має форму\((B \land C)\).

4. \(A\)має форму\((B \lor C)\).

5. \(A\)має форму\((B \lif C)\).

6. \(A\)має форму\(\lforall{x}{B}\).

7. \(A\)має форму\(\lexists{x}{B}\).

Причому, в кожному конкретному випадку\(B\), або\(B\) і\(C\), визначаються однозначно. Це означає, що, наприклад, немає різних пар\(B\)\(B'\),\(C\) і,\(C'\) так\(A\) що обидві форми\((B \lif C)\) and \((B' \lif C')\).

Доказ. Правила формування вимагають, щоб якщо формула не є атомарною, вона повинна починатися з відкриває дужки (\(\lnot\),або з квантора. З іншого боку, кожна формула, яка починається з одного з наступних символів, повинна бути атомарною: символ предиката, символ функції, постійний символ,\(\lfalse\).

Таким чином, ми дійсно тільки повинні показати, що якщо\(A\) є форми,\((B \ast C)\) а також форми\((B' \mathbin{\ast'} C')\), то\(B \ident B'\)\(C \ident C'\), і\(\ast = {\ast'}\).

Так що припустимо, що обидва\(A \ident (B \ast C)\) і\(A \ident (B' \mathbin{\ast'} C')\). Тоді\(B \ident B'\) або ні. Якщо це так, чітко\(\ast = {\ast'}\) і\(C \ident C'\), оскільки вони потім є підрядками\(A\), що починаються в тому ж місці і мають однакову довжину. Інший випадок - це\(B \not\ident B'\). Оскільки\(B\) і\(B'\) є обидва підрядки\(A\), що починаються в одному і тому ж місці, один повинен бути належним префіксом іншого. Але це неможливо по Леммі\(\PageIndex{2}\). ◻