10.4: Розширення Хенкіна

Last updated
Save as PDF

Page ID: 52780

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

Частина завдання в доведенні теореми про повноту полягає в тому, що модель, яку ми будуємо з повного узгодженого набору,\(\Gamma\) повинна зробити всі кількісні формули\(\Gamma\) істинними. Для того, щоб гарантувати це, ми використовуємо трюк завдяки Леону Хенкіну. По суті, хитрість полягає в розширенні мови нескінченно багатьма постійними символами і додаванні для кожної формули з однією\(A(x)\) вільною змінною формули виду\(\lexists{x}{A(x)} \lif A(c)\), де\(c\) знаходиться один з нових постійних символів. Коли ми будуємо структуру, яка задовольняє\(\Gamma\), це гарантуватиме, що кожне справжнє екзистенціальне речення має свідка серед нових констант.

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

Якщо\(\Gamma\) послідовний в\(\Lang L\) і\(\Lang L'\)\(\Lang L\) отримується від додавання незліченно нескінченного набору нових постійних символів\(\Obj d_0\)\(\Obj d_1\),,..., то\(\Gamma\) послідовний в \(\Lang L'\).

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

Набір\(\Gamma\) формул мови\(\Lang {L}\) насичений, якщодля кожної формули\(A(x) \in \Frm[L]\) з однією вільною змінною\(x\) є постійний символ\(c \in \Lang{L}\) такий, що\(\lexists{x}{A(x)} \lif A(c) \in \Gamma\).

Наступне визначення буде використано в доведенні наступної теореми.

Визначення\(\PageIndex{2}\)

Нехай\(\Lang L'\) буде як у Пропозиції\(\PageIndex{1}\). Виправте перерахування\(A_0(x_0)\)\(A_1(x_1)\),... всіх формул,\(\Lang L'\) в\(A_i(x_i)\) яких одна змінна (\(x_i\)) зустрічається безкоштовно. Визначаємо пропозиції\(D_n\) шляхом індукції на\(n\).

\(c_0\)Дозволяти бути першим постійним\(\Obj d_i\) символом серед доданих до\(\Lang{L}\) якого не зустрічається в\(A_0(x_0)\). Припускаючи\(D_0\), що,...,\(D_{n-1}\) вже визначено, нехай\(c_n\) буде першим серед нових постійних символів,\(\Obj d_i\) які не зустрічаються ні в\(D_0\),...,\(D_{n-1}\) ні в\(A_n(x_n)\).

Тепер нехай\(D_{n}\) буде формула\(\lexists{x_{n}}{A_{n}(x_{n})} \lif A_{n}(c_{n})\).

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

Кожен послідовний набір\(\Gamma\) може бути розширений до насиченого послідовного набору\(\Gamma'\).

Доказ. Враховуючи послідовний набір речень\(\Gamma\) мовою\(\Lang{L}\), розширити мову, додавши незліченно нескінченний набір нових постійних символів для формування\(\Lang{L'}\). За пропозицією\(\PageIndex{1}\),\(\Gamma\) все ще узгоджується у багатшій мові. Далі, нехай\(D_i\) буде як у визначенні\(\PageIndex{2}\). Нехай\[\begin{aligned} \Gamma_0 & = \Gamma \\ \Gamma_{n+1} & = \Gamma_n \cup \{D_n \}\end{aligned}\] т. Е.\(\Gamma_{n+1} = \Gamma \cup \{ D_0, \dots, D_n \}\), і нехай\(\Gamma' = \bigcup_{n} \Gamma_n\). \(\Gamma'\)явно насичений.

Якби\(\Gamma'\) були суперечливими, то для деяких\(n\),\(\Gamma_n\) було б непослідовним (Вправа: поясніть, чому). Таким чином, щоб показати,\(\Gamma'\) що послідовно, досить показати, шляхом індукції\(n\), що кожен набір\(\Gamma_n\) є послідовним.

Основою індукції є просто твердження, яке\(\Gamma_0 = \Gamma\) є послідовним, що є гіпотезою теореми. Для індукційного кроку припустимо, що\(\Gamma_{n}\) це послідовно\(\Gamma_{n+1} = \Gamma_n \cup \{D_n\}\), але непослідовно. Нагадаємо, що\(D_n\) є\(\lexists{x_{n}}{A_{n}(x_n)} \lif A_{n}(c_{n})\), де\(A_n(x_n)\) знаходиться формула\(\Lang{L'}\) з тільки змінною\(x_n\) free. До речі, ми вибрали\(c_n\) (див. Визначення\(\PageIndex{2}\)),\(c_n\) не відбувається\(A_n(x_n)\) ні в ні в\(\Gamma_n\).

Якщо\(\Gamma_n \cup \{D_n\}\) є непослідовним, то\(\Gamma_n \Proves \lnot D_n\), і, отже, обидва наступні утримання:\[\Gamma_n \Proves \lexists{x_n}{A_n(x_n)} \qquad \Gamma_n \Proves \lnot A_n(c_n)\nonumber\] Оскільки\(c_n\) не відбувається в\(\Gamma_n\) або в\(A_n(x_n)\), Теореми 8.11.1 і 9.10.1 застосовується. Від\(\Gamma_n \Proves \lnot A_n(c_n)\), отримуємо\(\Gamma_n \Proves \lforall{x_n}{\lnot A_n(x_n)}\). Таким чином, ми маємо, що обидва\(\Gamma_n \Proves \lexists{x_n}{A_n(x_n)}\) and \(\Gamma_n \Proves \lforall{x_n}{\lnot A_n(x_n)}\), так\(\Gamma_n\) само є непослідовним. (Зауважте, що\(\lforall{x_n}{\lnot A_n(x_n)} \Proves \lnot\lexists{x_n}{A_n(x_n)}\).) протиріччя: повинно\(\Gamma_n\) було бути послідовним. Отже\(\Gamma_n \cup \{ D_n\}\), послідовно. ◻

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

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

Припустимо,\(\Gamma\) є повним, послідовним і насиченим.

\(\lexists{x}{A(x)} \in \Gamma\) iff \(A(t) \in \Gamma\) for at least one closed term \(t\).
\(\lforall{x}{A(x)} \in \Gamma\) iff \(A(t) \in \Gamma\) for all closed terms \(t\).

Доказ.

Спочатку припустимо, що\(\lexists{x}{A(x)} \in \Gamma\). Тому що\(\Gamma\) є насиченим,\((\lexists{x}{A(x)} \lif A(c)) \in \Gamma\) для якогось постійного символу\(c\). Пропозиції 8.10.3 і 9.9.3, пункт (1), і Пропозиція 10.3.1 (1),\(A(c) \in \Gamma\).

Для іншого напрямку насичення не потрібно: припустимо\(A(t) \in \Gamma\). Потім\(\Gamma \Proves \lexists{x}{A(x)}\) Пропозиціями 8.11.1 та 9.10.1, пункт (1). За пропозицією 10.3.1 (1),\(\lexists{x}{A(x)} \in \Gamma\).
Вправа.

◻