X на терм u, если a не содержит части вида ∃y b, для любой перемен-

ной y из u. Говоря о подстановке, мы всегда подразумеваем допустимую

подстановку.

Пусть A - формула, b—терм.Обозначим через Ax[a] результат замены

каждого свободного вхождения переменной x в формулу A на терм b.

ТЕОРЕМА 13 Результат замены Ax[a] является формулой.

Доказательство самостоятельно индукцией по длине формулы A.

Теперь мы можем перечислить логические аксиомы. Напомним, что

аксиомы делятся на два вида:

• логические аксиомы (в них отражены законы логики, а не специфи-

ческие свойства предметов, которые мы обсуждаем);

• нелогические аксиомы. В них отражены те свойства предметов,

которые мы изучаем в рамках данной теории.

Логические аксиомы имеют следующий вид, где A — произвольная

формула, a—терм.

пропозициональная аксиома ￢A ∨ A ;

аксиома равенства (два вида)

x1 = y1 → x2 = y2 →· · ·→fx1 . . .xn = fy1 . . .yn,

x1 = y1 → x2 = y2 →· · ·→px1 . . .xn → py1 . . .yn

аксиома подстановки Ax[a] → ∃xA;

аксиома тождества x = x.

Аксиома равенства отражает, например, свойство: если предмет x1

совпадает с y1, . . . , xn совпадает с yn, то значение функции fx1 . . .xn

совпадает со значением функции = fy1 . . .yn. Если предмет x1 =

y1, . . . , xn = yn, то справедливость p для x1 . . .xn влечет справедли-

вость для py1 . . .yn.

Правила вывода. Теории первого порядка рассматриваются в виде

формальных систем. Третьей частью формальной системы являются ее

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

вести правила вывода в теориях первого порядка. В этих правилах отра-

жены законы логики, которые мы применяем в математическом доказа-

тельстве.

Имеется пять правил вывода. Четыре из них заимствованы из исчис-

ления высказываний и одно новое.

Правило расширения

A

B ∨ A

(24)

Правило сокращения

A ∨ A

A

(25)

Правило ассоциативности

A ∨ (B ∨ C)

(A ∨ B) ∨ C

(26)

46

Правило сечения.

A ∨ B, ￢A ∨ C

B ∨ C

(27)

Правило ∃ введения.

A → B

∃x A→ B

− где x не является свободной переменной вB. (28)

Лекция 10. Модель теории первого порядка

До сих пор мы рассматривали синтаксис языков первого порядка, то

есть точные правила для построения термов, формул, задания аксиом и

теорем. Наряду с синтаксическим аспектом будем рассматривать семан-

тический аспект теории. Переход от синтаксиса к семантике совершается

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

риваемых как буквы и только, мы начинаем изучать конкретные функции

и предикаты на некотором множестве M. Множество M будем называть

универсумом, а его элементы – индивидами.

Представим, что мы рассматриваем одну из теорий первого порядка—

теорию групп и изучаем семантический аспект. Следовательно, мы долж-

ны рассмотреть конкретную группу. Это означает, что нужно задать кон-

кретное множество, элементы которого являются элементами группы, ко-

торую мы представляем. Вместо бинарного предикатного символа · , рас-

сматриваемой как знак в языке теории групп, мы должны ввести кон-

кретное умножение на множествеM. В общем случае мы должны вместо

функциональных символов f,g,h, . . . рассматривать конкретные функции

на множестве M. Вместо предикатных символов p, q, нужно рассмотреть

конкретные предикаты на множестве M.

Сформулируем обсуждаемые понятия более точно.

Структура для языка первого порядка. Пусть L — язык первого

порядка. Структура A для языка L состоит из следующего.

1. Непустого множества M, называемого универсумом структуры A

( элементы изM называются индивидами структуры);

2. n-арной функции fA из M в M для каждого n-арного функциональ-

ного символа f из L;

3. n-арного предиката pA на M для каждого n-арного предикатного

символа p из L, отличного от =.

Напомним определение функций и предикатов, кото-

рое мы применяем. Пусть M — некоторое множество и

Mn = M × . . . × M—n-ая степень множества M. Элемен-

тами Mn являются всевозможные строки (a1, . . . , an), то есть

Mn = {(a1, . . . , an) | ai ∈ M}.

