29.Теории первого порядка

Теория первого порядка сигнатуры s определяется с помощью аксиом. Интерпретация, при к-ой истинны все аксиомы теории первого порядка G, называется моделью G. Если теория первого порядка G выполнима,то она непротиворечива. Логические следствия теории первого порядка наз-ся её теоремами. Д-во предложения F в теории первого порядка G есть вывод F из подмн-ва аксиом из G.

Теоремы корректности и полноты выполняются для логик предикатов с функциональными символами и равенством и могут быть сформулированы в рамках теорий первого порядка следующим образом. В соответствие с теоремой корректности, если сущ-ет д-во предложения F в теории первого порядка G, тогда F явл-ся теоремой G. В соответствие с теоремой полноты Гёделя, обратное также верно: для любой теоремы F теории первого порядка G,сущ-ет д-во F в G. Однако, добавление правил вывода для кванторов второго порядка ведёт к формальной системе к-ая корректна, но не полна.

Теория линейного порядка

Сигнатура этой теории первого порядка состоит всего из одного символа – бинарной предикатной константы P. Мы будем писать атомарную формулу P(t1, t2) как t1 Ј t2. Аксиомы теории являются универсальным замыканием следующих формул:

1) x Ј x- рефлексивность

2) (x Ј y & y Ј z) Й x Ј z - транзитивность

3) (x Ј y & y Ј x) Й x = y - транзитивность

4) x Ј y Ъ y Ј x - симметричеость

Для любых термов t1 и t2, t1 < t2 обозначает t1 Ј t2 & t1 № t2.

30.Т.Геделя о неполноте. Всякая ω-непротиворечивая и адекватная формальная арифметика не является полной.

Д-во. Мн-во Q натуральных чисел, к-ое перечислимо, но

неразрешимо. Перидикат Р(х, у) такой, что

Q={x:( y)(λ[P(x,y)] = l)}. (*)

Вполне представимость предиката Р(х, у) в формальной

арифметике означает, что найдется такая формула F(x, у) этой теории,

содержащая лишь две свободных предметных переменных, что для

каждой пары натуральных чисел (а, b), для которой λ [Р(а, b)] = 1,

имеет место теорема: ├F{a*, b*),а для каждой пары натуральных

чисел (а, b), для к-ой λ [Р(а, b)] = 0, имеет место теорема: ├ ¬F(a*,b*).

Применим к формуле F(x, у) квантор общности по

переменной у. Получим формулу с единственной свободной предметной переменной

х: G(x) = ( y)(F(x, у)) (**). Покажем, что Q={x:├G(x*)}.Предположим, что mЄQ. Тогда (согласно (*)) найдется такое натуральное n, что выск-ие Р(m, n) истинно.

Сл-но, имеет место теорема:

├ F(m*, n*).

Поскольку наша формальная арифметика, кроме того, ω-непро-

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

существовать такое натуральное число n0, что ф-ла ¬F(m*,n0*)

не явл-ся теоремой этой арифметики. А раз так, то

выск-ие Р(m, n0) истинно. По определению (*) мн-ва Q, это означает, что mЄQ. Таким образом, {x :├G(x*)} Q.

Итак, равенство (**) доказано.