Теорія моделей

Одним з найбільш важливих інструментів теорії моделей є теорема компактності, доведена Мальцевим, котра стверджує, що множина формул першого порядку має модель тільки тоді, коли модель має кожна його скінченна підмножина.

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

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

Теорема компактності знаходить використання і в конструюванні нестандартних моделей класичних теорій, наприклад, елементарної арифметики або математичного аналізу.

Теорія ${\displaystyle T}$ — це множина замкнутих формул, замкнутих відносно виводу, тобто якщо є формула ${\displaystyle \varphi }$ слідує з ${\displaystyle T}$, то ${\displaystyle \varphi }$ належить ${\displaystyle T}$.

Теорія, яка має хоч би одну модель, називається несуперечливою, решта теорій — суперечливі.

Теорія ${\displaystyle T}$ називається повною, якщо для будь-якої формули ${\displaystyle \varphi }$ теорія має ${\displaystyle \varphi }$ або ${\displaystyle \lnot \varphi }$. Якщо ${\displaystyle A}$ — Алгебраїчна система, то множина істинних ${\displaystyle A}$ замкнутих формул утворює повну теорію — теорія системи ${\displaystyle A}$, позначувану за допомогою ${\displaystyle Th(A)}$.

Якщо на алгебраїчних системах ${\displaystyle A}$ й ${\displaystyle B}$ істинні одні і ті ж самі формули, то ${\displaystyle A}$ і ${\displaystyle B}$ називаються елементарно еквівалентні. Таким чином, ${\displaystyle A}$ і ${\displaystyle B}$ елементарно еквівалентні тоді і тільки тоді, коли вони моделі однієї і тої самої теорії.

Якщо повна теорія ${\displaystyle T}$ має скінченну модель ${\displaystyle A}$, то всі моделі теорії ${\displaystyle T}$ ізоморфні ${\displaystyle A}$, в тому числі, всі вони містять таку ж кількість елементів. Слідує що, для скінченних алгебраїчних систем, поняття елементарної еквівалентності і ізоморфізму збігаються.

Алгебраїчна система ${\displaystyle B}$ називається підсистемою алгебраїчної системи ${\displaystyle A}$, якщо ${\displaystyle |B|\subseteq |A|}$ і інтерпретація кожного сигнатурного символу в ${\displaystyle B}$ є обмеженням його ж інтерпретації в ${\displaystyle A}$ на множину ${\displaystyle |B|}$. Підсистема називається елементарною, якщо для будь-якої формули ${\displaystyle \varphi (x_{1},\;\ldots ,\;x_{n})}$ і для будь-яких ${\displaystyle b_{1},\;\ldots ,\;b_{n}\in |B|}$ виконано: ${\displaystyle A\models \varphi (b_{1},\;\ldots ,\;b_{n})}$ тоді і тільки тоді, коли ${\displaystyle B\models \varphi (b_{1},\;\ldots ,\;b_{n})}$. Система ${\displaystyle A}$ називається в цих випадках (елементарним) розширенням системи ${\displaystyle B}$.

Елементарна підсистема ${\displaystyle B}$ елементарно еквівалентна ${\displaystyle A}$. Теорії, для моделей котрих вірно і навпаки — кожна елементарна підсистема є підсистемою — називається модельно повною. Модельна повнота теорії ${\displaystyle T}$ еквівалентна кожному з наступних властивостей:

• будь-яка формула в ${\displaystyle T}$ еквівалентна екзистенційній формулі,
• будь-яка формула в ${\displaystyle T}$ еквівалентна універсальній формулі,
• об'єднання ${\displaystyle T}$ з діаграмою будь-якої моделі породжує повну теорію.

Якщо ${\displaystyle X\subseteq |A|}$ — непорожня множина, то серед всіх підсистем ${\displaystyle A}$, включаючих ${\displaystyle X}$, існує найменша, як а називається найменшою множиною ${\displaystyle X}$. Для елементарної підсистеми в загальному випадку таке твердження невірне.

Кажуть, що теорія ${\displaystyle T}$ має термальні скулемівські функції, якщо для кожної формули ${\displaystyle \varphi (x,\;{\bar {y}})}$ існує терм ${\displaystyle t_{\varphi }({\bar {y}})}$ і з теорії ${\displaystyle T}$ слідує формула ${\displaystyle (\forall {\bar {y}})((\exists x)\varphi (x,\;{\bar {y}})\to \varphi (t_{\varphi }({\bar {y}}),\;{\bar {y}}))}$. Інакше кажучи, якщо існує елемент, на якому формула ${\displaystyle \varphi (x,\;{\bar {y}})}$ істинна, то як цей елемент можна взяти ${\displaystyle t({\bar {y}})}$. Якщо теорія має нормальні скулемівські функції, то вона модельно повна. Кожна теорія ${\displaystyle T}$ має розширення ${\displaystyle T^{s}}$, яке має термальні скулемівські функції. При цьому кожна модель ${\displaystyle A}$ теорії ${\displaystyle T}$ може бути збагачена до моделі ${\displaystyle A^{s}}$ теорії ${\displaystyle T^{s}}$.

