Структура (математическая логика)

Сопоставление математических формул с определенным значением в универсальной алгебре и теории моделей.

В универсальной алгебре и теории моделей структура состоит из набора вместе с набором финитных операций и отношений , определенных на нем.

Универсальная алгебра изучает структуры, которые обобщают алгебраические структуры , такие как группы , кольца , поля и векторные пространства . Термин универсальная алгебра используется для структур теорий первого порядка без символов отношений . ^[1] Теория моделей имеет другую сферу применения, которая охватывает более произвольные теории первого порядка , включая фундаментальные структуры, такие как модели теории множеств .

С теоретико-модельной точки зрения структуры — это объекты, используемые для определения семантики логики первого порядка , ср. также теория истины Тарского или семантика Тарского .

Для данной теории в теории моделей структура называется моделью, если она удовлетворяет определяющим аксиомам этой теории, хотя иногда ее понимают как семантическую модель , когда обсуждают это понятие в более общей ситуации математических моделей . Логики иногда называют структуры « интерпретациями », ^[2] тогда как термин «интерпретация» обычно имеет другое (хотя и связанное) значение в теории моделей, см. Интерпретация (теория моделей) .

В теории баз данных структуры без функций изучаются как модели реляционных баз данных в форме реляционных моделей .

История

В контексте математической логики термин « модель » был впервые применен в 1940 году философом Уиллардом Ван Орманом Куайном в связи с математиком Ричардом Дедекиндом (1831–1916), пионером в разработке теории множеств . ^{[3] [4]} С 19 века одним из основных методов доказательства непротиворечивости набора аксиом было создание для него модели.

Определение

Формально структуру можно определить как тройку, состоящую из домена , подписи и функции интерпретации , которая указывает , как подпись должна интерпретироваться в домене. Чтобы указать, что структура имеет определенную сигнатуру, можно назвать ее -структурой . ${\displaystyle {\mathcal {A}}=(A,\sigma ,I)}$ ${\displaystyle A,}$ ${\displaystyle \sigma ,}$ ${\displaystyle I}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma }$

Домен

Область определения структуры — произвольное множество; его также называют базовым набором структуры, ее носителем (особенно в универсальной алгебре), ее вселенной (особенно в теории моделей, ср. «вселенная ») или ее областью дискурса . В классической логике первого порядка определение структуры запрещает пустую область определения . ^{[ нужна ссылка ] [5]}

Иногда для обозначения области используется обозначение или , но часто между структурой и ее областью не проводится никакого различия в обозначениях (то есть один и тот же символ относится как к структуре, так и к ее области). ^[6] ${\displaystyle \operatorname {dom} ({\mathcal {A}})}$ ${\displaystyle |{\mathcal {A}}|}$ ${\displaystyle {\mathcal {A}},}$ ${\displaystyle {\mathcal {A}}}$

Подпись

Сигнатура структуры состоит из: ${\displaystyle \sigma =(S,\operatorname {ar} )}$

• набор функциональных символов и символов отношений , а также ${\displaystyle S}$
• функция , которая приписывает каждому символу натуральное число ${\displaystyle \operatorname {ar} :\ S\to \mathbb {N} _{0}}$ ${\displaystyle s}$ ${\displaystyle n=\operatorname {ar} (s).}$

Натуральное число символа называется арностью потому, что оно представляет собой арность интерпретации ^{[ необходимы} пояснения ^] ${\displaystyle n=\operatorname {ar} (s)}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s.}$

Поскольку подписи, возникающие в алгебре, часто содержат только функциональные символы, подпись без символов отношения называется алгебраической подписью . Структура с такой сигнатурой также называется алгеброй ; это не следует путать с понятием алгебры над полем .

Функция интерпретации

Функция интерпретации присваивает символы подписи функции и отношения. Каждому функциональному символу арности присваивается -арная функция в домене. Каждому символу арности отношения присваивается -арное отношение в области. Нулевой ( -арный) функциональный символ называется постоянным символом , поскольку его интерпретацию можно отождествить с постоянным элементом области определения. ${\displaystyle I}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle f^{\mathcal {A}}=I(f)}$ ${\displaystyle R}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle R^{\mathcal {A}}=I(R)\subseteq A^{\operatorname {ar(R)} }}$ ${\displaystyle =\,0}$ ${\displaystyle c}$ ${\displaystyle I(c)}$

