Читать онлайн «О проблеме конечной сигнатуры»

Сибирский математический журнал Январь—февраль, 2003. Том 44, № 1 УДК 510. 67 О ПРОБЛЕМЕ КОНЕЧНОЙ СИГНАТУРЫ А. С. Морозов Аннотация: Показано, что не всегда можно заменить произвольную модель дру- гой моделью конечной сигнатуры так, чтобы группа ее автоморфизмов при этом не изменилась. Ключевые слова: автоморфизм, конечная сигнатура Мы в основном следуем стандартной терминологии и обозначениям, при- нятым в теории конструктивных моделей (см. [1]) и теории вычислимости (см. [2]). Хорошо известно, что группа автоморфизмов любой счетной модели счет- ной сигнатуры реализуется с точностью до изоморфизма как группа всех ав- томорфизмов некоторого бинарного предиката. При этом если эта группа ре- ализуется как группа всех автоморфизмов некоторой вычислимой модели, то этот бинарный предикат тоже может быть выбран вычислимым. Аналогичный результат верен и для групп всех вычислимых автоморфизмов вычислимых моделей. Идеи преобразования моделей бесконечных сигнатур в модели конеч- ных сигнатур с сохранением типа изоморфизма группы всех автоморфизмов достаточно просты, хорошо известны и многократно описаны в разных вариа- циях. Автор затрудняется установить первоисточник этого вопроса. Сама идея преобразования моделей заключается в том, что для каждой n-ки элементов a1 , . . . , an , удовлетворяющих предикату Pi , мы добавляем в модель серию новых элементов, связанных с этими элементами и между собой бинарным отношени- ем R так, что по фигуре, образуемой этими новыми добавленными элементами с помощью R, можно однозначно восстановить номер i предиката Pi и факт принадлежности этой n-ки данному предикату. Например, если предикат Pi тернарный, то для каждой тройки a1 , a2 , a3 такой, что Pi (a1 , a2 , a3 ), в модель можно добавлять новые элементы b1 , . . . , bi+1 , c1 , c2 , c3 , на которых R определе- но как {hb1 , a1 i, hb2 , b1 i, hb3 , b2 i, . . . , hbi+1 , bi i, hb1 , c1 i, hc1 , a2 i, hb1 , c2 i, hc2 , c3 i, hc3 , a3 i}. При соблюдении некоторой аккуратности в построении так полученное множе- ство элементов с бинарным предикатом R, рассматриваемое как модель, будет иметь группу автоморфизмов и группу вычислимых автоморфизмов, изоморф- ные соответственно группе всех автоморфизмов и группе всех вычислимых ав- томорфизмов исходной модели. Сокращение числа сигнатурных символов при этом было достигнуто за счет добавления в модель новых элементов. Разуме- ется, при этом действие соответствующих групп на полученной таким образом Работа выполнена при частичной финансовой поддержке INTAS (грант № 00–499) и Российского фонда фундаментальных исследований (код проекта 02–01–00593). c 2003 Морозов А. С. О проблеме конечной сигнатуры 207 новой модели уже может оказаться неизоморфным действию этих групп на ис- ходной модели.