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

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

Історія

Теорія моделей присвячена вивченню фундаментального зв'язку між синтаксисом та семантикою. При цьому, першому в ній відповідає формальна мова, а другому — модель — математична структура, яка допускає деякий опис цією мовою. Теорія моделей виникла як узагальнення існуючих підходів рішень метаматематичних проблем, пов'язаних із алгеброю й математичною логікою. Самі ці підходи існували давно, але при цьому довгий час не розглядались у всій своїй загальності, в рамках однієї науково-філософської парадигми. Природним прикладом в цьому контексті, пов'язаним з п'ятим постулатом Евкліда про паралельну лінію. Сторіччями математикам не вдавалося довести його істинність, доки у XIX столітті Больяї й Лобачевський не збудували неевклідову геометрію, показавши тим самим, що постулат паралельності не може бути ні доведений, ні спростований. З точки зору теорії моделей, це означає, що система аксіом без п'ятого постулату допускає декілька різних моделей, тобто в цьому випадку — декілька варіантів реалізації геометрії.

Таким чином, початкова теорія моделей виросла з таких розділів математики як логіка, універсальна алгебра, теорія множин як узагальнення і закріплення існуючих знань. Тому перші результати теорії моделей з'явились задовго після її «Офіційного» виникнення. Першим таким результатом прийнято вважати теорему Льовенгейма — Сколема (1915). Другим великим результатом стала , доведена Геделем (1930) та Мальцевим (1936).

Класична історія моделей першого порядку

Теорія моделей для класичної логіки першого порядку є історично розвиненим і найбільш яскравим прикладом теоретично-модельного підходу. В ролі моделей тут є множини, що вказує область можливих значень змінних. Функціональні символи інтерпретуються як операції відповідної арності над ними, а предикати — як відношення (більш детально, див. (Логіка першого порядку, інтерпретація)).

Теорема компактності

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

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

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

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

Теорії та елементарна еквівалентність

Теорія ${\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}$ з рівністю, яка має скінченну або зліченну сигнатуру, зветься категориною в зліченній , якщо всі її зліченні нормальні моделі . Категоричність в даній незліченній потужності визначається аналогічно.

Теорія моделей вищих порядків

Теорія скінченних моделей

Примітки

1. Кейслер Г., Чен Ч. Теория моделей. — М.: Мир, 1977. — с. 14.