Теорема Левенгейма — Скулема «вгору» стверджує, що якщо ${\displaystyle A}$ — алгебраїчна система потужності не менше ${\displaystyle \alpha =|Th(A)|}$, то ${\displaystyle A}$ то має елементарні розширення будь-якої потужності менш чи більш рівної ${\displaystyle \alpha }$.

Теорема Левенгейма — Скулема «вниз»: якщо ${\displaystyle A}$ — алгебраїчна система потужності ${\displaystyle \alpha }$ і ${\displaystyle \beta =|Th(A)|}$, то ${\displaystyle A}$ має елементарні підсистеми будь-якої потужності між ${\displaystyle \beta }$ і ${\displaystyle \alpha }$.

Множина формул ${\displaystyle A}$ називається множиною аксіом для теорії ${\displaystyle T}$, якщо ${\displaystyle T}$ є ножино слідст^{[прояснити]} ${\displaystyle A}$. Також, сама ${\displaystyle T}$ є множиною аксіом для себе. Якщо для теорії ${\displaystyle T}$ існує скінченна множина аксіом, то вона називається скінченно аксіоматизовною.

Суму алгебраїчних систем називають класами. Клас алгебраїчних систем ${\displaystyle K}$ називається аксіоматизуємий, якщо він є сукупністю моделей деякої теорії ${\displaystyle T}$. В тому випадку множина аксіом для ${\displaystyle T}$ називається також множиною аксіом для ${\displaystyle K}$. Клас ${\displaystyle K}$ звичайно аксіоматизуємий тоді і тільки тоді, коли аксіоматизуємий сам ${\displaystyle K}$ і його доповнення.

Теорія ${\displaystyle T}$ називається стійкою відносно надсистем (відповідно, підсистем), якщо для будь-якої алгебраїчної системи ${\displaystyle A}$ з ${\displaystyle A\models T}$ і ${\displaystyle B\subseteq A}$ (відповідно, ${\displaystyle A\subseteq B}$) слідує, що ${\displaystyle B\models T}$. Теорія ${\displaystyle T}$ стійка відносно підсистем тоді і тільки тоді, коли вона автоматизуєма засобом унвіерсальних формул. Теорія ${\displaystyle T}$ стійка відносно надсистем тоді і тільки тоді, коли вона аксіоматизуєма засобом екзестинційних формул.

Теорія ${\displaystyle T}$ теорія зветься стійкою відносно гомоморфізмів, якщо для будь-якої алгебраїчної системи ${\displaystyle A}$ з ${\displaystyle A\models T}$ слідує, що ${\displaystyle B\models T}$, якщо ${\displaystyle B}$ — гомоморфний образ ${\displaystyle A}$. Теорія ${\displaystyle T}$ стійка відносно гомоморфізмів тоді і тільки тоді, коли вона аксіоматизуєма засобом простих формул (тобто формул, які не мають імплікацію і заперечення).

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

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

При об'єднанні ланцюгів (в тому рахунку неелеменатрних) зберігається істинність ${\displaystyle \forall \exists }$-формул, правдиво і протилежно — якщо формула зберігає свою істинність при об'єднанні будь-яких ланцюгів, то вона еквівалентна деякій ${\displaystyle \forall \exists }$-формулі.

Теорії, які можуть бути аксіоматизовані засобом ${\displaystyle \forall \exists }$-формул називаються індуктивними. За теоремою Ченя — Лося — Сушко теорія ${\displaystyle T}$ є індуктивністю тоді і тільки тоді, коли вона стійка відносно об'єднаних ланцюгів. Важливий приклад індуктивної теорії — теорія полів фіксованої характеристики.

Метод підсистем є найважливішим при побудові алгебраїчних систем з потрібними властивостями.

Нехай ${\displaystyle L}$ — мова. ${\displaystyle \{{\mathcal {A}}_{i}\}_{i\in I}}$ — сім'я алгебраїчних систем, ${\displaystyle {\mathcal {A}}_{i}=\langle M_{i},\;L\rangle }$. прямий вивід алгебраїчних систем ${\displaystyle {\mathcal {A}}_{i}}$, ${\displaystyle i\in I}$, називається алгебраїчна система ${\displaystyle \prod _{i\in I}{\mathcal {A}}_{i}=\left\langle \prod _{i\in I}A_{i},\;L\right\rangle }$, де для кожного предикатного символу ${\displaystyle P\in L}$

