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

Не путать с математической моделью .

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

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

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

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

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

История

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

Определение

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

Домен

Основная статья: Область дискурса

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

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

Подпись

Основная статья: Подпись (логика)

Подпись $\sigma =(S,\operatorname {ar} )$ конструкции состоит из:

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

Натуральное число $n=\operatorname {ar} (s)$ символа $s$ называется арностью ​ $s$ потому что это арность интерпретации из $s.$

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

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

Не путать с интерпретацией одной модели в другой модели.

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

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

Примеры

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

Во всех трех случаях мы имеем стандартную подпись, заданную $$\sigma _{f}=(S_{f},\operatorname {ar} _{f})$$ с $S_{f}=\{+,\times ,-,0,1\}$ и $${\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}}$$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

См. Также: Универсальная алгебра § Основные конструкции.

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

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

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

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

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

$(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}}$

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

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

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

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

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

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

Вложения

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

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

$(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^{\mathcal {A}}$, $R^{\mathcal {B}}$ относится к интерпретации символа отношения R теории объекта σ в структуре ${\mathcal {A}}$, ${\mathcal {B}}$ соответственно).

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

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

Пример

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

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

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

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

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

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

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

См. также: Теория моделей § Логика первого порядка и Теория моделей § Определимость.

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

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

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

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

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

Ан $n$-арное отношение $R$ во вселенной (т.е. домене) $M$ структуры ${\mathcal {M}}$ называется определимым (или явно определяемым, ср. определимость по Бету , или $\emptyset$- определяемый или определяемый с помощью параметров из $\emptyset$ ср. ниже), если есть формула $\varphi (x_{1},\ldots ,x_{n})$ такой, что $$R=\{(a_{1},\ldots ,a_{n})\in M^{n}:{\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})\}.$$Другими словами, $R$ определимо тогда и только тогда, когда существует формула $\varphi$ такой, что $$(a_{1},\ldots ,a_{n})\in R\Leftrightarrow {\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})$$это правильно.

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

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

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

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

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

Напомним выше, что $n$-арное отношение $R$ во вселенной $M$ из ${\mathcal {M}}$ явно определимо, если существует формула $\varphi (x_{1},\ldots ,x_{n})$ такой, что $$R=\{(a_{1},\ldots ,a_{n})\in M^{n}:{\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})\}.$$

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

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

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

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

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

+ S и × S арности ( S , S ; S ). − S арности ( S ; S ). 0 S и 1 S арности ( S ).

+ V of arity ( V ,  V ;  V ). − V of arity ( V ;  V ). 0 В арности ( В ).

× арности ( S , V ; V ).

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

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

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

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

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

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

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

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

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

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

Основная статья: Логика второго порядка

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

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

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

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

См. также

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

Ссылки

• Беррис, Стэнли Н.; Санкаппанавар, 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

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

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