Модели теории первого порядка

Среди моделей языка первого порядка выделяются модели, удовлетворяющие набору аксиом. Этот набор и будет определять теорию, а модели, для которых выполнены аксиомы, будут моделями теории.

Теорией (первого порядка) Т в языке L называется произвольное множество предложений языка L.

Таким образом, теория получается из исчисления предикатов добавлением некоторого множества предложений T.

Моделью теории Т называется модель А языка L, такая, что A |= q для всех
q Î Т. Теория Т непротиворечива, если она состоит из непротиворечивого множества предложений. Если существует модель теории Т, то Т называется выполнимой. Множеством аксиом теории Т называется всякое её подмножество å Í Т такое, что для каждого предложения q Î Т существует вывод å q. Если существует конечное множество аксиом, то Т называется конечно аксиоматизируемой.

Рассмотрим теории наиболее часто встречающихся моделей.

Теория частично упорядоченных множеств

Язык L = {£} состоит из одного двухместного предиката. Теория имеет 3 аксиомы:

1) "x"y"z (x £ y & y £ z ® x £ z);

2) "x"y (x £ y & y £ x ® x = y);

3) "x (x £ x);

Моделями этой теории являются частично упорядоченные множества. Если присоединить аксиому:

4) "x"y (x £ y Ú y £ x),

то получим теорию, моделями которой служат линейно упорядоченные множества.

Теория булевых алгебр

Язык L = {Ç, È, Ø} состоит из символов двух бинарных операций и одной унарной. Теория имеет аксиомы 1 – 6 (разд. 1.11) (все свободные переменные в этих аксиомах превращены в связанные с помощью кванторов всеобщности). Моделями будут булевы алгебры.

Теория групп

Пусть состоит из символов бинарной и унарной операций и константы. Теория групп определяется аксиомами:

1) "x"y"z (x × (y × z) = (x × y) × z);

2) "x (e × x = x & x × e = x);

3) .

Моделями служат группы. Если добавить аксиому коммутативности:

4) "x"y (x × y = y × x),

то получим теорию, моделями которой являются абелевы группы.

Теория чисел

Пусть L = {+, ×, S, 0} состоит из двух бинарных операций + и ×, унарной операции S и символа константы 0. Теория чисел задаётся аксиомами Пеано:

1) "x (Ø(0 = Sx));

2) "x"y(Sx = Sy ® x = y);

3) x + 0 = x;

4) x + Sy = S(x + y);

5) x × 0 = 0;

6) x × Sy = (x × y) + x;

7) для каждой формулы q, не содержащей связанных вхождений .

Аксиома 7 (аксиома индукции) состоит в действительности из бесконечного числа предложений, каждое из которых соответствует некоторой формуле q языка L.

Стандартной моделью теории чисел является модель (w, +, ×, S, 0) с обычными операциями сложения и умножения чисел. Операция S интерпретируется как функция S(x) = x + 1. Существуют и нестандартные модели теории чисел.

Теория множеств

Пусть L = {Î}. Добавим логическую связку q «y, служащую сокращением для (q ® y) & (y ® q). Запишем в виде формул аксиомы Цермело-Френкеля(разд. 1.2). Эти аксиомы определяют теорию ZF:

1) $x"y (Ø(y Î x)) (пустое множество);

2) "x"y"z ((z Î x «z Î y) ® (x = y)) (экстенсиональность);

3) "u"v$x"z (z Î x «z = u Ú z = v) (пара);

4) "x$y"z"u (u Î z & z Î x ® u Î y) (объединение);

5) "x$y"u ("v(v Î u ® v Î x) ® u Î y) (множество подмножеств);

6) $x ($y (y Î x) & "y (y Î x ® $z (y Î z & z Î x))) (бесконечность);

7) (схема аксиом выделения);

8) (схема аксиом подстановки);

9) "u$x (x Î u & "v(Ø(v Î x & v Î u))) (регулярность).

Если добавить к этой системе аксиом аксиому выбора, то получится теория ZFC. Существуют различные модели теории множеств. Далее мы увидим, что существуют модели, в которых число всех множеств счётно.