Когда структура (и, следовательно, функция интерпретации) задается контекстом, между символом и его интерпретацией не проводится никакого различия в обозначениях . Например, если это бинарная функция, символ просто пишется, а не ${\displaystyle s}$ ${\displaystyle I(s).}$ ${\displaystyle f}$ ${\displaystyle {\mathcal {A}},}$ ${\displaystyle f:{\mathcal {A}}^{2}\to {\mathcal {A}}}$ ${\displaystyle f^{\mathcal {A}}:|{\mathcal {A}}|^{2}\to |{\mathcal {A}}|.}$

Примеры

Стандартная подпись для полей состоит из двух символов двоичной функции , из которых могут быть получены дополнительные символы, такие как символ унарной функции (однозначно определяемый ) и два константных символа и (однозначно определяемые и соответственно). Таким образом, структура (алгебра) этой сигнатуры состоит из набора элементов вместе с двумя двоичными функциями, которые можно расширить с помощью унарной функции, и двух выделенных элементов; но нет требования, чтобы оно удовлетворяло какой-либо аксиоме поля. Рациональные числа, действительные числа и комплексные числа , как и любое другое поле, можно очевидным образом рассматривать как -структуры: ${\displaystyle \sigma _{f}}$ ${\displaystyle \mathbf {+} }$ ${\displaystyle \mathbf {\times } }$ ${\displaystyle \mathbf {-} }$ ${\displaystyle \mathbf {+} }$ ${\displaystyle \mathbf {0} }$ ${\displaystyle \mathbf {1} }$ ${\displaystyle \mathbf {+} }$ ${\displaystyle \mathbf {\times } }$ ${\displaystyle A}$ ${\displaystyle \mathbb {Q} ,}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {C} ,}$ ${\displaystyle \sigma }$

$${\displaystyle {\begin{alignedat}{3}{\mathcal {Q}}&=(\mathbb {Q} ,\sigma _{f},I_{\mathcal {Q}})\\{\mathcal {R}}&=(\mathbb {R} ,\sigma _{f},I_{\mathcal {R}})\\{\mathcal {C}}&=(\mathbb {C} ,\sigma _{f},I_{\mathcal {C}})\\\end{alignedat}}}$$

Во всех трех случаях мы имеем стандартную подпись, заданную

$${\displaystyle \sigma _{f}=(S_{f},\operatorname {ar} _{f})}$$

^[7] ${\displaystyle S_{f}=\{+,\times ,-,0,1\}}$

$${\displaystyle {\begin{alignedat}{3}\operatorname {ar} _{f}&(+)&&=2,\\\operatorname {ar} _{f}&(\times )&&=2,\\\operatorname {ar} _{f}&(-)&&=1,\\\operatorname {ar} _{f}&(0)&&=0,\\\operatorname {ar} _{f}&(1)&&=0.\\\end{alignedat}}}$$

Функция интерпретации : ${\displaystyle I_{\mathcal {Q}}}$

${\displaystyle I_{\mathcal {Q}}(+):\mathbb {Q} \times \mathbb {Q} \to \mathbb {Q} }$это сложение рациональных чисел,

${\displaystyle I_{\mathcal {Q}}(\times ):\mathbb {Q} \times \mathbb {Q} \to \mathbb {Q} }$это умножение рациональных чисел,

${\displaystyle I_{\mathcal {Q}}(-):\mathbb {Q} \to \mathbb {Q} }$это функция, которая переводит каждое рациональное число в и ${\displaystyle x}$ ${\displaystyle -x,}$

${\displaystyle I_{\mathcal {Q}}(0)\in \mathbb {Q} }$это число и ${\displaystyle 0,}$

${\displaystyle I_{\mathcal {Q}}(1)\in \mathbb {Q} }$это число ${\displaystyle 1;}$

и и определяются аналогично. ^[7] ${\displaystyle I_{\mathcal {R}}}$ ${\displaystyle I_{\mathcal {C}}}$

Но кольцо целых чисел , которое не является полем, точно так же является -структурой. Фактически, не требуется, чтобы какая-либо из аксиом поля выполнялась в -структуре. ${\displaystyle \mathbb {Z} }$ ${\displaystyle \sigma _{f}}$ ${\displaystyle \sigma _{f}}$