Если f—некоторая n-арная функция на множествеM, то она являет-

ся сопоставлением (a1, . . . , an) _→ a ∈ M. Таким образом, a1, . . . , an—

значения аргумента, a—значение функции, т.е. f(x1, . . ., xn) = a при

x1 = a1, . . . , xn = an. Аргументы и значения функции берутся из одно-

го и того же множестваM.

n-арным предикатом на множестве M называется произвольное под-

множества R из декартова произведения Mn = M × M × M. . . × M.

Если (a1, . . . , an) ∈ R , то говорят, что элементы a1, . . . ,an находится в

отношении R. При n = 2 записываем a1 R a2.

Поскольку мы имеем конкретные функции и предикаты на множестве ,

то мы сможем приписывать нашим формулам значения истина или ложь.

Вформуле A заменяем значения переменных на конкретные индивиды из

M и приписываем формуле значение Иили Л ( истина или ложь ). При

этом мы будем говорить, что формула A была истинна в A, если все ее

значения истинны.

Пример. Рассмотрим формулу x + y = 3. Возьмем в качестве универ-

сума множество натуральных чисел, функциональный символ + истол-

ковываем как обычное сложение. Заменяем значение переменной x на 2,

а значение переменной y на 1. Значения формулы равно И. При x = 2,

y = 3 значение формулы равно Л.

Опишем процедуру приписывания значение формуле A более точно.

Пусть L — язык первого порядка и A– структура для языка L с уни-

версумом M, n-арными функциями fA, gA, . . . и n-арными предикатами

pA, qA, . . .

Заменим произвольным образом значения переменных x,y,. . . языка L

на конкретные индивиды a,b, . . . изM

x = a, y = b, . . . (29)

По существу это равенство задает отображение переменных языка пер-

вого порядка L в универсум M. Назовем такое отображение интерпрета-

цией.

Рассмотрим произвольный терм u. Он имеет запись fu1u2un, где

u1, . . . , un — ранее построенные термы и f –n-арный функциональный

символ. По теореме об однозначности построения терма части u1, . . . , un

определены однозначно. Далее разберем однозначно на части каждый

из термов u1, . . . , un и т.д. В результате получим сборку u из его ча-

стей. Части, с которых начинается сборка терма u имеют некоторый вид

g(x1, x2, . . .), где x1, x2, . . . — переменные. Они должны заменяться на

конкретные индивиды a1, a2, . . . из M в соответствие с интерпретацией

(29). В терме g(x1, x2, . . .) заменим функциональный символ g на функцию

gA, а переменные x1, x2, . . . на a1, a2, . . .. Получим индивид gA(a1, a2, . . .)

из M. Подставим это значение в качестве аргумента в следующий терм,

участвующий в сборке терма u. Повторив действие несколько раз, полу-

чим значение a ∈ M терма u при интерпретации (29).

Рассмотрим атомную формулу p(u1, u2, . . . , un), где p– n-арный пре-

дикатный символ. Заменим символ p на предикат pA, т.е. на некоторое

подмножества R из декартова произведения Mn = M ×M ×M. . . ×M.

При интерпретации (29) вместо термов u1, u2, . . . , un получатся элементы

a1, . . . , an изM.

Если n-ка элементов (a1, . . . , an) содержится в R, то приписываем

атомной формуле p(u1, . . . , un) значение И, в противном случае – значе-

ние Л.

Рассмотрим процесс приписывания значений И,Л произвольной фор-

муле X.

Напомним, что

1. Атомная формула является формулой

2. Если A и B - произвольные формулы, то ￢A, ∨AB - формулы.

3. Если A - формула, то ∃xA - формула

4. Выражение является формулой тогда и только тогда, когда оно по-

лучено несколькими применениями правил 1-3.

По теореме построения сборка формулы X из ее частей A,B,. . . одно-

значна. Исходный элемент для сборки формулы X —атомные формулы.

При каждой интерпретации (29) атомная формула принимает значение И

или Л. Поэтому нужно лишь указать, как вычислять значение формулы

Y из значений ее частей при построениях вида (2), (3),(4). Обозначаем

значение произвольной формулы Y через V(Y).

• Пусть Y = ￢A. Тогда значение формулы Y противоположно значе-

нию формулы A, т.е. V (Y) = ￢V (A) (если V (A) =И , то V (Y) =–Л

и наоборот);