${\displaystyle \prod _{i\in I}{\mathcal {A}}_{i}\models P(a_{1},\;\ldots ,\;a_{n_{P}})\Leftrightarrow {\mathcal {A}}_{i}\models P(a_{1i},\;\ldots ,\;a_{n_{P}i})}$ для кожного ${\displaystyle i\in I}$;

для кодного функціонального символу ${\displaystyle f\in L}$

${\displaystyle (f(a_{1},\;\ldots ,\;a_{n_{f}}))_{i}=f(a_{1i},\;\ldots ,\;a_{n_{f}i})}$

і для кожного константного символу ${\displaystyle c\in L}$

${\displaystyle (c)_{i}=c.}$

Нехай ${\displaystyle D}$ — фільтр над ${\displaystyle I}$. Визначеним над ${\displaystyle \prod _{i\in I}A_{i}}$ відношення ${\displaystyle a\sim _{D}b\Leftrightarrow \{i\in I\mid a_{i}=b_{i}\}\in D}$. Введемо позначення:

${\displaystyle a/D=\{b\mid b\sim _{D}a\}}$, ${\displaystyle \prod _{i\in I}A_{i}/D=\left\{a/D\mid a\in \prod _{i\in I}A_{i}\right\}.}$

Визначимо алгебраїчну систему ${\displaystyle {\mathcal {A}}=\left\langle \prod _{i\in I}A_{i}/D,\;L\right\rangle }$ наступним чином.

Покладемо для предикатного символу ${\displaystyle P\in L}$

${\displaystyle {\mathcal {A}}\models P(a_{1},\;\ldots ,\;a_{n_{P}})\Leftrightarrow \{i\mid {\mathcal {A}}_{i}\models P(a_{1}i,\;\ldots ,\;a_{n_{P}i})\}\in D,}$

для кожного функціонального символу ${\displaystyle f\in L}$

${\displaystyle f(a_{1}/D,\;\ldots ,\;a_{n_{f}}/D)=f(a_{1},\;\ldots ,\;a_{n})/D}$

і для сталих символі ${\displaystyle c\in L}$

${\displaystyle c=c/D.}$

Визначена таким чином алгебраїчна система ${\displaystyle {\mathcal {A}}}$ зветься фільтрованним виводом систем ${\displaystyle {\mathcal {A}}_{i}}$ по фільтру ${\displaystyle D}$ і позначається ${\displaystyle \prod _{i\in I}{\mathcal {A}}_{i}/D}$. Якщо ${\displaystyle D}$ — ультрафільтр, то ${\displaystyle \prod _{i\in I}{\mathcal {A}}_{i}/D}$ називається ультравивід, якщо все ${\displaystyle {\mathcal {A}}_{i}}$ збігаються і рівні ${\displaystyle {\mathcal {A}}}$, то ${\displaystyle \prod _{i\in I}{\mathcal {A}}_{i}/D}$ називається ультрастепенем ${\displaystyle {\mathcal {A}}}$ і позначається ${\displaystyle {\mathcal {A}}^{I}/D}$.

Основна властивість ультравиводу полягає в тому, що вони зберігають всі пропозиції:

Теорема Лося. Нехай ${\displaystyle L}$ — мова, ${\displaystyle \{{\mathcal {A}}_{i}\}_{i\in I}}$ — сім'я алгебраїчних систем мови ${\displaystyle L}$, ${\displaystyle D}$ — ультрафільтр над ${\displaystyle I}$. Тоді для будь-якої формули ${\displaystyle \varphi ({\overline {x}})}$ мови ${\displaystyle L}$ і будь-якої послідовності ${\displaystyle {\overline {a}}}$ елементів з ${\displaystyle \prod _{i\in I}A_{i}}$

${\displaystyle \prod _{i\in I}{\mathcal {A}}_{i}/D\models \varphi ({\overline {a}}/D)\Leftrightarrow \{i\in I\mid {\mathcal {A}}_{i}\models \varphi ({\overline {a}}_{i})\}\in D.}$

Також теорему компактності можна сформулювати наступним чином.

Теорема компактності. Якщо множина формул локально виконувана в деякому класі ${\displaystyle \mathbf {K} }$, то вона виконувана в деякому ультравивіді систем з ${\displaystyle \mathbf {K} }$.

Теорія ${\displaystyle T}$ з рівністю, яка має скінченну або зліченну сигнатуру, зветься категориною в зліченній потужності, якщо всіїї зліченні нормальні моделі Ізоморфні. Категоричність в даній незліченній потужності визначається аналогічно.