Сигнатура для упорядоченных полей требует дополнительного бинарного отношения, такого как или , и поэтому структуры для такой сигнатуры не являются алгебрами, хотя они, конечно, являются алгебраическими структурами в обычном, широком смысле этого слова. ${\displaystyle \,<\,}$ ${\displaystyle \,\leq ,\,}$

Обычная сигнатура теории множеств включает одно бинарное отношение. Структура этой сигнатуры состоит из набора элементов и интерпретации отношения как бинарного отношения на этих элементах. ${\displaystyle \in .}$ ${\displaystyle \in }$

Индуцированные подструктуры и закрытые подмножества

${\displaystyle {\mathcal {A}}}$называется (индуцированной) подструктурой if ${\displaystyle {\mathcal {B}}}$

• ${\displaystyle {\mathcal {A}}}$и у них такая же подпись ${\displaystyle {\mathcal {B}}}$ ${\displaystyle \sigma ({\mathcal {A}})=\sigma ({\mathcal {B}});}$
• область действия содержится в области области и ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}:}$ ${\displaystyle |{\mathcal {A}}|\subseteq |{\mathcal {B}}|;}$
• интерпретации всех символов функций и отношений согласуются друг с другом. ${\displaystyle |{\mathcal {A}}|.}$

Обычное обозначение этого отношения: ${\displaystyle {\mathcal {A}}\subseteq {\mathcal {B}}.}$

Подмножество области определения структуры называется замкнутым, если оно замкнуто относительно функций , то есть если выполняется следующее условие: для каждого натурального числа каждый -арный символ функции (в сигнатуре ) и все элементы являются результатом применение к кортежу снова является элементом ${\displaystyle B\subseteq |{\mathcal {A}}|}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}},}$ ${\displaystyle n,}$ ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle b_{1},b_{2},\dots ,b_{n}\in B,}$ ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle b_{1}b_{2}\dots b_{n}}$ ${\displaystyle B:}$ ${\displaystyle f(b_{1},b_{2},\dots ,b_{n})\in B.}$

Для каждого подмножества существует наименьшее замкнутое подмножество, содержащее его . Оно называется замкнутым подмножеством , порожденным или оболочкой и обозначаемым или . Оператор является оператором финитного замыкания на множестве подмножеств . ${\displaystyle B\subseteq |{\mathcal {A}}|}$ ${\displaystyle |{\mathcal {A}}|}$ ${\displaystyle B.}$ ${\displaystyle B,}$ ${\displaystyle B,}$ ${\displaystyle \langle B\rangle }$ ${\displaystyle \langle B\rangle _{\mathcal {A}}}$ ${\displaystyle \langle \rangle }$ ${\displaystyle |{\mathcal {A}}|}$

Если и является замкнутым подмножеством, то является индуцированной подструктурой где каждому символу σ присваивается ограничение на его интерпретацию. И наоборот, область определения индуцированной подструктуры является замкнутым подмножеством. ${\displaystyle {\mathcal {A}}=(A,\sigma ,I)}$ ${\displaystyle B\subseteq A}$ ${\displaystyle (B,\sigma ,I')}$ ${\displaystyle {\mathcal {A}},}$ ${\displaystyle I'}$ ${\displaystyle B}$ ${\displaystyle {\mathcal {A}}.}$

Замкнутые подмножества (или индуцированные подструктуры) структуры образуют решетку . Встреча двух подмножеств является их пересечением . Соединение двух подмножеств — это замкнутое подмножество, порожденное их объединением . Универсальная алгебра подробно изучает решетку подструктур структуры.

Примеры

Пусть снова будет стандартная подпись для полей. Если рассматривать рациональные числа естественным образом как -структуры, то они образуют подструктуру действительных чисел , а действительные числа образуют подструктуру комплексных чисел . Рациональные числа — это наименьшая подструктура действительных (или комплексных) чисел, которая также удовлетворяет аксиомам поля. ${\displaystyle \sigma =\{+,\times ,-,0,1\}}$ ${\displaystyle \sigma }$

Набор целых чисел дает еще меньшую подструктуру действительных чисел, которая не является полем. Действительно, целые числа представляют собой подструктуру действительных чисел, генерируемых пустым набором с использованием этой сигнатуры. В абстрактной алгебре понятием, которое соответствует подструктуре поля в этой сигнатуре, является понятие подкольца , а не подполя .

Наиболее очевидным способом определения графа является структура с сигнатурой, состоящей из одного символа бинарного отношения. Вершины графа образуют область определения структуры, а для двух вершин и означает, что и соединены ребром. В этом кодировании понятие индуцированной подструктуры является более ограничительным, чем понятие подграфа . Например, пусть это граф, состоящий из двух вершин, соединенных ребром, и пусть это граф, состоящий из тех же вершин, но без ребер. является подграфом, но не индуцированной подструктурой. В теории графов понятием , соответствующим индуцированным подструктурам, является понятие индуцированных подграфов . ${\displaystyle \sigma }$ ${\displaystyle E.}$ ${\displaystyle a}$ ${\displaystyle b,}$ ${\displaystyle (a,b)\!\in {\text{E}}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle G,}$

Гомоморфизмы и вложения

Гомоморфизмы

Для двух структур одинаковой сигнатуры σ (σ-)гомоморфизм из to является отображением , сохраняющим функции и отношения. Точнее: ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle h:|{\mathcal {A}}|\rightarrow |{\mathcal {B}}|}$

• Для каждого n -арного функционального символа f из σ и любых элементов выполняется следующее уравнение: ${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$

${\displaystyle h(f(a_{1},a_{2},\dots ,a_{n}))=f(h(a_{1}),h(a_{2}),\dots ,h(a_{n}))}$.

• Для каждого n -арного символа отношения R σ и любых элементов имеет место следующая импликация: ${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$

${\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R^{\mathcal {A}}\implies (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R^{\mathcal {B}}}$

где , – интерпретация символа отношения теории объекта в структуре соответственно . ${\displaystyle R^{\mathcal {A}}}$ ${\displaystyle R^{\mathcal {B}}}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$

Гомоморфизм h от до обычно обозначается как , хотя технически функция h находится между областями двух структур . ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$ ${\displaystyle |{\mathcal {A}}|}$ ${\displaystyle |{\mathcal {B}}|}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$

Для каждой сигнатуры σ существует конкретная категория σ- Hom , которая имеет σ-структуры в качестве объектов и σ-гомоморфизмы в качестве морфизмов .

Гомоморфизм иногда называют сильным , если: ${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$

• Для каждого n -арного символа отношения R теории объектов и любых таких элементов , что существуют такие, что и ^{[ нужна цитация ] [ сомнительно ]} ${\displaystyle b_{1},b_{2},\dots ,b_{n}\in |{\mathcal {B}}|}$ ${\displaystyle (b_{1},b_{2},\dots ,b_{n})\in R^{\mathcal {B}}}$ ${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$ ${\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R^{\mathcal {A}}}$ ${\displaystyle b_{1}=h(a_{1}),\,b_{2}=h(a_{2}),\,\dots ,\,b_{n}=h(a_{n}).}$

Сильные гомоморфизмы порождают подкатегорию категории σ- Hom , которая была определена выше.

Вложения

(σ-)гомоморфизм называется (σ-) вложением , если он взаимно однозначен и ${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$

• для каждого n -арного символа отношения R σ и любых элементов имеет место следующая эквивалентность: ${\displaystyle a_{1},a_{2},\dots ,a_{n}}$

${\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R^{\mathcal {A}}\iff (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R^{\mathcal {B}}}$

(где, как и раньше , относится к интерпретации символа отношения R теории объекта σ в структуре соответственно ). ${\displaystyle R^{\mathcal {A}}}$ ${\displaystyle R^{\mathcal {B}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$

Таким образом, вложение — это то же самое, что и сильный гомоморфизм, который взаимно однозначен. Категория σ- Emb σ-структур и σ-вложений является конкретной подкатегорией σ- Hom .

Индуцированные подструктуры соответствуют подобъектам в σ- emb . Если σ имеет только функциональные символы, σ- Emb является подкатегорией мономорфизмов σ- Hom . В этом случае индуцированные подструктуры также соответствуют подобъектам в σ- Hom .

Пример

Как видно выше, при стандартном кодировании графов как структур индуцированные подструктуры являются именно индуцированными подграфами. Однако гомоморфизм между графами — это то же самое, что гомоморфизм между двумя структурами, кодирующими граф. В примере из предыдущего раздела, даже несмотря на то, что подграф H группы G не индуцирован, тождественное отображение id:  H  →  G является гомоморфизмом. Это отображение на самом деле является мономорфизмом в категории σ- Hom , и, следовательно, H является подобъектом G , который не является индуцированной подструктурой.

Проблема гомоморфизма

Следующая проблема известна как проблема гомоморфизма :

Для данных двух конечных структур и конечной реляционной сигнатуры найдите гомоморфизм или покажите, что такого гомоморфизма не существует. ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$

Каждая проблема удовлетворения ограничений (CSP) имеет перевод в проблему гомоморфизма. ^[8] Поэтому сложность CSP можно изучать с помощью методов теории конечных моделей .

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

Структуры и логика первого порядка

Структуры иногда называют «структурами первого порядка». Это вводит в заблуждение, поскольку ничто в их определении не связывает их с какой-либо конкретной логикой, и на самом деле они подходят в качестве семантических объектов как для очень ограниченных фрагментов логики первого порядка, таких как та, которая используется в универсальной алгебре, так и для логики второго порядка . В связи с логикой первого порядка и теорией моделей структуры часто называют моделями , даже когда вопрос «модели чего?» не имеет очевидного ответа.

Отношение удовлетворенности

Каждая структура первого порядка имеет отношение удовлетворения , определенное для всех формул языка, состоящего из языка вместе с постоянным символом, каждый элемент которого интерпретируется как этот элемент. Это отношение определяется индуктивно с использованием Т-схемы Тарского . ${\displaystyle {\mathcal {M}}=(M,\sigma ,I)}$ ${\displaystyle {\mathcal {M}}\vDash \phi }$ ${\displaystyle \,\phi }$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle M,}$

Структура называется моделью теории , если язык ее такой же, как язык и каждое предложение в ней удовлетворяет Так, например, «кольцо» — это структура языка колец, которая удовлетворяет каждому из аксиомы кольца, а модель теории множеств ZFC — это структура на языке теории множеств, которая удовлетворяет каждой из аксиом ZFC. ${\displaystyle {\mathcal {M}}}$ ${\displaystyle T}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle {\mathcal {M}}.}$

Определимые отношения

-арное отношение в универсуме (т.е. области) структуры называется определимым (или явно определяемым , см. определимость по Бету , или определимым по Бету , или определяемым с параметрами из см. ниже), если существует формула такая, что ${\displaystyle n}$ ${\displaystyle R}$ ${\displaystyle M}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle \emptyset }$ ${\displaystyle \emptyset }$ ${\displaystyle \varphi (x_{1},\ldots ,x_{n})}$

$${\displaystyle R=\{(a_{1},\ldots ,a_{n})\in M^{n}:{\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})\}.}$$

${\displaystyle R}$ ${\displaystyle \varphi }$

$${\displaystyle (a_{1},\ldots ,a_{n})\in R\Leftrightarrow {\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})}$$

Важным частным случаем является определимость конкретных элементов. Элемент определим тогда и только тогда, когда существует формула такая, что ${\displaystyle m}$ ${\displaystyle M}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle \varphi (x)}$

$${\displaystyle {\mathcal {M}}\vDash \forall x(x=m\leftrightarrow \varphi (x)).}$$

Определяемость с помощью параметров

Отношение называется определяемым с помощью параметров (или - определяемым ), если существует формула с параметрами ^{[ необходимы пояснения ]} из таких, которые можно определить с помощью . Каждый элемент структуры можно определить с использованием самого элемента в качестве параметра. ${\displaystyle R}$ ${\displaystyle |{\mathcal {M}}|}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle R}$ ${\displaystyle \varphi .}$

Некоторые авторы используют термин «определимый» для обозначения «определимый без параметров ^» , в то время как другие авторы имеют в виду ^« определяемый с параметрами ^» . ^{[ нужна цитата ]} Вообще говоря, соглашение о том, что определимое означает определяемое без параметров, более распространено среди теоретиков множеств, в то время как противоположное соглашение более распространено среди теоретиков моделей.

Неявная определимость

Напомним выше, что -арное отношение во вселенной можно явно определить, если существует такая формула, что ${\displaystyle n}$ ${\displaystyle R}$ ${\displaystyle M}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle \varphi (x_{1},\ldots ,x_{n})}$

$${\displaystyle R=\{(a_{1},\ldots ,a_{n})\in M^{n}:{\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})\}.}$$

