Интерпретация теории первого порядка

Для придания содержательного смысла формулам УИП сигнатуры W сначала задается область интерпретации – непустое множество M, которое является областью возможных значений всех предметных переменных, и затем на этом множестве M для каждого символа сигнатуры фиксируется соответствующий математический объект: для каждого предикатного символа арности фиксируется -арное отношение на множестве M, для каждого функционального символа арности фиксируется -арная алгебраическая операция на множестве M и для каждого предметного символа фиксируется элемент в множестве M.

В результате получается алгебраическая система с основным множеством M, которая называется алгебраической W-системой и обозначается или просто . Такая система называется также интерпретацией языка УИП сигнатуры W.

Конкретные значения предметным переменным по-прежнему присваиваются с помощью оценок предметных переменных, т.е. отображений a таких переменных в область интерпретации M.

Выполнимость формул теории первого порядка

Выполнимость формулы :

1) при оценке каждый терм интерпретируется в ееэлементом , который получается в результате вычисления для элементов значений соответствующих сигнатурных операций, с помощью которых определяется терм ;

2) если - атомарная формула для термов , то равносильно ;

3) если - атомарная формула вида для n-местного предикатного символа и термов , то равносильно тому, что истинно;

Определение. Винтерпретации M формула F называется:

- общезначимой (или тождественно истинной) и записывается ,если при любых оценках ;

- выполнимой, если для некоторой оценки ;

- опровержимой, если для некоторой оценки неверно, что ;

- тождественно ложной, если для любой оценки неверно, что .

Определение. Интерпретация M языка УИП сигнатуры W называется моделью множества формул S, если в этой интерпретации M тождественно истинны все формулы .

Определение. Формула F называется общезначимой формулой узкого исчисления предикатов сигнатуры W с множеством аксиом S, если она тождественно истинна в любой моделимножества формул S. Множество всех таких общезначимых формул обозначим T_W(S).

Главная цель - определение такой системы нелогических аксиом S, для которой Th_W(S)=T_W(S).

Примеры теорий первого порядка

1. Теория полугрупп. Пусть сигнатура содержит один бинарный функциональный символ , для которого используется инфиксная запись с помощью символа × : для любых предметных переменных x,y терм обозначается , или просто . Тогда термамы сигнатуры : и атомарные формулы: (для некоторых и правильно расставленных скобок).

Рассмотрим систему аксиом S: , выражающую свойство ассоциативности операции умножения.

Моделями множества формул S языка УИП сигнатуры являются алгебры с одной ассоциативной бинарной операцией, которые называются полугруппами.

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

Элементарная теория Th_W(S) называется теорией полугрупп.

2. Теория групп. Пусть содержит один бинарный функциональный символ × (для которого используется прежняя инфиксная запись) и один предметный символ e. Рассмотрим систему аксиом S:

, , .

Моделями множества формул S языка УИП сигнатуры являются алгебры с одной ассоциативной бинарной операцией и одним выделенным элементом, которые называются группами.

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

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

Система аксиом S:

, , .

В этом случае моделями множества формул S языка УИП сигнатуры являются множества с отношением порядка, которые называются упорядоченными множествами.

Элементарная теория Th_W(S) называется теорией упорядоченных множеств.

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

4. Теория вещественных чисел. Пусть сигнатура содержит один бинарный предикатный символ £, два бинарных функциональных символа +, × (для которых используется инфиксная запись) и два предметных символа 0,1. Рассмотрим систему аксиом S:

, ,

, ,

, , ,

, , , ,

где – произвольная формула языка УИП рассматриваемой сигнатуры , содержащая единственную свободную предметную переменную x.

В этом случае элементарная теория Th_W(S) называется теорией вещественных чисел.

Моделью такой теории является, например, множество вещественных чисел R с отношением £ сравнения чисел по величине, бинарными операциями сложения + и умножения × чисел, выделенными числами 0 и 1. Такая модель R=(R;£,+,×,0,1) называется стандартной моделью теории вещественных чисел.

С другой стороны, известно, что эта теория имеет также модели, которые существенно отличаются от стандартной модели R и которые называются нестандартными моделями теории вещественных чисел.

Показательно, что, если последнюю аксиому теории вещественных чисел переформулировать, заменив формулу УИП на неэлементарную формулу для одноместной предикатной переменной X, то полученная система аксиом будет иметь единственную модель – систему вещественных чисел R=(R;£,+,×,0,1).

Но эта аксиоматика уже не является элементарной.

5. Теория арифметики. Сигнатура содержит два бинарных функциональных символа +, × (для которых используется инфиксная запись), один унарных функциональный символ S и один предметный символ 0.

Система аксиом S: , , , , , , ,

где – произвольная формула языка УИП рассматриваемой сигнатуры Ω, содержащая единственную свободную переменную x.

Элементарная теория Th_W(S) называется теорией арифметики и обозначается Ar.

Моделью такой теории является, например, множество неотрицательных целых чисел N₀ с бинарными операциями сложения + и умножения × чисел, унарной операцией и выделенным числом 0. Такая модель N₀=(N₀;+,×,S,0) называется стандартной моделью арифметики.

С другой стороны, известно, что теория Ar имеет также модели, которые существенно отличаются от стандартной модели N₀ и которые называются нестандартными моделями теории арифметики.

Отметим, что теория Arпринято называть также арифметикой Пеано в честь итальянского математика Дж.Пеано, который в 1891 году впервые рассмотрел аксиоматику множества натуральных чисел.

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

если – такое свойство натуральных чисел, что (т.е. 0 обладает этим свойством ) и (т.е. вместе с любым натуральным числом n этим свойством обладает следующее за ним число n+1), то данным свойством обладает каждое натуральное число.

Показательно, что, с одной стороны, аксиоматика Пеано имеет единственную модель – множество натуральных чисел N₀=(N₀;+,×,S,0), но, с другой стороны, последняя аксиома Пеано не может быть выражена на языке УИП рассматриваемой сигнатуры .

Более того, известная теорема Геделя о неполноте формальной арифметики показывает, что множество всех формул языка УИП сигнатуры , тождественно истинных на алгебре N₀=(N₀;+,×,S,0), существенно шире элементарной теории арифметики Ar.

Не нашли, что искали? Воспользуйтесь поиском по сайту: