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

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$ є повним, послідовним і насиченим.

1. $\lexists{x}{A(x)} \in \Gamma$ iff $A(t) \in \Gamma$ for at least one closed term $t$.

2. $\lforall{x}{A(x)} \in \Gamma$ iff $A(t) \in \Gamma$ for all closed terms $t$.

Доказ.

1. Спочатку припустимо, що$\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$.

2. Вправа.

◻