Теория чистого равенства

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

Эта теория последовательна , но неполна, поскольку непустое множество с обычным отношением равенства обеспечивает интерпретацию, делающую некоторые предложения истинными. Это пример разрешимой теории и фрагмент более выразительных разрешимых теорий, включая монадический класс логики первого порядка (который также допускает унарные предикаты и связан через нормальную форму Сколема ^[2] с ограничениями множеств в программном анализе ) и монадическую теорию второго порядка чистого множества (которая дополнительно допускает квантификацию по предикатам и чья сигнатура распространяется на монадическую логику второго порядка k последователей ^[3] ).

Разрешимость теории чистого равенства была доказана Леопольдом Лёвенгеймом в 1915 году.

Если добавить дополнительную аксиому, утверждающую, что для фиксированного натурального числа m существует ровно m объектов , или добавить схему аксиом, утверждающую, что существует бесконечно много объектов, то полученная теория будет полной .

Чистая теория равенства содержит формулы логики первого порядка с равенством, где единственным предикатным символом является само равенство и нет никаких функциональных символов.

Следовательно, единственная форма атомарной формулы — это где есть (возможно, идентичные) переменные. Синтаксически более сложные формулы могут быть построены, как обычно, в логике первого порядка с использованием пропозициональных связок, таких как и квантификаторы .${\displaystyle x=y}$${\displaystyle x,y}$${\ displaystyle \ земля, \ лор, \ lnot}$${\displaystyle \forall ,\exists }$

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

Следующая формула:

${\displaystyle \forall x,y,z.\ (z=x\lor z=y)}$

истинно, когда множество, интерпретирующее формулу, имеет не более двух элементов.

Эта теория может выразить тот факт, что область интерпретации имеет по крайней мере элементы для константы, используя формулу, которую мы обозначим для константы :${\displaystyle к}$${\displaystyle к}$${\displaystyle D_{k}}$${\displaystyle к}$

${\displaystyle \exists x_{1},\ldots ,x_{k}.\ \bigwedge _{1\leq i<j\leq k}x_{i}\neq x_{j}}$

Используя отрицание, он может затем выразить, что домен имеет более элементов. В более общем смысле, он может ограничить домен, чтобы иметь заданный конечный набор конечных мощностей.${\displaystyle к}$

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

${\displaystyle (\forall x,y,z.\ (z=x\lor z=y))\lor (\exists p,q,r.\ p\neq q\land p\neq r\land q\neq r)}$

В силу полноты логики первого порядка все допустимые формулы доказуемы с использованием аксиом логики первого порядка и аксиом равенства (см. также эквациональную логику ).

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

Чтобы получить исключение квантификатора , можно расширить сигнатуру языка, сохранив при этом определяемые отношения (метод, который работает в более общем случае для монадических формул второго порядка). Другой подход к установлению разрешимости заключается в использовании игр Эренфойхта–Фрессе .

• Список теорий первого порядка
• Эквациональная логика
• Свободная теория

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

• в
• т
• е