Доказуемое и недоказуемое - Манин Ю.И.
Скачать (прямая ссылка):
\р\, IQh
\р\ 1 Q1 | (Q-*P> |
0 0 1 1
0 1 1 1
1 0 0 1
1 1 1 1
Это — образец «таблиц истинности».
Вариант В. Основное свойство связки-хюстоит в том, что Р—*Q ложно, только если Р истинно, a Q ложно. Если бы P->-(Q-*-P) оказалось ложным, то Р было бы истинным, a Q-W3 ложно, откуда, в свою очередь, Q истинно, в Р ложно — противоречие.
Читателю рекомендуется проверить тавтологичность более сложных формул (окажем, А.2) и решить, какой вариант ему больше нравится.
3.5.
Множество Т L содержит “логические аксиомы с кванторами*, т. е. формулы
а) yx(P—+Q)—+(P—*yxQ), если все вхождения х в Р связаны;
б) —ПзхР’>
в) ухР (х)—*Р (t), если х не связывает терм t в Р (аксиома специализации). Здесь P(t) означает результат подстановки t вместо всех свободных вхождений х в Р.
В остальном формулы Р, Q произвольны.
Проверку ф-истинности формул 3.5 мы проведем в п. 3.7. Их интуитивный смысл более или менее ясен. Аксиома специализации, например, означает, что если Р(х) верна для всех х, то верна и P(t), где t — название любого объекта. Условие, чтобы х не связывала t, — гигиеническое правило при перемене обозначений.
Множество
AxL = {тавтологии L} (J {аксиомы с кванторами} называется множеством логических аксиом языка L.
37
Будем называть для краткости гёделевым любое множество формул е языка Б, которое полно, не содержит противоречия, замкнуто относительно применений правил вывода МР и Оеп и содержит все логические аксиомы языка. Зафиксируем основной результат обсуждения:
3.6. Предложение.
Множество истинных формул языка (в данной интерпретации) гёделево.
В § 6 мы докажем, что и, наоборот, любое гёделево множество;, является множеством истинных формул в подходящей интерпретации. Таким образом, гёделевость — это максимальное приближение к истинности, которого можно достичь «безотносительно к смыслу».
3.7. Проверка истинности аксиом 3.5.
а) Пусть Р — формула 3.5а. Допустим, что |Р|(1)=0 для некоторой я придем к противоречию.
Действительно, тогда 1 ух (Р-> С) | (?) = 1 и | Р -* ухф | (11 = 0. Из второго
равенства следует, что |Я|(!)=1 и | ухС} | (1) = 0. Пусть ?'— такое измене-
ние 1 по х, что | <2 | (!') = 0. Тогда | Р | (!') = [ Р | (Ц = 1 в силу предложения 2.10, ибо х не входит в Р свободно. Значит, |Р—>-?2|(1')=0, но это противоречит тому, что 1 ух (Р О) | (1) = 1.
б) Для всех 1 еМ и изменений 1' точки 1 по х имеем ух Д Р\ (1) = шах^| "1 Р\ (!') = 1 = 1 — шш | Р\ (!'),
ТЗ-^К |) = 1-тЩ|Я1(П-
Значит, значения истинности \/х "1 Р и "] дх/5 совпадают, а потому ух "1 Р*—» «—> ”~| дхЯ тождественно истинна.
в) Пусть 1 ухР (х) —? Р (<) ] (1) = 0 для некоторой точки ??=М. Выведем от-сюда противоречие. Действительно, тогда
ухР(х)|(1)= 1; |Р(О|«)=0.
Из первого равенства следует, что |Р(х)|(1') = 1 для всех 1' — изменений 1 ПО X.
Возьмем в качестве 1' такое изменение, для которого Если мы
докажем, что | Р (I) \ (1) = | Р (х) | (!'), то получим желаемое противоречие.
Установим этот результат индукцией по общему числу связок и кванторов в Р.
В() Пусть Р — атомарная формула р(Ц, ..., /„). Последовательно находим,, обозначая через й результат подстановки t вместо всех вхождений х в Б:
Е- = X* (по определению 1');
7}= (индукцией по длине ^).
в2) Пусть Р есть "1 <2 или С,;ф<2г, где связка. Так как по предположе*;
нню х не связывает / в Р, то же верно для <2, <2и (22 и нужный индукционный; шаг производится автоматически.
38
В3) Пусть, наконец, Р есть дуС} или ууО.. Разберем первый случай; второй разбирается аналогично.
Подслучай 1. у=х. Тогда х связана в Р\ поэтому Р(х)=Р(/) и \Р\(?) — \Р\ (1/) п0 предложению 2.4.
Подслучай 2. уфх. Индуктивное предположение имеет вид: 10. (О | (т]) = =) 0. М I (У) > если ^— такое изменение г| по х, что х^'= С*, 'П любая точка из М.
Нужно доказать совпадение следующих двух значений истинности (где |, ?' определены, как выше):
уО- ( ) I (?') 6СЛИ ^ = ^ ДЛЯ нек0Т0Р°® Ч'1 изменения ?' по У»
( 1, если | о (() | (т)) = 1 ДЛЯ некоторой 7), изменения ? по у,
ду7(*) (5) = < А а (0 иначе.
Напомним еще, что у —такое изменение | по х, что х^ —
Предположим сначала, что второе значение истинности равно 1. Выберем т]еЛГ так, что | <2 (/) | (Т1) = 1, и построим такое изменение т\' точки р по х, что хт‘' — <’1. Тогда по индуктивному предположению 1 = | С} (/) | (т|) = |<3 (х) | (т]')-Покажем, что р' есть изменение по у, отсюда будет следовать, что и первое значение истинности равно 1. В самом деле, р' получилось изменением т) по х,
г) — изменением | по у, а | — изменением по х. Значит, р' есть изменение |' по х и у, нужно проверить, что изменение по х на самом деле не произошло: X4' = X*'.
Действительно, левая часть есть ^ по определению р\ а правая часть естч ^ по определению но р получилось изменением > по г/, а г/ не входит в
ибо х не связывает ? в Р=дг^.
Осталось проверить, что если второе значение истинности равно 0, то и первое равно 0. Рассуждения почти такие нее. Если второе значение истинности равно 0, то 1 б? (/) ] (т!) = 0 для всех г| — изменений | по у. По каждому такому 1] построим р', как в первой части доказательства. Как выше, проверяется, что р' является изменением у по у и, более того, пробегает все такие изменения, когда т] пробегает все изменения | по у. Значит, и первое значение истинности равно 0.