Здесь формула, используемая для определения отношения, должна находиться над сигнатурой и поэтому не может упоминать себя, поскольку ее нет в сигнатуре. Если существует формула на расширенном языке, содержащая язык и новый символ, и отношение является только отношение к такому, что тогда называется неявно определимым над ${\displaystyle \varphi }$ ${\displaystyle R}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle \varphi }$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {M}}.}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle R,}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}\vDash \varphi ,}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {M}}.}$

По теореме Бета каждое неявно определяемое отношение является явно определяемым.

Многосортные структуры

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

Векторные пространства , например, можно рассматривать как двухсортированные структуры следующим образом. Двусортная сигнатура векторных пространств состоит из двух сортов V (для векторов) и S (для скаляров) и следующих функциональных символов:

Если V — векторное пространство над полем F , соответствующая двухсортированная структура состоит из векторной области , скалярной области и очевидных функций, таких как векторный ноль , скалярный ноль или скалярное умножение . ${\displaystyle {\mathcal {V}}}$ ${\displaystyle |{\mathcal {V}}|_{V}=V}$ ${\displaystyle |{\mathcal {V}}|_{S}=F}$ ${\displaystyle 0_{V}^{\mathcal {V}}=0\in |{\mathcal {V}}|_{V}}$ ${\displaystyle 0_{S}^{\mathcal {V}}=0\in |{\mathcal {V}}|_{S}}$ ${\displaystyle \times ^{\mathcal {V}}:|{\mathcal {V}}|_{S}\times |{\mathcal {V}}|_{V}\rightarrow |{\mathcal {V}}|_{V}}$

