Эта процедура основана на синтаксическом понятии тавтология.
Пусть j высказывание такое, что все высказывательные символы содержатся среди n+1 символов S0,S1,¼Sn. Пусть a0,a1,¼an - последовательность из t и f. Назовем эту последовательность - интерпретацией.
Определение. Значение высказывания j при интерпретации a0,a1,¼an.
(i) j - высказывательный символ Sm, m£n Þ значение j есть am
(ii) j = Øy Þ значение j - противоположно значению y
(iii) j = q&y Þ j=t, если y=t и q=t, иначе j=f
Отметим, что два последних определения сходны. Единственное существенное различие между ними состоит в том, что первое определение оперирует с бесконечной моделью А, в то время как это - только с конечной интерпретацией a0,a1,¼an.
Определение. j - тавтология, (|=j),
если j имеет значение t для любой интерпретации a0,a1,¼an.
Отметим, что знак ‘|=‘ оперирует с семантическими понятиями, а ‘|-’ - с синтаксическими.
А та процедура, о которой мы говорили выше, очень проста - нужно просто построить таблицу истинности! Применение этих таблиц позволяет построить простую и чисто механическую процедуру, определяющую, является ли высказывание j тавтологией, - надо просто выписать таблицу истинности для j и проверить, при всех ли интерпретациях j принимает значение t.
Теорема (о полноте).
|-j Û |=j
(т.е. высказывание является тавтологией тогда и только тогда, когда оно истинно. Эта теорема фактически показывает связь синтаксиса с семантикой.
Доказательство:
Пусть j - высказывание и его высказывательные символы находятся среди S0,S1,¼Sn. Рассмотрим произвольную модель А.
Для m=0,1,...,n положим am=t, если SmÎA
am=f, если SmÎA.
Таким образом, получим некоторую интерпретацию. Докажем теперь вспомогательное утверждение.
Утверждение 1. А|=j Û высказывание j принимает значение t при интерпретации a0,a1,¼an.
Доказательство: по индукции определения высказывания.
(i) j- высказывательный символ Þ очевидно.
(ii) Если утверждение верно для y и q, то оно верно и для Øy, q&y.
■
Þ Если j - тавтология, то по утверждению j - истинно.
Ü т.к. любая интерпретация a0,a1,¼an может быть получена из некоторой модели А, то заключаем, что если j истинно, то оно - тавтология.
■
Таким образом, с помощью нашей разрешающей процедуры для отношения |-j можно также выяснять, истинно ли |j.
4.3.3 Теорема компактности в логике высказываний
Введем теперь понятие формального вывода в нашей логике. Правило отделения (или модус поненс) гласит:
Из высказываний y и y®j выводится j.
Рассмотрим теперь конечное или бесконечное множество высказываний S в языке L.
Определение. Множество высказываний S выполнимо, если имеет хотя бы одну модель.
Определение. Множество высказываний S противоречиво (несовместно), если S|=j для всякого высказывания j, иначе - непротиворечиво (совместно).
Утверждение 2. S противоречиво <=> S |- S&ØS для произвольного SÎL.
Покажем теперь самую важную теорему логики высказываний, дающую критерий выполнимости множества S.
Теорема. (Обобщенная теорема о полноте.)
Множество высказываний S языка L непротиворечиво Û когда оно выполнимо.
Из этой теоремы можно вывести чисто семантическое следствие теорему компактности.
Следствие. (Теорема компактности.)
Если любое конечное подмножество S выполнимо, то всё S выполнимо (Если любое конечное подмножество S имеет модель, то и все S имеет модель. )
Доказательство:
Пусть любое конечное подмножество S выполнимо, а S - невыполнимо.
Тогда по обобщенной теореме о полноте S противоречиво. Тогда по утверждению 2 S |- S&ØS . Но в выводе высказывания S&ØS участвует только конечное множество S0ÌS. Таким образом, S0 |- S&ØS.
Но тогда по утверждению 2 S0 - противоречиво => по обобщенной теореме полноте S0 невыполнимо. Получили противоречие.
■
Заметим, что обратное верно. ( Для любого выполнимого множества - любое его конечное подмножество выполнимо).
Альтернативная формулировка теоремы компактности.
Если S|=j, то $ конечное S0ÍS: S0|=j.
Стандартный пример простого применения теоремы компактности для логики высказываний.
Рассматривается задача о раскраске бесконечной карты k красками так, чтобы каждая страна на карте имела цвет, отличный от всех ее соседей.
Утверждение.
Если бесконечная карта не может быть раскрашена k красками, то некоторая конечная подкарта не может быть раскрашена k красками.
Доказательство:
Каждой стране на карте присваивается к первичных формул (по одной для каждого цвета).
Выписываем тривиальные аксиомы такие, что каждая страна делает истинным ровно один цвет, и соседние страны делают истинными разные цвета.
Получаем бесконечное количество высказываний. Доказательство проведем от противного. Пусть бесконечная карта не может быть раскрашена k красками, а все конечные подкарты могут быть раскрашены соответствующим образом. Тогда, используя теорему компактности, бесконечная карта также может быть раскрашена k красками. Получили противоречие.
■
4.3.4 Что и как можно выразить в логике I порядка.
Формулы логики первого порядка - это конечные цепочки символов, состоящих из символов переменных x, y, z, ¼, логических связок &, Ú, Ø, ®, =, кванторов всеобщности и существования " и $, скобок (,).
Кроме этих логических символов можно ввести множество L примитивных нелогических символов. Например, если мы работаем с абелевыми группами, то множество L состоит из функционального символа + для группового сложения и константного символа 0 для нулевого элемента. При работе с множеством L имеет символ принадлежности Î.
Определение. Теория - множество предложений.
Определение. Теория называется конечно аксиоматизируемой, если она обладает конечным множеством аксиом.
Определение. Множество D называется множеством аксиом теории Г, если Г и D имеют одни и те же следствия.
Определение. j следствие S, если любая модель для S является моделью и для j.
Для нас интересны следующие вопросы:
- Какие теории можно описать с помощью конечного числа аксиом?
- Какие теории нельзя описать с помощью конечного числа аксиом, но можно - с помощью бесконечного?
- Существуют ли теории, которые вообще нельзя описать с помощью логики предикатов первого порядка?
Таким образом эти вопросы приближают нас к пониманию границы применимости, выразимости логики первого порядка.
Так что же можно выразить в логике первого порядка? Ответы на поставленные вопросы мы можем получить, используя стандартный метод для доказательства неаксиоматизируемости теорий - теорему компактности.
Теорема компактности (Гедель - Мальцев)
Пусть Т - произвольное множество аксиом логики первого порядка. Если для каждого конечного подмножества Т0 множества Т существует модель для всех аксиом из Т0, то существует модель для всех аксиом из Т.
Альтернативная форма теоремы компактности:
Если TÈ{y} - множество предложений логики первого порядка, и T|=y (y - логическое следствие из T), то существует конечное T0ÍT: T0|=y.
Это следует из основной формулировки теоремы компактности.
Данная формулировка яснее показывает смысл теоремы, фактически нам говорят:
“Если вы из бесконечной теории выводите y, то вы на самом деле пользуетесь только конечным числом аксиом.”
Теорема компактности не верна для логики высказываний II порядка или даже для слабой логики II порядка.
Применение теоремы компактности. Группы
Рассмотрим пять математических понятий (а)-(f) и попробуем ответить на поставленные вопросы об аксиоматизируемости теорий, используя теорему компактности.
(a) группа,
(b) абелева группа,
(c) абелева группа, в которой порядок любого элемента £ N,
(d) полная группа,
(e) периодическая группа.
Мы можем утверждать, что
(а) - (с) - легко задаются несколькими аксиомами логики первого порядка,
(d) требует бесконечного списка аксиом.
(f) - не является понятием логики первого порядка.
Итак,
группа: G = (G, +, 0), где ‘+’:
"x"y"z [x+(y+z) = (x+y)+z] (1)
"x [x+0 = x] (2)
"x$y [x+y = 0] (3)
Или иначе можем сказать, что G является моделью для (1),(2),(3) и написать G|=(1),(2),(3) вместо того ,чтобы говорить, что G удовлетворяет (1),(2),(3).
(b) абелева группа - группа, удовлетворяющая аксиоме:
"x$y [x+y = y+x] (4)
(c) Введем соглашение: заменяем формальный терм (x+x) термом 2x, ((х+х)+х) => 3х и т.д. (Nx+x)=>(N+1)x.
абелева группа, в которой порядок любого элемента £ N: если G является моделью для выражения
"x [x=0Ú2x=0Ú¼ÚNx=0] (5)
где N - константа
(d) Абелева группа G является полной, если
"n³1 "x$y[ny=x] (6)
Пример - рациональные числа.
(6) не является аксиомой логики первого порядка, т.к. квантор " действует на множестве положительных натуральных чисел, а не рассматриваемой области G. Попытаемся имитировать (6).