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

• Разделы:
  • Классическая теория моделей первого порядка
  • Теория моделей высших порядков
  • Теория конечных моделей
  • Примечания

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

Содержание

• 1 История возникновения
• 2 Классическая теория моделей первого порядка
  • 2.1 Теорема компактности
  • 2.2 Теории и элементарная эквивалентность
  • 2.3 Подсистемы и теоремы Лёвенгейма — Скулема
  • 2.4 Аксиоматизируемость и устойчивость
  • 2.5 Цепи
  • 2.6 Ультрапроизведения
  • 2.7 Типы
  • 2.8 Категоричность
• 3 Теория моделей высших порядков
• 4 Теория конечных моделей
• 5 Примечания

История возникновения

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

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

Классическая теория моделей первого порядка

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

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

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

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

Из теоремы компактности следует, что некоторые понятия не являются выразимыми в логике первого порядка. Например, понятия конечностиили счётности не могут быть выражены никакими формулами первого порядка и даже их множествами: если множество формул имеет сколь угодно большие конечные модели, то оно имеет и бесконечную модель. Аналогично, теория, имеющая бесконечную модель, мощность которой не меньше мощности сигнатуры, имеет модели и любой большей мощности.

Теорема компактности находит применение для конструирования нестандартных моделей классических теорий, например, элементарной арифметики или математического анализа.

Теории и элементарная эквивалентность

Теория T{displaystyle T}

  — это множество замкнутных формул, замкнутое относительно выводимости, то есть если формула φ{displaystyle varphi }  следует из T{displaystyle T} , то φ{displaystyle varphi }  принадлежит T{displaystyle T} .

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

Теория T{displaystyle T}

  называется полной, если для любой формулы φ{displaystyle varphi }  теория содержит φ{displaystyle varphi }  или ¬φ{displaystyle lnot varphi } . Если A{displaystyle A}  — алгебраическая система, то множество истинных на A{displaystyle A}  замкнутых формул образует полную теорию — теорию системы A{displaystyle A} , обозначаемую с помощью Th(A){displaystyle Th(A)} .

Если на алгебраических системах A{displaystyle A}

  и B{displaystyle B}  истинны одни и те же замкнутые формулы, то A{displaystyle A}  и B{displaystyle B}  называются элементарно эквивалентными. Таким образом, A{displaystyle A}  и B{displaystyle B}  элементарно эквивалентны тогда и только тогда, когда они являются моделью одной и той же полной теории.

Если полная теория T{displaystyle T}

  имеет конечную модель A{displaystyle A} , то все модели теории T{displaystyle T}  изоморфны A{displaystyle A} ,в частности, все они содержат такое же количество элементов. Следовательно, для конечных алгебраических систем понятия элементарной эквивалентности и изоморфизма совпадают.

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

Алгебраическая система B{displaystyle B}

  называется подсистемой алгебраической системы A{displaystyle A} , если |B|⊆|A|{displaystyle |B|subseteq |A|}  и интерпретация каждого сигнатурного символа в B{displaystyle B}  является ограничением его же интерпретации в A{displaystyle A}  на множество |B|{displaystyle |B|} . Подсистема называется элементарной, если для любой формулы φ(x1,…,xn){displaystyle varphi (x_{1},;ldots ,;x_{n})}  и для любых b1,…,bn∈|B|{displaystyle b_{1},;ldots ,;b_{n}in |B|}  выполнено: A⊨φ(b1,…,bn){displaystyle Amodels varphi (b_{1},;ldots ,;b_{n})}  тогда и только тогда, когда B⊨φ(b1,…,bn){displaystyle Bmodels varphi (b_{1},;ldots ,;b_{n})} . Система A{displaystyle A}  называется в этих случаях (элементарным) расширением системы B{displaystyle B} .

Элементарная подсистема B{displaystyle B}

  элементарно эквивалентна A{displaystyle A} .Теории, для моделей которых верно и обратное — каждая элементарно эквивалентнаяподсистема является элементарной — называются модельно полными.Модельная полнота теории T{displaystyle T}  эквивалентна каждому из следующих свойств:любая формула в T{displaystyle T}  эквивалентна экзистенциальной формуле,любая формула в T{displaystyle T}  эквивалентна универсальной формуле,объединение T{displaystyle T}  с диаграммой любой модели порождает полную теорию.

Если X⊆|A|{displaystyle Xsubseteq |A|}

  — непустое множество, то среди всех подсистем A{displaystyle A} , включающих X{displaystyle X} , существует наименьшая, которая называется порожденной множеством X{displaystyle X} . Для элементарных подсистем в общем случае такое утверждение неверно.