Многосортные структуры часто используются как удобный инструмент, даже если их можно избежать, приложив небольшие усилия. Но они редко определяются строго, потому что явное обобщение является простым и утомительным (а значит, и неблагодарным).

В большинстве математических исследований сортам не уделяется много внимания. Однако многосортная логика естественным образом приводит к теории типов . Как выразился Барт Джейкобс: «Логика всегда является логикой теории типов». Этот акцент, в свою очередь, приводит к категориальной логике , поскольку логика теории типов категорически соответствует одной («общей») категории, охватывая логику, и расслояется на другую («базовую») категорию, охватывающую теорию типов. ^[9]

Другие обобщения

Частичные алгебры

И универсальная алгебра, и теория моделей изучают классы (структур или) алгебр, которые определяются сигнатурой и набором аксиом. В случае теории моделей эти аксиомы имеют форму предложений первого порядка. Формализм универсальной алгебры гораздо более ограничителен; по сути, он допускает только предложения первого порядка, которые имеют форму универсально квантифицированных уравнений между терминами, например x y  ( x  +  y  =  y  +  x ). Одним из следствий является то, что выбор сигнатуры более важен в универсальной алгебре, чем в теории моделей. Например, класс групп, в сигнатуре состоящей из символа бинарной функции × и символа константы 1, является элементарным классом , но не является многообразием . Универсальная алгебра решает эту проблему, добавляя символ унарной функции ⁻¹ . ${\displaystyle \forall }$   ${\displaystyle \forall }$

В случае полей эта стратегия работает только для сложения. Для умножения это не удается, поскольку 0 не имеет обратного мультипликативного числа. Специальной попыткой решить эту проблему было бы определение 0 ⁻¹  = 0. (Эта попытка терпит неудачу, по существу, потому, что с этим определением 0 × 0 ⁻¹  = 1 неверно.) Таким образом, естественным образом приходится допускать частичные функции. , то есть функции, которые определены только в подмножестве своей области определения. Однако существует несколько очевидных способов обобщить такие понятия, как подструктура, гомоморфизм и тождество.

Структуры для типизированных языков

В теории типов существует множество разновидностей переменных, каждая из которых имеет тип . Типы определяются индуктивно; для данных двух типов δ и σ существует также тип σ → δ, который представляет функции от объектов типа σ к объектам типа δ. Структура типизированного языка (в обычной семантике первого порядка) должна включать отдельный набор объектов каждого типа, а для типа функции структура должна иметь полную информацию о функции, представляемой каждым объектом этого типа.

Языки высшего порядка

