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

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

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

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

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

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

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

История

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

Определение

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

Домен

Область структуры — это произвольное множество; оно также называется базовым множеством структуры, ее носителем (особенно в универсальной алгебре), ее вселенной (особенно в теории моделей, ср. universe ), или ее областью дискурса . В классической логике первого порядка определение структуры запрещает пустую область . ^{[ необходима цитата ] [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}}}$$

Во всех трех случаях мы имеем стандартную сигнатуру, заданную с помощью [ ^7] и $${\displaystyle \sigma _{f}=(S_{f},\operatorname {ar} _{f})}$$ ${\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}}}$называется (индуцированной) подструктурой , если ${\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,}$

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

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

При наличии двух структур и одинаковой сигнатуры σ (σ-)гомоморфизм из в является отображением , которое сохраняет функции и отношения. Точнее: ${\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 можно изучать с помощью методов теории конечных моделей .

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

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

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

Удовлетворенность отношения

Каждая структура первого порядка имеет отношение удовлетворения, определенное для всех формул в языке, состоящем из языка вместе с постоянным символом для каждого элемента которого интерпретируется как этот элемент. Это отношение определяется индуктивно с использованием T-схемы Тарского . ${\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 не имеет мультипликативной инверсии. Попытка ad hoc справиться с этим заключалась бы в определении 0 ⁻¹  = 0. (Эта попытка терпит неудачу, по сути, потому что при таком определении 0 × 0 ⁻¹  = 1 неверно.) Поэтому естественно приходится допускать частичные функции, т. е. функции, которые определены только на подмножестве своей области определения. Однако существует несколько очевидных способов обобщить такие понятия, как подструктура, гомоморфизм и тождество.

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

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

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

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

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

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

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

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

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

Примечания

1. Некоторые авторы называют структуры «алгебрами», обобщая универсальную алгебру, допускающую как отношения, так и функции.
2. Ходжес, Вилфрид (2009). "Функциональное моделирование и математические модели". В Мейерс, Энтони (ред.). Философия технологий и инженерных наук . Справочник по философии науки. Том 9. Elsevier. ISBN 978-0-444-51667-1.
3. Oxford English Dictionary, sv "model, n., sense I.8.b", июль 2023 г. Oxford University Press. Тот факт, что такие классы составляют модель традиционной системы действительных чисел, был отмечен Дедекиндом.[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), «Ограничения и универсальная алгебра», Анналы математики и искусственного интеллекта , 24 : 51–67, doi :10.1023/A:1018941030227, S2CID  15244028.
9. Якобс, Барт (1999), Категориальная логика и теория типов, Elsevier, стр. 1–4, ISBN 9780080528700

Ссылки

• Беррис, Стэнли Н.; Санкаппанавар, Х.П. (1981), Курс универсальной алгебры, Берлин, Нью-Йорк: Springer-Verlag
• Чан, Чэнь Чанг; Кейслер, Х. Джером (1989) [1973], Теория моделей , Elsevier, ISBN 978-0-7204-0692-4
• Дистель, Рейнхард (2005) [1997], Теория графов, Graduate Texts in Mathematics, т. 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), Более короткая модельная теория , Кембридж: Cambridge University Press , 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

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

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