![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
(1) ├ L (" x)A(x). Далее
(2) ├ L (" x)A(x) ® A(0), АБ1;
(3) ├ L A(0), П3(1,2);
(4) ├ L (" x)A(x) ® A(l), АБ1;
(5) ├ L A(l), П3(1,4);
и так далее. Получили ├ L A(0), ├ L A(l),..., ├ L A(k),....
Пусть теперь ├ L A(k), k = 0,1,2,.... Допустим, что в L формула (" x)A(x) не доказуема. Так как формализм L полон, то
(1) ├ L ù (" x)A(x). Далее
(2) ├ L ù (" x)A(x) ® ($ х) ù А(х), Т12;
(3) ├ L ($х) ù А(х), П3(1,2).
Последняя формула есть некоторая формула ($хk)Вk(х). Тогда
(4) ├ L ($хk)Bk(x) Далее имеем
(5) ├ L ($xk)Bk(x) ® Bk (pk), аксиома Ek;
(6) ├ L Bk(pk),П3(4,5);
(7) ├ L ù А(рk).
Получили, что в формализме L доказуема формула А(рk) и ее отрицание. Противоречие с непротиворечивостью L.
Лемма. Если А(х) есть формула с единственной свободной переменной х, то
├ L ($х)А(х) «(├ L А(0) V ├ L А(1) V...V ├ L A(k) V...).
Доказательство. Пусть ├ L ($х)А(х), Допустим противное: формулы A(k) не доказуемы в L ни при каком k. Так как формализм L полон, то ├ L ù А(0),
├ L ù А(1),..., ├ L ù A(k),...). Тогда
(1) ├ ("x) ù A(x). Далее
(2) ├ ("x) ù A(x) ® ù ($х)А(х), Т14;
(3) ├ ù ($х)А(х), П3(1,2).
Получили, что в исчислении L доказуема формула ù ($х)А(х) и ее отрицание одновременно. Противоречие с непротиворечивостью L. Следовательно, справедливо ├ L А(0) V ├ L A(l) V....
Пусть теперь существует такое натуральное число р, для которого
(1) ├ L A(p). Далее
(2) ├ L А(р) ® ($х)А(х), АБ2;
(3) ├ L ($х)А(х), П3(1,2). Лемма доказана.
Лемма. Всякий непротиворечивый класс К замкнутых формул УИП выполним на множестве натуральных чисел.
Доказательство. Пусть N = {0,1,2,...} есть множество натуральных чисел. Индукцией по построению формул из класса К зададим на N предикаты так, чтобы доказуемые в L формулы стали истинными высказываниями, т.е. покажем, что формулы класса T L, доказуемые в исчислении L, выполнимы на множестве натуральных чисел. Пусть Р(а1,а2,...,аn) - элементарная формула в L, где Р - предикатная буква; а1,а2,...,аn - символы натуральных чисел. В силу полноты L либо ├ L Р(а1,а2,...,аn), либо ├ L ù Р(а1,а2,...,аn). Пусть предикат
P (a1,a2,…,a3) =
Индукцией по глубине k построения формулы покажем, что при так определенных предикатах замкнутые доказуемые в L формулы принимают истинные значения.
БАЗИС. k = 1. Пусть ├ L А. Тогда А есть элементарная формула Р(а1,а2,...,аn), причем ├ L Р(а1,а2,...,аn). Поэтому Р (а 1, а 2,..., а n) = И.
ПРЕДПОЛОЖЕНИЕ ИНДУКЦИИ. Допустим, что все доказуемые в L замкнутые формулы с глубиной построения меньше k при выше определенных на N предикатах принимают значение И.
ШАГ ИНДУКЦИИ. Покажем, что все доказуемые в L замкнутые формулы с глубиной построения k при выше определенных на N предикатах принимают значение И.
Пусть ├ L А, причем формула А имеет глубину построения k. Возможны следующие случаи.
1. А есть ("x)B(x). Тогда
(1) ├ L ("x)B(x). Далее имеем
(2) ├ L ("x)B(x) «(├ L B(0), ├ L B(l),..., ├ L B(p),...);
(3) ├ L B(0), ├ L B(l),..., ├ L B(p),....
Так как глубины построения формул В(р), р = 0,1,2,..., меньше k, то по предположению индукции высказывания
B(0) = И, B(1) = И,..., B(p) = И,....
По смыслу квантора общности высказывание (" х)В(х) истинно.
2. ├ L А и А есть ($х)В(х). Тогда
(1) ├ L ($х)В(х). Далее имеем
(2) ├ L ($х)В(х) «(├ L B(0) V ├ L B(1) V...V ├ L B(p) V...);
(3) ├ L B(0) V ├ L B(l) V... V ├ L B(p) V....
Пусть для определенности ├ L В(р). Так как глубина построения формулы В(р) меньше k, то по предположению индукции высказывание В(р)истинно. По смыслу квантора общности высказывание (" х)В(х) истинно.
3. ├ L А и А есть В & С. Тогда ├ L В & С, откуда по ПВ2 получаем ├ L В и
├ L С. Так как глубины построения формул В и С меньше k, то по предположе-нию индукции высказывания В и С истинны. Тогда В & С истинно, т.е. высказывание А истинно.
Случаи, когда А есть В V С, В ® С, ù В, рассматриваются аналогично.
Итак, все доказуемые в L замкнутые формулы при выше определенных на N предикатах принимают истинные значения. Так как формулы класса К доказуемы в L как аксиомы, то класс К замкнутых формул выполним на множестве натуральных чисел. Иначе говоря, непротиворечивый класс замкнутых формул УИП имеет модель.
Теорема. Всякая замкнутая общезначимая в логике предикатов формула доказуема в УИП.
Доказательство. Пусть А - общезначимая формула логики предикатов. Допустим противное: формула А в УИП не доказуема. Тогда класс формул К = { ù А} непротиворечив и по предыдущей лемме формула ù А выполнима на мно-жестве натуральных чисел. Противоречие с общезначимостью формулы А. Следовательно, общезначимая формула А доказуема в УИП.
Из двух выше доказанных теорем следует следующая теорема.
Теорема (Геделя о полноте). Замкнутая формула доказуема в УИП тогда и только тогда, когда она общезначима.
Замечание. К узкому исчислению предикатов можно добавить специальный предикат равенства х = у и две характеризующие его аксиомы равенства (АР):
AP1) х = х;
АР2) х = у ® (А(х) ® А(у)),
где А(х) - произвольная формула УИП, имеющая свободную переменную х (возможно и другие переменные).
В УИП с равенством справедлива теорема о совпадении класса общезначимых формул (с равенством) и класса формул, доказуемых в УИП (с равенством).
УИП с равенством можно расширить далее, допустив при построении элементарных формул использование функциональных термов. И здесь справедлива выше приведенная теорема.
Заметим еще, что если формула А(Р1,...,Рn) с указанным множеством предикатных переменных доказуема в исчислении предикатов, то можно построить такое ее доказательство, в котором не встречаются предикатные переменные, отличные от Р1,..., Рn.
Дата публикования: 2015-01-23; Прочитано: 179 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!