Говорят, что теория T{displaystyle T}

  имеет термальные скулемовские функции, если для каждой формулы φ(x,y¯){displaystyle varphi (x,;{bar {y}})}  существует терм tφ(y¯){displaystyle t_{varphi }({bar {y}})}  и из теории T{displaystyle T}  следует формула (∀y¯)((∃x)φ(x,y¯)→φ(tφ(y¯),y¯)){displaystyle (forall {bar {y}})((exists x)varphi (x,;{bar {y}})to varphi (t_{varphi }({bar {y}}),;{bar {y}}))} . Иначе говоря, если существует элемент, на котором формула φ(x,y¯){displaystyle varphi (x,;{bar {y}})}  истинна, то в качестве этого элемента может быть взято t(y¯){displaystyle t({bar {y}})} . Если теория имеет термальные скулемовские функции,то она модельно полна. Каждая теория T{displaystyle T}  имеет расширение Ts{displaystyle T^{s}} , имеющее термальные скулемовские функции. При этом каждая модель A{displaystyle A}  теории T{displaystyle T}  может быть обогащена до модели As{displaystyle A^{s}}  теории Ts{displaystyle T^{s}} .

Теорема Лёвенгейма — Скулема «вверх» утверждает, что если A{displaystyle A}

  — алгебраическая система мощности не меньше α=|Th(A)|{displaystyle alpha =|Th(A)|} , то A{displaystyle A}  имеет элементарные расширения любой мощности больше или равной α{displaystyle alpha } .Теорема Лёвенгейма — Скулема «вниз»: если A{displaystyle A}  — алгебраическая система мощности α{displaystyle alpha }  и β=|Th(A)|{displaystyle beta =|Th(A)|} ,то A{displaystyle A}  имеет элементарные подсистемы любой мощности между β{displaystyle beta }  и α{displaystyle alpha } .

Аксиоматизируемость и устойчивость

Множество формул A{displaystyle A}

  называется множеством аксиом для теории T{displaystyle T} , если T{displaystyle T}  является множеством следствий A{displaystyle A} . В частности, сама T{displaystyle T}  является множеством аксиом для себя. Если для теории T{displaystyle T}  существует конечное множество аксиом,то она называется конечно аксиоматизируемой.

Совокупности алгебраических систем называют классами. Класс алгебраических систем K{displaystyle K}

  называется аксиоматизируемым, если он является совокупностью моделей некоторой теории T{displaystyle T} . В этом случае множество аксиом для T{displaystyle T}  называется также множеством аксиом для K{displaystyle K} . Класс K{displaystyle K}  конечно аксиоматизируем тогда и только тогда, когда аксиоматизируемы сам K{displaystyle K}  и его дополнение.

Теория T{displaystyle T}

  называется устойчивой относительно надсистем (соответственно, подсистем), если для любой алгебраической системы A{displaystyle A}  из A⊨T{displaystyle Amodels T}  и B⊆A{displaystyle Bsubseteq A}  (соответственно, A⊆B{displaystyle Asubseteq B} ) следует, что B⊨T{displaystyle Bmodels T} .Теория T{displaystyle T}  устойчива относительно подсистем тогда и только тогда, когда она аксиоматизируема посредством универсальных формул.Теория T{displaystyle T}  устойчива относительно надсистем тогда и только тогда, когда она аксиоматизируема посредством экзистенциальных формул.

Теория T{displaystyle T}

  называется устойчивой относительно гомоморфизмов, если для любой алгебраической системы A{displaystyle A}  из A⊨T{displaystyle Amodels T}  следует, что B⊨T{displaystyle Bmodels T} , если B{displaystyle B}  — гомоморфный образ A{displaystyle A} . Теория T{displaystyle T}  устойчива относительно гомоморфизмов тогда и только тогда, когда она аксиоматизируема посредством позитивных формул (то есть формул, не содержащих импликацию и отрицание).

Цепи

Цепью называется множество алгебраических систем,линейно упорядоченное отношением «быть подсистемой».Если для элементов цепи выполняется свойство «быть элементарной подсистемой»,то цепь также называется элементарной.

Объединение цепи алгебраических систем дает новую системутой же сигнатуры, которая будет надсистемой для всехэлементов цепи. При объединении элементарной цепиэто объединение будет элементарной надсистемой и,следовательно, в нем будет сохраняться истинность всех формул.

При объединении любых цепей (в том числе неэлементарных)сохраняется истинность ∀∃{displaystyle forall exists }

 -формул,верно и обратное — если формула сохраняет свою истинностьпри объединении любых цепей, то она эквивалентна некоторой∀∃{displaystyle forall exists } -формуле.

Теории, которые могут быть аксиоматизируемы посредством ∀∃{displaystyle forall exists }

 -формулназываются индуктивными.Согласно теореме Ченя-Лося-Сушко теория T{displaystyle T}  является индуктивной тогда и толькотогда, когда она устойчива относительно объединения цепей.Важный пример индуктивной теории — теория полей фиксированной характеристики.

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

Ультрапроизведения

