Введение

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

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

История

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

Определение

Формально, структура может быть определена как тройка, состоящая из области определения, сигнатуры и функции интерпретации, которая указывает, как сигнатура интерпретируется на этой области определения. Чтобы указать, что структура имеет определенную сигнатуру, её можно назвать -структурой.

Домен

Домен структуры — это произвольное множество; его также называют базовым множеством структуры, носителем (особенно в универсальной алгебре), вселенной (особенно в теории моделей, см. Вселенная), или областью допустимых значений. В классической логике первого порядка определение структуры исключает пустое доменное пространство. Иногда для обозначения домена структуры используются обозначения или , но часто не делается различий в обозначениях между структурой и её доменом (то есть один и тот же символ обозначает как структуру, так и её домен).

Примеры

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

Пример

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

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

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

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

Каждая структура первого порядка имеет отношение удовлетворения, определенное для всех формул в языке, состоящем из языка вместе с постоянным символом для каждого элемента из , который интерпретируется как этот элемент. Это отношение определяется индуктивно с использованием T-схемы Тарского. Структура называется моделью теории, если язык структуры совпадает с языком теории, и каждое предложение в теории удовлетворяется структурой. Таким образом, например, "кольцо" – это структура для языка колец, удовлетворяющая каждой из аксиом кольца, а модель теории множеств ZFC – это структура в языке теории множеств, удовлетворяющая каждой из аксиом ZFC.

Определяемость с параметрами

Отношение называется определимым с параметрами (или просто определимым), если существует формула с параметрами из некоторой области, такая что это отношение определимо с помощью этой формулы. Каждый элемент структуры определим, используя сам элемент в качестве параметра. Некоторые авторы используют термин "определимое" для обозначения определимости без параметров, а другие – для обозначения определимости с параметрами. В целом, среди теоретиков множеств более распространено соглашение, что "определимое" означает определимое без параметров, а среди теоретиков моделей – противоположное соглашение.

Многосортированные структуры

Структуры, как определено выше, иногда называют односортированными структурами, чтобы отличить их от более общих многосортированных структур. Многосортированная структура может иметь произвольное количество доменов. Сорты являются частью сигнатуры и играют роль имен для различных доменов. Многосортированные сигнатуры также предписывают, на каких сортах определены функции и отношения многосортированной структуры. Следовательно, аритеты символов функций или символов отношений должны быть более сложными объектами, такими как кортежи сортов, а не натуральные числа. Например, векторные пространства можно рассматривать как двухсортированные структуры следующим образом. Двухсортированная сигнатура векторных пространств состоит из двух сортов V (для векторов) и S (для скаляров) и следующих символов функций: +S и ×S с аритетом (S, S; S), −S с аритетом (S; S), 0S и 1S с аритетом (S), +V с аритетом (V, V; V), −V с аритетом (V; V), 0V с аритетом (V), × с аритетом (S, V; V). Если V — векторное пространство над полем F, соответствующая двухсортированная структура состоит из векторного домена, скалярного домена и очевидных функций, таких как векторный ноль, скалярный ноль или скалярное умножение. Многосортированные структуры часто используются как удобный инструмент, даже когда их можно избежать с небольшими усилиями. Но они редко определяются строго, поскольку явное выполнение обобщения — дело прямолинейное, но утомительное (и, следовательно, неблагодарное). В большинстве математических исследований не уделяется особого внимания сортам. Однако многосортированная логика естественным образом приводит к теории типов. Как говорит Барт Джейкобс: «Логика всегда является логикой над теорией типов». Это, в свою очередь, приводит к категориальной логике, поскольку логика над теорией типов категорически соответствует одной («полной») категории, отражающей логику, будучи расслоенной над другой («базовой») категорией, отражающей теорию типов.

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

И универсальная алгебра, и теория моделей изучают классы (структур или) алгебр, которые определяются сигнатурой и набором аксиом. В случае теории моделей эти аксиомы имеют вид формул первого порядка. Формализм универсальной алгебры гораздо более строгий: он по сути допускает только формулы первого порядка, представляющие собой универсально квантифицированные уравнения между термами, например, ∀x∀y (x + y = y + x). Одно из следствий заключается в том, что выбор сигнатуры в универсальной алгебре более значим, чем в теории моделей. Например, класс групп, в сигнатуре, состоящей из бинарной операции × и константы 1, является элементарным классом, но не является разновидностью. Универсальная алгебра решает эту проблему, добавляя унарную операцию −1. В случае полей эта стратегия работает только для сложения. Для умножения она не работает, поскольку 0 не имеет мультипликативной обратной. Попытка обойти это ограничение заключалась бы в определении 0⁻¹ = 0. (Эта попытка терпит неудачу, поскольку при таком определении 0 × 0⁻¹ = 1 не выполняется.) Поэтому естественно прийти к разрешению использовать частичные функции, то есть функции, определенные только на подмножестве своей области определения. Однако существует несколько очевидных способов обобщить такие понятия, как подструктура, гомоморфизм и тождество.

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

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

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

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

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

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