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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Альфред Тарскі
Tarski 4.jpg
Народився 14 січня 1901(1901-01-14)
Варшава, Польща
Помер 26 жовтня 1983(1983-10-26) (82 роки)
Берклі, Каліфорнія
Громадянство США США
Національність поляк
Галузь наукових інтересів математика, логіка
Заклад Каліфорнійський університет, Берклі
Alma mater Варшавський університет
Відомий завдяки: основи сучасної логіки, формальне поняття істини, теорія моделей

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

Історія виникнення[ред.ред. код]

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

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

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

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

Теорема компактності[ред.ред. код]

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

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

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

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

Теорії та елементарна еквівалентність[ред.ред. код]

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

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

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

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

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

Підсистеми і теореми Лёвенгейма — Скулема[ред.ред. код]

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

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

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

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

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

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

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

Аксіоматизуємість та стійкість[ред.ред. код]

Множина формул A називається множиною аксіом для теорії T, якщо T являється ножино слідст A. Тако ж, сама T є множиною аксіом для себе. Якщо для теорії T існує кінцева множина аксіом, то вона називається кінцево аксіоматизуємою.

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

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

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

Ланцюги[ред.ред. код]

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

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

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

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

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

Ультравивід[ред.ред. код]

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

\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_Pi}) для кожного i \in I;

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

(f(a_1,\;\ldots,\;a_{n_f}))_i=f(a_{1i},\;\ldots,\;a_{n_fi})

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

(c)_i=c.

Нехай D — фільтр над I. Визначеним над \prod_{i\in I}A_i відношення a\sim_D b\Leftrightarrow\{i\in I\mid a_i=b_i\}\in D. Введем позначення:

a/D=\{b\mid b\sim_D a\}, \prod_{i\in I}A_i/D=\left\{a/D\mid a\in\prod_{i\in I}A_i\right\}.

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

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

\mathcal{A}\models P(a_1,\;\ldots,\;a_{n_P})\Leftrightarrow\{i\mid\mathcal{A}_i\models P(a_1i,\;\ldots,\;a_{n_Pi})\}\in D,

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

f(a_1/D,\;\ldots,\;a_{n_f}/D)=f(a_1,\;\ldots,\;a_n)/D

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

c=c/D.

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

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

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

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

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

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

Типи[ред.ред. код]


Категоричність[ред.ред. код]

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

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


Теорія кінцевих моделей[ред.ред. код]


Примітки[ред.ред. код]

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