Пусть L{displaystyle L}

  — язык. {Ai}i∈I{displaystyle {{mathcal {A}}_{i}}_{iin I}}  — семейство алгебраических систем, Ai=⟨Mi,L⟩{displaystyle {mathcal {A}}_{i}=langle M_{i},Lrangle } . Прямым произведением алгебраических систем Ai{displaystyle {mathcal {A}}_{i}} , i∈I{displaystyle iin I} , называется алгебраическая система ∏i∈IAi=⟨∏i∈IAi,L⟩{displaystyle prod _{iin I}{mathcal {A}}_{i}=leftlangle prod _{iin I}A_{i},Lrightrangle } , гдедля каждого предикатного символа P∈L{displaystyle Pin L} 

∏i∈IAi⊨P(a1,…,anP)⇔Ai⊨P(a1i,…,anPi){displaystyle prod _{iin 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})}

  для каждого i∈I{displaystyle iin I} ,

для каждого функционального символа f∈L{displaystyle fin L}

(f(a1,…,anf))i=f(a1i,…,anfi){displaystyle (f(a_{1},ldots ,a_{n_{f}}))_{i}=f(a_{1i},ldots ,a_{n_{f}i})}

и для каждого константного символа c∈L{displaystyle cin L}

(c)i=c{displaystyle (c)_{i}=c}

 .

Пусть D{displaystyle D}

  — фильтр над I{displaystyle I} . Определим на ∏i∈IAi{displaystyle prod _{iin I}A_{i}}  отношение

a∼Db⇔{i∈I∣ai=bi}∈D{displaystyle asim _{D}bLeftrightarrow {iin Imid a_{i}=b_{i}}in D}

 . Введём обозначения:

a/D={b∣b∼Da}{displaystyle a/D={bmid bsim _{D}a}}

 , ∏i∈IAi/D={a/D∣a∈∏i∈IAi}{displaystyle prod _{iin I}A_{i}/D=left{a/Dmid ain prod _{iin I}A_{i}right}} .

Определим алгебраическую систему A=⟨∏i∈IAi/D,L⟩{displaystyle {mathcal {A}}=leftlangle prod _{iin I}A_{i}/D,Lrightrangle }

  следующим образом.Положим для предикатного символа P∈L{displaystyle Pin L} 

A⊨P(a1,…,anP)⇔{i∣Ai⊨P(a1i,…,anPi)}∈D{displaystyle {mathcal {A}}models P(a_{1},ldots ,a_{n_{P}})Leftrightarrow {imid {mathcal {A}}_{i}models P(a_{1}i,ldots ,a_{n_{P}i})}in D}

 ,

для каждого функционального символа f∈L{displaystyle fin L}

f(a1/D,…,anf/D)=f(a1,…,an)/D{displaystyle f(a_{1}/D,ldots ,a_{n_{f}}/D)=f(a_{1},ldots ,a_{n})/D}

и для константных символов c∈L{displaystyle cin L}

c=c/D{displaystyle c=c/D}

 .

Определённая таким образом алгебраическая система A{displaystyle {mathcal {A}}}

  называется фильтрованным произведением систем Ai{displaystyle {mathcal {A}}_{i}}  по фильтру D{displaystyle D}  и обозначается ∏i∈IAi/D{displaystyle prod _{iin I}{mathcal {A}}_{i}/D} . Если D{displaystyle D}  — ультрафильтр, то ∏i∈IAi/D{displaystyle prod _{iin I}{mathcal {A}}_{i}/D}  называется ультрапроизведением, если все Ai{displaystyle {mathcal {A}}_{i}}  совпадают и равны A{displaystyle {mathcal {A}}}  то ∏i∈IAi/D{displaystyle prod _{iin I}{mathcal {A}}_{i}/D}  называется ультрастепенью A{displaystyle {mathcal {A}}}  и обозначается AI/D{displaystyle {mathcal {A}}^{I}/D} .

Основное свойство ультрапроизведений состоит в том, что они сохраняют все предложения:

Теорема Лося. Пусть L{displaystyle L}

  — язык, {Ai}i∈I{displaystyle {{mathcal {A}}_{i}}_{iin I}}  — семейство алгебраических систем языка L{displaystyle L} , D{displaystyle D}  — ультрафильтр над I{displaystyle I} . Тогда для любой формулы ϕ(x¯){displaystyle phi ({overline {x}})}  языка L{displaystyle L}  и любой последовательности a¯{displaystyle {overline {a}}}  элементов из ∏i∈IAi{displaystyle prod _{iin I}A_{i}} 

∏i∈IAi/D⊨ϕ(a¯/D)⇔{i∈I∣Ai⊨ϕ(a¯i)}∈D{displaystyle prod _{iin I}{mathcal {A}}_{i}/Dmodels phi ({overline {a}}/D)Leftrightarrow {iin Imid {mathcal {A}}_{i}models phi ({overline {a}}_{i})}in D}

 .

Также теорему компактности можно сформулировать следующим образом.

Теорема компактности. Если множество формул локально выполнимо в некотором классе K{displaystyle mathbf {K} }

 , то оно выполнимо в некотором ультрапроизведении систем из K{displaystyle mathbf {K} } .

Типы

Категоричность

Теория моделей высших порядков

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

Примечания

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