• Пусть Y = A ∨ B. Тогда V (Y) = V (A) ∨ V (B).

• Пусть Y = ∃xA. Наряду с интерпретацией (29), рассматриваем ин-

терпретации, где значения переменных, отличных от x, те же, что и

в интерпретации (29). Эти значения переменных, отличных от x, со-

четаем с произвольным выбором x = a, x = b, . . . и вычисляем зна-

чение формулы A. Если хотя бы один раз получается значение И,

то формуле Y = ∃xA приписываем значение И, в противном случае

приписываем значение Л.

Пусть T — теория с языком L и A — структура для языка первого

порядка . Тем самым задан универсум M, заданы n-арные функции fA и

n-арные предикаты pA для каждого n-арного функционального символа

f для каждого n-арного предикатного символа p из L. При каждой ин-

терпретации каждая формуле принимает значение Иили Л.

ОПРЕДЕЛЕНИЕ 11 Формула A теории T, называется истинной

в структуре A если при каждой интерпретации формула A при-

нимает значение И.

СтруктураAдля языка L теории T называется моделью теории T, если

при каждой интерпретации все нелогические аксиомы из T принимают

значение И.

Другими словами структура A для языка L теории T —модель теории

T, если все нелогические аксиомы из T истинны в структуре A.

В определении речь идет лишь о нелогических аксиомах, т.к. логиче-

ские аксиомы истинны в любой структуре.

ТЕОРЕМА 14 Пусть A структура для языка L теории T и X —

логическая аксиома теории T. Тогда X истинна в A.

Доказательство. По определению логическая аксиома X имеет один из

видов:

пропозициональная аксиома ￢A ∨ A;

аксиома равенства, имеющая один из видов a) или б)

a) x1 = y1 → x2 = y2 →· · ·→fx1 . . .xn = fy1 . . .yn,

б) x1 = y1 → x2 = y2 →· · ·→px1 . . .xn = py1 . . .yn;

аксиома подстановки Ax[u] → ∃xA;

аксиома тождества x = x.

Рассмотрим произвольную интерпретацию, т.е. заменим значения пере-

менных x,y,. . . на конкретные индивиды a,b, . . . из M; x = a, y = b, . . . .

Вычислим истинностное значение V (X) формулы X.

1 случай, X = ￢A∨A. Тогда V (X) = ￢V (A) ∨ V (A). Если истинност-

ное значение V (A) формулы A равно И, то V (X) = ￢V (A)∨ И=И. Если

V (A)=Л, то V (X) = ￢ Л ∨V (A) =И ∨V (A)= И .

В случае 2, предположим противное, т.е. при некоторой замене в фор-

мула X значений переменных: x1 = a1, y1 = b1, . . . истинностное зна-

чение V (X) равно Л. Тогда посылка a1 = b1 истинна, а заключение

a2 = b2 → · · · → f(a1 . . .an) = f(b1 . . . bn) ложно (напомним, что A → B

–сокращение для ￢A ∨ B и, поэтому, имеет такое правило для приписы-

вания И, Л).

Получили совпадение элементов a1 и b1. Аналогично получаем a2 =

b2, . . .. и ложность равенства f(a1 . . .an) = f(b1 . . . bn).

Тогда совпадение элементов a1 = b1, a2 = b2, . . . влечет совпадение

значений функции f(a1 . . .an) = f(b1 . . . ), противоречие с допущением

f(a1 . . .an) _= f(b1 . . . bn)

В случае 2 б) поступаем аналогично.

Случай 3, X имеет вид Ax[a] → ∃xA.Предположим противное, т.е. при

некоторой интерпретации формула X имеет значение Л. Тогда V (Ax[u])

равно И, V (∃xA) равно Л. Терм u при заменяется при интерпретации на

некоторый элемент a ∈ M. Замена x на этот элемент приводит к значе-

нию V (Ax[a]) равному И. Итак, существует значение переменной x, ко-

торое которое вместе со значениями переменных, отличных от x, таково,

что значение V (A равное И. Тогда значение формулы V (∃xA) равно И,

что противоречит допущению.

Случай 4, X имеет вид x = x. Подставим индивид a переменной x.

Получим a = a.

Предикат= по своему определению должен быть таковым, что резуль-

тат замены a = a имеет значение И. Теорема доказана.