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

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

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

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

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

Определение

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

Домен

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

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

Подпись

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

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

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

Функция интерпретации I из ЦЕССИОНАРИЕВ функций и отношений к символам подписи. Каждому функциональному символу f арности n назначается n- мерная функция в области. Каждому символу отношения R арности n назначено n -арное отношение в области. Нулевой функциональный символ c называется постоянным символом , потому что его интерпретация I (c) может быть идентифицирована с постоянным элементом области.

Когда структура (и, следовательно, функция интерпретации) задается контекстом, не делается никаких различий между символом s и его интерпретацией I (s) . Например, если f является двоичным функциональным символом , вместо него просто пишется .

Примеры

Стандартная сигнатура σ f для полей состоит из двух двоичных функциональных символов + и × , из которых могут быть выведены дополнительные символы, такие как унарный функциональный символ - (однозначно определяется с помощью + ) и два постоянных символа 0 и 1 (однозначно определяется с помощью + и × соответственно). Таким образом, структура (алгебра) этой сигнатуры состоит из набора элементов A вместе с двумя бинарными функциями, которые могут быть расширены унарной функцией, и двух выделенных элементов; но нет требования, чтобы он удовлетворял какой-либо из аксиом поля. В рациональных чисел Q , то действительные числа ¨R и комплексные числа C , как и любой другой области, можно рассматривать как сг-структур очевидным образом:

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

с

,   .

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

сложение рациональных чисел,
умножение рациональных чисел,
- функция, которая переводит каждое рациональное число x в - x , а
это число 0 и
это число 1;

и и определяются аналогично.

Но кольцо Z из целых чисел , которое не является полем, также является σ е -структуре таким же образом. Фактически не требуется, чтобы какая-либо из аксиом поля выполнялась в σ f -структуре.

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

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

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

называется (индуцированное) подструктура в случае

  • и иметь такую ​​же подпись ;
  • область содержится в области : ; и
  • интерпретации всех символов функций и отношений совпадают .

Обычное обозначение для этого отношения .

Подмножество области структуры называется замкнутым, если оно замкнуто относительно функций , т. Е. Если выполняется следующее условие: для каждого натурального числа n , каждого n -арного функционального символа f (в сигнатуре ) и всех элементов , результат применения п к п -кратного снова является элементом B : .

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

Если и является замкнутым подмножеством, то является индуцированной подструктурой , где каждому символу σ присваивается ограничение на B его интерпретации в . И наоборот, область индуцированной подструктуры является замкнутым подмножеством.

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

Примеры

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

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

Наиболее очевидный способ определить график представляет собой структуру с подписью сг , состоящий из одного двоичного символа отношения Е . Вершины графа образуют область структуры, а также для двух вершин и б ,   означает , что и Ь соединены ребром. В этом кодировании понятие индуцированной подструктуры более ограничено, чем понятие подграфа . Например, пусть G - граф, состоящий из двух вершин, соединенных ребром, и пусть H - граф, состоящий из тех же вершин, но без ребер. H является подграфом G , но не индуцированной подструктурой. Понятие в теории графов, которое соответствует индуцированным подструктурам, - это понятие индуцированных подграфов.

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

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

Для двух структур и одной и той же сигнатуры σ (σ-) гомоморфизм из в является отображением , сохраняющим функции и отношения. Точнее:

  • Для любого n -арного функционального символа f оператора σ и любых элементов выполняется следующее уравнение:
.
  • Для любого n -арного символа отношения R из σ и любых элементов имеет место следующая импликация:
.

Обозначение для гомоморфизма h из в есть .

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

Гомоморфизм иногда называют сильным, если для любого n -арного символа отношения R и любых элементов, таких что , существуют такие, что и Сильные гомоморфизмы порождают подкатегорию в σ- Hom .

Вложения

(Σ-) гомоморфизм называется (σ-) вложением, если он взаимно однозначен и

  • для любого n -арного символа отношения R из σ и любых элементов имеет место следующая эквивалентность:
.

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

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

Пример

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

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

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

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

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

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

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

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

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

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

Структура называется быть модель из теории T , если язык такой же , как на языке T и каждое предложение в Т удовлетворяется . Так, например, «кольцо» - это структура языка колец, которая удовлетворяет каждой из аксиом колец, а модель теории множеств ZFC - это структура на языке теории множеств, которая удовлетворяет каждой из аксиом ZFC.

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

П -ичное отношение R на вселенной M структуры называется определимые (или явно определим , или - определимо ) , если существует формула φ ( х 1 , ..., х п ) такое , что

Другими словами, R определимо тогда и только тогда, когда существует формула φ такая, что

правильно.

Важным частным случаем является определяемость конкретных элементов. Элемент m из M определим в тогда и только тогда, когда существует формула φ ( x ) такая, что

Возможность определения с параметрами

Отношение R называется определимым с параметрами (или - определимым ), если существует формула φ с параметрами из такой, что R определимо с помощью φ. Каждый элемент структуры можно определить с помощью самого элемента в качестве параметра.

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

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

Напомним, что n- мерное отношение R на универсуме M структуры явным образом определимо, если существует формула φ ( x 1 , ..., x n ) такая, что

Здесь формула φ, используемая для определения отношения R, должна быть над сигнатурой, поэтому φ может не упоминать сам R , поскольку R не входит в сигнатуру . Если в расширенном языке существует формула φ, содержащая язык и новый символ R , и отношение R является единственным отношением на таком, что , то говорят , что R является неявно определимым над .

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

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

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

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

  • + S и × S арности ( SSS ).
  • - S арности ( SS ).
  • 0 S и 1 S арности ( S ).
  • + V арности ( VVV ).
  • - V арности ( VV ).
  • 0 В арности ( В ).
  • × арности ( SVV ).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

использованная литература

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