Доказуемое и недоказуемое - Манин Ю.И.
Скачать (прямая ссылка):
2.13. Следствие.
Если М бесконечно и card ({константы} (J {операции} (J {отношения}) < 2card м, то “ почти все11 множества невыразимы.
Таким образом, единственный способ выразить все подмножества М — набрать огромное количество имен-констант в языке. Для языков, отражающих реальные математические рассуждения, это нереалистический рецепт. По существу, любой финитно описываемый набор средств выражения дает возможность выразить только счетное число множеств. Технически, однако, бывает удобно включать в алфавит языка, скажем, имена всех элементов М.
В следующих параграфах мы приступаем к систематическому изучению множеств истинных формул.
тривиален.
I у*<2| (Ю -
Y*Q 1(П= {
(1, если | ?21 ('')) = 1 для всех •*;, изменений | по х,
\0 иначе,
|1, если | (2 | (?*]'’) = 1 для всех к)', изменений 5' по х, (О иначе.
34
3. СИНТАКСИЧЕСКИЕ СВОЙСТВА ИСТИННОСТИ
Пусть L — язык класса SSJt 9—его интерпретация, TL— множество -истинных формул. В этом параграфе мы перечислим те свойства TL, которые отражают заложенную в языки Х1 логику независимо от конкретных особенностей интерпретации 9.
3.1.
Множество TL полно. По определению это означает, что для любой замкнутой формулы Р, либо Р, либо ~]Р лежит в Т L.
Это следует из утверждения 2.11.
3.2.
Множество TL не содержит противоречия, т. е. ни для какой формулы Р не может быть, чтобы Р и ~] Р лежали в T.L.
Действительно, 7’<pL={P||P|<p=l}, а ПР)в=1 — |Р|?.
3.3.
Множество TL замкнуто относительно применения правил вывода МР (Modus Ponens) и Gen (Generalization — обобщение).
По определению это означает, что если Р и Р—>Q лежат в 7" L, то также Q лежит в TL; если Р лежит в 7^L, то ухР для любой переменной х лежит в ТаL. Проверка почти очевидна: если |Р|=1 и JP—*-Q] = 1, то обязательно \Q\V~ 1; если |Р] (&)== = 1 для всех S, то и | ул:Р| (?) = 1.
Формула Q называется непосредственным следствием формул Р, P-+Q то правилу МР.
Формула ухР называется непосредственным следствием формулы Р по правилу вывода Gen.
Интуитивный смысл правил вывода следующий. Правило МР отвечает элементарному рассуждению типа: Если верно Р и верно, что из верности Р следует верность Q, то верно Q. Таким образом, можно сказать, что семантика выражения «если ..., то» естественных языков распределяется между семантикой связки-»- и правила вывода МР в языках класса 9?\.
Это часто не учитывается и приводит к недоразумениям при объяснении правил приписывания истинности формуле P-»-Q.
Правило Gen соответствует практике записи тождества или универсально верных утверждений в математике. Когда мы пишем (а+b)2=a2 + 2ab + b2 или «в прямоугольном треугольнике квадрат гипотенузы равен сумме квадратов катетов», кванторы yayb, у .(треугольник) опускаются. Восстановление их не меняет истинности, но высвобождает связанные обозначения.
3*
35
3.4.
Множество Т Ь содержит все тавтологии. Чтобы определить
тавтологии, введем сначала понятие логического- многочлена над множеством формул е: это элемент наименьшего множества формул, содержащего е и замкнутого относительно конструкции формул с помощью логических связок.
Последовательность формул Р\, ..., Рп и представлений каждой из формул Рг в виде "] <2 или % '0.2, где 0, 0: 02 лежат в е и {Ри . . Рг-1>, называется представлением Рп в виде логического многочлена над е. Представление Рп не обязательно определено однозначно: например, если е—{Р, О, Р-+0}, то Р-+0 имеет два представления.
Пусть | |: е-^{0, 1} — любое отображение. Если задано пред-
ставление г формулы Рп в виде логического многочлена над е, то можно рекурсивно определить \Рп\г относительно этого представ-, ления, пользуясь формулами п. 2.5.
Формула Р называется тавтологией, если существует такое множество формул е. и такое представление Р в виде логического многочлена над е, что |Р|Г = / для любых отображений I I : е->-^{0, 1}.
Тавтологичность эффективно распознаваема, ибо синтаксический анализ Р позволяет перечислить все представления Р как логического многочлена.
Принадлежность тавтологий к Т Ъ очевидна.
Вот первые примеры тавтологий:
А.О. Р — Р,
А. 1 Р-+(0-+Р),
А.2. (Р->(С^Р))-*((Р_сг)-*(Р-*Р)),
A.З. Р)^(П0-*Р)-*О),
B.1. 1 1Р-*Р, Р— 1 "|Р,
В.2. ПР — (Р — О).
Здесь Р, О, Р — любые формулы Ь; вид формул указывает на то представление тавтологий в виде логического многочлена над {Р, О, Я), которое имеется в виду.
Тавтологии — это рассуждения, истинные, независимо от истинности или ложности своих составных частей. Проверка тавтологичное™ требует достаточно удачного выбора этих частей.
В.1—это закон исключенного третьего: двойное отрицание равносильно утверждению.
В.2 — это механизм, с помощью которого противоречие в некотором множестве формул е языка Ь приводит к выводимости любой формулы и тем самым разрушает всю систему (см. приложение 4.2 ниже.) Продемонстрируем три варианта проверки тавтологичное™ простой формулы А.1.
36
Вариант А. По формулам п. 2.5 имеем |P^(Q^jP)| = 1_|/>| + = i-\P\ + |/>| (1—IQ| +'
+ \P\\Q\) = h
пбо\Р\2=\Р\. т
Вариант Б. Протабулирчем \P-*-(;Q-*~P) | в зависимости от