Существует более одной возможной семантики для логики высшего порядка , как обсуждалось в статье о логике второго порядка . При использовании полной семантики высшего порядка структура должна иметь только юниверс для объектов типа 0, а Т-схема расширяется так, чтобы квантор типа более высокого порядка удовлетворялся моделью тогда и только тогда, когда он дисквотирован. истинный. При использовании семантики первого порядка для каждого типа более высокого порядка добавляется дополнительная сортировка, как в случае с многосортным языком первого порядка.

Структуры, являющиеся собственными классами

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

В «Principia Mathematica » Бертрана Рассела структурам также разрешалось иметь в качестве своей области соответствующий класс.

Смотрите также

• Математическая структура  – ​​Дополнительный математический объект

Примечания

1. Некоторые авторы называют структуры «алгебрами» при обобщении универсальной алгебры, позволяющей использовать как отношения , так и функции.
2. Ходжес, Уилфрид (2009). «Функциональное моделирование и математические модели». В Мейерсе, Энтони (ред.). Философия техники и инженерных наук . Справочник по философии науки. Том. 9. Эльзевир. ISBN 978-0-444-51667-1.
3. Оксфордский словарь английского языка, sv «модель, сущ., смысл I.8.b», июль 2023 г .. Издательство Оксфордского университета. На то, что такие классы составляют модель традиционной системы действительных чисел, указывал Дедекинд.[1]
4. Куайн, Уиллард В.О. (1940). Математическая логика . Том. VI. Нортон.
5. Логическая система, допускающая пустой домен, называется инклюзивной логикой .
6. Как следствие этих соглашений, обозначения также могут использоваться для обозначения мощности области. На практике это никогда не приводит к путанице. ${\displaystyle |{\mathcal {A}}|}$ ${\displaystyle {\mathcal {A}}.}$
7. Примечание: слева относятся к знакам, а справа относятся к натуральным числам и унарной операции минус в ${\displaystyle \mathbf {0} ,\mathbf {1} ,}$ ${\displaystyle \mathbf {-} }$ ${\displaystyle S_{f}.}$ ${\displaystyle 0,1,2,}$ ${\displaystyle -}$ ${\displaystyle N_{0}}$ ${\displaystyle \mathbb {Q} .}$
8. Дживонс, Питер; Коэн, Дэвид; Пирсон, Джастин (1998), «Ограничения и универсальная алгебра», Annals of Mathematics and Artificial Intelligence , 24 : 51–67, doi : 10.1023/A: 1018941030227, S2CID  15244028.
9. Джейкобс, Барт (1999), Категориальная логика и теория типов, Elsevier, стр. 1–4, ISBN 9780080528700

Рекомендации

• Беррис, Стэнли Н.; Санкаппанавар, HP (1981), Курс универсальной алгебры, Берлин, Нью-Йорк: Springer-Verlag
• Чанг, Чен Чунг; Кейслер, Х. Джером (1989) [1973], Теория моделей , Elsevier, ISBN 978-0-7204-0692-4
• Дистель, Рейнхард (2005) [1997], Теория графов, Тексты для выпускников по математике, том. 173 (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-3-540-26183-4
• Эббингауз, Хайнц-Дитер; Флум, Йорг; Томас, Вольфганг (1994), Математическая логика (2-е изд.), Нью-Йорк: Springer, ISBN 978-0-387-94258-2
• Хинман, П. (2005), Основы математической логики , AK Peters , ISBN 978-1-56881-262-5
• Ходжес, Уилфрид (1993), Теория моделей , Кембридж: Издательство Кембриджского университета , ISBN 978-0-521-30442-9
• Ходжес, Уилфрид (1997), Более короткая теория модели , Кембридж: Издательство Кембриджского университета , ISBN 978-0-521-58713-6
• Маркер, Дэвид (2002), Теория моделей: Введение , Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-98760-6
• Пуаза, Бруно (2000), Курс теории моделей: введение в современную математическую логику , Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-98655-5
• Раутенберг, Вольфганг (2010), Краткое введение в математическую логику (3-е изд.), Нью-Йорк : Springer Science+Business Media , doi : 10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6
• Ротмалер, Филипп (2000), Введение в теорию моделей , Лондон: CRC Press , ISBN 978-90-5699-313-9

Внешние ссылки

• Раздел семантики в классической логике (запись в Стэнфордской энциклопедии философии)