Невыразимые предикаты: автоморфизмы
Мы видели, как можно доказать выразимость некоторых свойств. Сейчас мы покажем, каким образом можно доказывать невыразимость.
Начнем с такого примера. Пусть сигнатура содержит двуместный предикат равенства () и двуместную операцию сложения (). Рассмотрим ее интерпретацию, носителем которой являются целые числа, а равенство и сложение интерпретируются стандартным образом. Оказывается, что предикат не является выразимым.
Причина очевидна: с точки зрения сложения целые числа устроены симметрично, положительные ничем не отличаются от отрицательных. Если мы изменим знак у всех переменных, входящих в формулу, то ее истинность не может измениться. Но при этом заменится на , и потому это свойство не является выразимым.
Формально говоря, надо доказывать по индукции такое свойство: если формула указанной сигнатуры истинна при оценке , то она истинна и при оценке , в которой значения всех переменных меняют знак. (Подробно мы объясним это в общей ситуации дальше.)
Сформулируем общую схему, которой следует это рассуждение. Пусть имеется некоторая сигнатура и интерпретация этой сигнатуры, носителем которой является множество . Взаимно однозначное отображение называется автоморфизмом интерпретации, если все функции и предикаты, входящие в интерпретацию, устойчивы относительно . При этом -местный предикат
называется устойчивым относительно , если
для любых элементов . Аналогичным образом -местная функция называется устойчивой относительно , если
Это определение обобщает стандартное определение автоморфизма для групп, колец, полей и т. д.
Теорема 27. Предикат, выразимый в данной интерпретации, устойчив относительно ее автоморфизмов.
Проведем доказательство этого (достаточно очевидного) утверждения формально.
Пусть — некоторая оценка, то есть отображение, ставящее в соответствие всем индивидным переменным некоторые элементы носителя. Через обозначим оценку, которая получится, если к значению каждой переменной применить отображение ; другими словами, для любой переменной .
Первый шаг состоит в том, чтобы индукцией по построению терма доказать такое утверждение: значение терма при оценке получается применением к значению терма при оценке :
Для переменных это очевидно, а шаг индукции использует устойчивость всех функций интерпретации относительно .
Теперь индукцией по построению формулы легко доказать такое утверждение:
Мы не будем выписывать эту проверку; скажем лишь, что взаимная однозначность используется, когда мы разбираем случай кванторов. (В самом деле, если с одной стороны изоморфизма берется какой-то объект, то взаимная однозначность позволяет взять соответствующий ему объект с другой стороны изоморфизма.)
Теорема 27 позволяет доказать невыразимость какого-то предиката, предъявив автоморфизм интерпретации, относительно которого интересующий нас предикат неустойчив. Вот несколько примеров:
- Сигнатура содержит равенство и отношение порядка. Интерпретация: целые числа. Невыразимый предикат: . Автоморфизм: .
Сигнатура содержит равенство, отношение порядка и операцию сложения. Интерпретация: рациональные числа. Невыразимый предикат: . Автоморфизм: .
Заметим, что сложение позволяет выразить предикат . Кроме того, отметим, что вместо рациональных чисел можно взять действительные (но не целые, так как в этом случае единица описывается как наименьшее число, большее нуля).
- Сигнатура содержит равенство, порядок и константы
и . Интерпретация: действительные числа. Невыразимый предикат: . (Автоморфизм упорядоченного множества , сохраняющий и , но не , построить легко.) \end{specialparenv}
Сигнатура содержит равенство, сложение, константы
и . Интерпретация: действительные числа. Одноместный предикат выразим для рациональных и невыразим для иррациональных .
В самом деле, выразимость для рациональных очевидна. Невыразимость для иррациональных следует из того, что для любых двух иррациональных и
существует автоморфизм, переводящий в . (В самом деле, рассмотрим как бесконечномерное векторное пространство над . Векторы линейно независимы и потому их можно дополнить до базиса Гамеля (подробности смотри в книжке по теории множеств [6]). Сделаем то же самое с векторами . Получатся равномощные базисы, после чего мы берем -линейный оператор, переводящий в и в .)
В сигнатуру входят предикат равенства, операции сложения и умножения, а также константы и . Интерпретация: комплексные числа. Предикат , где — некоторое комплексное число, выразим для рациональных и невыразим для иррациональных .
В самом деле, если иррационально, то оно может быть алгебраическим или трансцендентным. В первом случае рассмотрим многочлен из минимальной степени, обращающийся в в точке ; по предположению он имеет степень больше и потому имеет другой корень . В алгебре доказывается (с использованием трансфинитной индукции или леммы Цорна, а также базисов трансцендентности), что существует автоморфизм
над , переводящий в .
В случае трансцендентного мы используем такой факт: для любых трансцендентных
существует автоморфизм поля над , который переводит в .
Отметим, что для поля вместо такое рассуждение не проходит, так как это поле не имеет нетривиальных автоморфизмов. (Отношение порядка выразимо: положительные числа суть квадраты, поэтому любой автоморфизм сохраняет порядок. Поскольку автоморфизм оставляет на месте все рациональные числа, он должен быть тождественным.)
В этом случае предикат выразим тогда и только тогда, когда — алгебраическое число. Это легко следует из теоремы Тарского-Зайденберга.
61. Покажите, что предикат невыразим в интерпретации , где — одноместная функция .
62. Покажите, что предикат невыразим в множестве целых положительных чисел с предикатами равенства и " делит ".
