Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 42
Текст из файла (страница 42)
Сколько элементов в полугруппе с образующими a и b и соотношениями a2 = ˜, b2 = ˜, ab = ba (через ˜ мы обозначаем пустое слово)?(Ответ: 4; это группа (Z/2Z) × (Z/2Z).)Известно, что существуют такие образующие и соотношения, прикоторых проблема равенства слов (выяснить, принадлежат ли дваданных слова одному классу эквивалентности) является алгоритмически неразрешимой (подробнее см.
в [5]). Мы сейчас покажем, чтоэтот вопрос можно свести к вопросу о выводимости некоторой фор-190Теории и модели[гл. 5]мулы в теории полугрупп, так что если бы она была разрешимой, тополучилось бы противоречие.Построение такой формулы происходит весьма естественным образом; мы поясним его на примере. Пусть мы хотим узнать, будутли слова bb и a равны в полугруппе с образующими a и b и соотношениями ab = aa и bab = b. (Другими словами, мы хотим узнать,можно ли из слова bb получить слово a с помощью замен подсловab ↔ aa и bab ↔ b.) Как сформулировать этот вопрос в терминахформул? Напишем такую формулу:∀a∀b ((ab = aa) ∧ (bab = b) → (bb = a)).Она является теоремой теории полугрупп (истинна во всех полугруппах, выводима из аксиом полугрупп) тогда и только тогда, когда слова bb и a эквивалентны в указанной полугруппе, заданнойобразующими и соотношениями.
В самом деле, если одно слово можно получить из другого заменами, то эти замены (в предположенииab = aa и bab = a) ничего не меняют и bb = a, так что написаннаяформула истинна во всех полугруппах.Напротив, если слово a не получается из bb заменой, то существует полугруппа, в которой эта формула не истинна: надо взять какраз полугруппу с образующими a и b и соотношениями ab = aa иbab = b, значением переменной a считать класс слова a, а значениемпеременной b считать класс слова b.
Тогда значением терма ab будеткласс слова ab, равный классу слова aa по построению полугруппы.Аналогичным образом при такой оценке будет истинно и равенствоbab = b. А равенство bb = a не будет истинно, так как значение терма bb есть класс слова bb, значение терма a есть класс слова a, а этиклассы различны по предположению.Таким образом, любой алгоритм, проверяющий истинность формул в классе всех полугрупп, можно было бы использовать для проверки равенства двух слов в полугруппе, заданной образующими исоотношениями. А среди таких полугрупп есть неразрешимые. Теория групп (в которой, помимо ассоциативности, есть ещё аксиомы существования единицы и обратного), также неразрешима,но доказательство этого сложнее, чем для полугрупп. Это и не удивительно, поскольку из неразрешимости теории групп формальновыводится неразрешимость теории полугрупп, как показывает следующая задача.142.
Пусть теория T разрешима, а теория T 0 той же сигнатуры получается из T добавлением конечного числа аксиом. Тогда теория T 0 разре-[п. 4]Неполные и неразрешимые теории191шима. (Указание: дополнительные аксиомы соединяем конъюнкциями ипомещаем в посылку импликации.)Добавление аксиом может сделать неразрешимую теорию разрешимой. Например, как мы уже упоминали, это происходит с теориейгрупп при добавлении аксиомы коммутативности.Теорема ЧёрчаИз сказанного легко следует знаменитая теорема Чёрча о неразрешимости исчисления предикатов:Теорема 70. Не существует алгоритма, проверяющего общезначимость формул первого порядка.В этой формулировке не ограничивается сигнатура (от алгоритма требуется, чтобы он определял общезначимость формулы с произвольным числом предикатных и функциональных символов). Насамом деле неразрешимость возникает уже в совсем простых сигнатурах, как видно из доказательства.
Поскольку теория полугрупп конечно аксиоматизируема, товыводимость формулы F в этой теории равносильна общезначимости формулы A → F , где A — конъюнкция всех аксиом теории полугрупп. Как мы видим, общезначимость неразрешима уже для формулс равенством и одним двуместным функциональным символом (используемым как умножение в полугруппе).Немного другой вариант рассуждения позволяет доказать неразрешимость общезначимости для формул с равенством и одноместными функциональными символами. Заметим, что вопрос о том, можно ли получить одно слово из другого с помощью замены подсловпо правилам, можно свести к вопросу об общезначимости некоторой формулы. Пусть, например, мы снова хотим узнать, можно лииз слова bb получить слово a с помощью замен подслов ab ↔ aa иbab ↔ b.
Для этого напишем формулу∀x (a(b(x)) = a(a(x))) ∧ ∀x (b(a(b(x))) = b(x)) → ∀x (b(b(x)) = a(x)).Несложно понять, что её общезначимость равносильна возможностиполучить a из bb с помощью указанных замен. В самом деле, цепочказамен даёт цепочку равенств, соединяющих b(b(x)) и a(x). Напротив,если замены не переводят bb в a, то существует интерпретация, вкоторой эта формула ложна.
А именно, в качестве носителя этойинтерпретации возьмём множество всех классов слов (в один классвходят слова, получающиеся друг из друга с помощью замен). На192Теории и модели[гл. 5]этих классах корректно определены функции приписывания слевабукв a и b. Более точно, если U — один из классов, то через A(U )мы обозначим класс, содержащий слова au для всех u ∈ U . (Все этислова лежат в одном классе: если u0 получается из u заменами, то иau0 получается из au теми же заменами.) Аналогично мы определяемфункцию B на классах.
Легко понять, что A(B(U )) = A(A(U )) длялюбого класса U . В самом деле, если u — слово из U , то слово auлежит в A(U ), слово bu лежит в B(U ), а слова abu и aau лежат вклассах A(B(U )) и A(A(U )). Но эти слова переводятся друг в другойзаменой ab ↔ aa, и потому два этих класса совпадают. Аналогичноеутверждение верно и для второй замены.
А вот B(B(U )) = A(U )верно не всегда: если в качестве U взять класс пустого слова, тоB(B(U )) будет классом слова bb, а A(U ) будет классом слова a, и попредположению классы будут разными. Так что функции A и B наклассах слов показывают, что наша формула не общезначима.Формальная арифметикаРассмотрим множество натуральных чисел с операциями сложения и умножения и его элементарную теорию Th(N, =, +, ×), то естьмножество всех истинных (в натуральном ряду) формул со сложением и умножением. Это множество, очевидно, полно. Можно доказать(см. [5]), что оно неразрешимо (и, более того, неарифметично, какговорит теорема Тарского).Отсюда следует, что теория Th(N, =, +, ×) не является конечноаксиоматизируемой.
(В самом деле, эта теория полна и неразрешима, и можно сослаться на теорему 67.) Более того, это же рассуждение показывает, что не существует разрешимого множества теоремэтой теории, из которых бы выводились все другие теоремы. Отсюдаследует, что классическая система аксиом формальной арифметики,называемая также арифметикой Пеано (свойства арифметическихопераций плюс аксиомы индукции), не может быть полной: существуют истинные формулы, невыводимые в формальной арифметике.
Это утверждение составляет содержание знаменитой теоремыГёделя о неполноте.143. Покажите, что нельзя добавить к языку теории Th(N, =, +, ×) конечное число выразимых предикатов так, чтобы после этого проходилаэлиминация кванторов. (Указание: арифметическая иерархия не ограничивается никаким конечным числом уровней.)144. Покажите, что элементарная теория целых чисел со сложением иумножением сводится к элементарной теории натуральных чисел со сложением и умножением: по замкнутой формуле ϕ со сложением и умноже-[п.
4]Неполные и неразрешимые теории193нием можно алгоритмически построить формулу ϕ0 с таким свойством: ϕистинна в Z тогда и только тогда, когда ϕ0 истинна в N. (Указание: целыечисла можно кодировать парами натуральных.)145. (Продолжение) Покажите, что верно и обратное: элементарнаятеория натуральных чисел сводится к элементарной теории целых чисел.(Указание. Если бы в целых числах был порядок, это было бы совсем просто. Чтобы его ввести, можно использовать теорему Лагранжа о том, чтовсякое натуральное число представимо в виде суммы четырёх квадратов.)Будет ли теория Th(N, =, +, ×) категоричной в счётной мощности? Другими словами, имеет ли она счётную модель, не изоморфную стандартной? Раньше, для более простых ситуаций, нам удавалось указать такие модели явно. Теперь это не удастся, но есть простое общее рассуждение, устанавливающее существование нестандартной модели. (Оно аналогично рассуждению, использованномупри доказательстве теоремы 5.2.)Рассмотрим последовательность формул E0 (x), E1 (x), E2 (x), .
. .с единственным параметром x, где Ei (x) — любая формула, выражающая в стандартной модели свойство x = i. (Если бы у нас вязыке была константа 1, можно было бы считать Ei (x) бескванторной формулой x = 1 + 1 + . . . + 1, в правой части которой стоит термс i единицами.)Добавим к сигнатуре новую константу c и рассмотрим теорию,получаемую из Th(N, =, +, ×) добавлением счётного семейства формул ¬Ei (c) (по существу мы добавляем формулы c 6= 0, c 6= 1, . . . ,записанные подходящим образом).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
