Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 19
Текст из файла (страница 19)
д. Теперь можно говорить об арифметичностипредикатов, определённых на двоичных словах, имея в виду арифметичность соответствующих предикатов на N.• Предикат «слово x состоит из одних нулей» арифметичен. В самом деле, при переходе к числам ему соответствует предикат«x + 1 есть степень двойки», который (как мы видели) арифметичен.• Предикат «слова x и y имеют одинаковую длину» арифметичен.
В самом деле, это означает, что найдётся степень двойкиc, для которой c − 1 6 x, y < 2c − 1 (именно такой промежутокзаполняют числа, которым соответствуют слова одной длины).Аналогичным образом устанавливается арифметичность предиката «x короче y».• Предикат «слово z является конкатенацией слов x и y» (проще говоря, z получается приписыванием y справа к слову x)арифметичен. В самом деле, его можно выразить так: найдётся слово y 0 из одних нулей, имеющее ту же длину, что и слово[п.
4]Выразимость в арифметике85y, при этом (z + 1) = (x + 1)(y 0 + 1) + (y − y 0 ) (умножение наy 0 + 1 соответствует дописыванию нулей, а добавление y − y 0заменяет нули на буквы слова y).• Предикат «слово x является началом слова y» арифметичен. Всамом деле, это означает, что существует слово t, при которомy есть конкатенация x и t.• То же самое верно для предикатов «x есть конец слова y», «xесть подслово слова y» (последнее означает, что найдутся словаu и v, для которых y есть конкатенация u, x и v; конкатенациятрёх слов выразима через конкатенацию двух).• Существует арифметический трёхместный предикат S(x, a, b),обладающий такими свойствами: (а) для любых a и b множество Sab = {x | S(x, a, b)} конечно; (б) среди множеств Sab приразличных парах a, b встречаются все конечные множества.
Например, в качестве такого предиката можно взять «x короче aи axa есть подслово слова b» (здесь axa есть конкатенация трёхслов: a, x и снова a).В самом деле, ясно, что слово x не длиннее слова b, и потомумножество Sab всегда конечно. С другой стороны, пусть имеется некоторое конечное множество слов x1 , . . . , xn . Положимa = 100 .
. . 001, где число нулей больше длины любого из словxi , и b = ax1 ax2 a . . . axn a.Последнее утверждение не упоминает слова, и больше они нам непонадобятся: достаточно знать, что конечные множества натуральных чисел можно кодировать парами натуральных чисел в описанном смысле.Теперь мы можем выразить, что число x является степенью числа4, следующим образом: существует конечное множество U , котороесодержит число x и обладает таким свойством: всякий элемент u ∈ Uлибо равен 1, либо делится на 4 и u/4 также принадлежит U . Теперьнадо везде заменить множество U на его код u1 , u2 , а утверждениеx ∈ U на S(x, u1 , u2 ), где S — построенный нами кодирующий предикат.Немного сложнее выразить двуместный предикат x = 4k .
Тут хотелось бы сказать так: существует последовательность x0 , x1 , . . . , xk ,для которой x0 = 1, каждый следующий член вчетверо больше предыдущего (xi+1 = 4xi ) и xk = x. Как научиться говорить о после-86Языки первого порядка[гл. 3]довательностях, если мы умеем говорить о множествах? Вспомним,что в терминах теории множеств последовательность есть функция,определённая на начальном отрезке натурального ряда, то есть конечное множество пар {h0, x0 i, h1, x1 i, . .
. , hk, xk i}. Пары можно кодировать числами. Например, можно считать кодом пары hx, yi числоc = (x + y)2 + x, поскольку по нему арифметически восстанавливается x + y (как наибольшее число, квадрат которого не превосходитc), а затем x и y. Теперь конечное множество пар можно заменитьконечным множеством их кодов, которое в свою очередь можно закодировать парой чисел.59. Проведите это рассуждение подробно.60.
Покажите, что двуместный предикат «x есть n-ое по порядку простое число» арифметичен.3.5. Невыразимые предикаты: автоморфизмыМы видели, как можно доказать выразимость некоторых свойств.Сейчас мы покажем, каким образом можно доказывать невыразимость.Начнём с такого примера. Пусть сигнатура содержит двуместный предикат равенства (=) и двуместную операцию сложения (+).Рассмотрим её интерпретацию, носителем которой являются целыечисла, а равенство и сложение интерпретируются стандартным образом. Оказывается, что предикат x > y не является выразимым.Причина очевидна: с точки зрения сложения целые числа устроены симметрично, положительные ничем не отличаются от отрицательных.
Если мы изменим знак у всех переменных, входящих вформулу, то её истинность не может измениться. Но при этом x > yзаменится на x < y, и потому это свойство не является выразимым.Формально говоря, надо доказывать по индукции такое свойство:если формула ϕ указанной сигнатуры истинна при оценке π, то онаистинна и при оценке π 0 , в которой значения всех переменных меняют знак. (Подробно мы объясним это в общей ситуации дальше.)Сформулируем общую схему, которой следует это рассуждение.Пусть имеется некоторая сигнатура σ и интерпретация этой сигнатуры, носителем которой является множество M . Взаимно однозначное отображение α : M → M называется автоморфизмом интерпретации, если все функции и предикаты, входящие в интерпретацию,устойчивы относительно α.
При этом k-местный предикат P назы-[п. 5]Невыразимые предикаты: автоморфизмы87вается устойчивым относительно α, еслиP (α(m1 ), . . . , α(mk )) ⇔ P (m1 , . . . , mk )для любых элементов m1 , . . . , mk ∈ M . Далее, k-местная функция fназывается устойчивой относительно α, еслиf (α(m1 ), . .
. , α(mk )) = α(f (m1 , . . . , mk )).Это определение обобщает стандартное определение автоморфизмадля групп, колец, полей и т. д.Теорема 27. Любой предикат, выразимый в данной интерпретации, устойчив относительно её автоморфизмов. Проведём доказательство этого (достаточно очевидного) утверждения формально.Пусть π — некоторая оценка, то есть отображение, ставящее в соответствие всем индивидным переменным некоторые элементы носителя. Через α ◦ π обозначим оценку, которая получится, если кзначению каждой переменной применить отображение α; другимисловами, α ◦ π(ξ) = α(π(ξ)) для любой переменной ξ.Первый шаг состоит в том, чтобы индукцией по построению терма t доказать такое утверждение: значение терма t при оценке α ◦ πполучается применением α к значению терма t при оценке π:[t](α ◦ π) = α([t](π)).Для переменных это очевидно, а шаг индукции использует устойчивость всех функций интерпретации относительно α.Теперь индукцией по построению формулы ϕ легко доказать такое утверждение:[ϕ](α ◦ π) = [ϕ](π).Мы не будем выписывать эту проверку; скажем лишь, что взаимнаяоднозначность α используется, когда мы разбираем случай кванторов.
(В самом деле, если с одной стороны изоморфизма берётся какой-то объект, то взаимная однозначность позволяет взять соответствующий ему объект с другой стороны изоморфизма.) Теорема 27 позволяет доказать невыразимость какого-то предиката, предъявив автоморфизм интерпретации, относительно которого интересующий нас предикат неустойчив. Вот несколько примеров:• (Z, =, <) Сигнатура содержит равенство и отношение порядка.Интерпретация: целые числа.
Невыразимый предикат: x = 0.Автоморфизм: x 7→ x + 1.88Языки первого порядка[гл. 3]• (Q, =, <, +) Сигнатура содержит равенство, отношение порядка и операцию сложения. Интерпретация: рациональные числа.Невыразимый предикат: x = 1. Автоморфизм: x 7→ 2x.Заметим, что сложение позволяет выразить предикат x = 0.Кроме того, отметим, что вместо рациональных чисел можновзять действительные (но не целые, так как в этом случае единица описывается как наименьшее число, большее нуля).• (R, =, <, 0, 1) Сигнатура содержит равенство, порядок и константы 0 и 1. Интерпретация: действительные числа. Невыразимый предикат: x = 1/2. (Автоморфизм упорядоченного множества R, сохраняющий 0 и 1, но не 1/2, построить легко.)• (R, =, +, 0, 1) Сигнатура содержит равенство, сложение, константы 0 и 1.
Интерпретация: действительные числа. Одноместный предикат x = γ выразим для рациональных γ и невыразим для иррациональных γ.В самом деле, выразимость для рациональных γ очевидна. Невыразимость для иррациональных γ следует из того, что длялюбых двух иррациональных γ1 и γ2 существует автоморфизм,переводящий γ1 в γ2 . (В самом деле, рассмотрим R как бесконечномерное векторное пространство над Q. Векторы 1, γ1линейно независимы и потому их можно дополнить до базисаГамеля (подробности смотри в книжке по теории множеств [6]).Сделаем то же самое с векторами 1, γ2 . Получатся равномощные базисы, после чего мы берём Q-линейный оператор, переводящий 1 в 1 и γ1 в γ2 .)• (C, =, +, ×, 0, 1) В сигнатуру входят предикат равенства, операции сложения и умножения, а также константы 0 и 1. Интерпретация: комплексные числа.
Предикат x = γ, где γ —некоторое комплексное число, выразим для рациональных γ иневыразим для иррациональных γ.В самом деле, если γ иррационально, то оно может быть алгебраическим или трансцендентным. В первом случае рассмотриммногочлен из Q[x] минимальной степени, обращающийся в 0 вточке γ; по предположению он имеет степень больше 1 и потомуимеет другой корень γ 0 . В алгебре доказывается (с использованием трансфинитной индукции или леммы Цорна, а также[п.
6]Элиминация кванторов89базисов трансцендентности), что существует автоморфизм Cнад Q, переводящий γ в γ 0 .В случае трансцендентного γ мы используем такой факт: длялюбых трансцендентных γ1 , γ2 ∈ C существует автоморфизмполя C над Q, который переводит γ1 в γ2 .Отметим, что для поля R вместо C такое рассуждение не проходит, так как это поле не имеет нетривиальных автоморфизмов.(Отношение порядка в нём выразимо: положительные числасуть квадраты, поэтому любой автоморфизм сохраняет порядок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
