Cтраница 1
Финитная аппроксимируемость является одним из важных условий конечности ( см. Полугруппа iic. [1]
Модификацией понятия финитной аппроксимируемости является финитная аппроксимируемость относительно предикатов. Пусть я-предикат, выделяющий свойства элементов и ( или) подмножеств полугруппы. Полугруппа S называется финитно аппроксимируемой относительно предиката я, если для любой комбинации значений элементов [ ai) и ( или) подмножеств М /, при которой значение я ложно, существует такой гомоморфизм р полугруппы S в конечную полугруппу, что значение л для c - f и ( или) Af / ф также ложно. Обычная финитная аппроксимируемость соответствует в этом определении предикату равенства. Полугруппу, ф.а. относительно вхождения элемента в подполугруппу, называют финитно отделимой. [2]
Связь между финитной аппроксимируемостью и разрешимостью проблемы равенства получается из следующих соображений. Пусть ФА-группа G задана конечным кодом. Тогда множество a ( TV) является рекурсивно перечислимым множеством. [3]
Связь между финитной аппроксимируемостью и разрешимостью проблемы равенства получается из следующих соображений. Пусть ФА-группа G задана конечным кодом. Тогда множество a ( N) является рекурсивно перечислимым множеством. [4]
Довольно общие достаточные признаки финитной аппроксимируемости разрешимых групп конечного приведенного ранга будут указаны далее. [5]
Модификацией понятия финитной аппроксимируемости является финитная аппроксимируемость относительно предикатов. Пусть я-предикат, выделяющий свойства элементов и ( или) подмножеств полугруппы. Полугруппа S называется финитно аппроксимируемой относительно предиката я, если для любой комбинации значений элементов [ ai) и ( или) подмножеств М /, при которой значение я ложно, существует такой гомоморфизм р полугруппы S в конечную полугруппу, что значение л для c - f и ( или) Af / ф также ложно. Обычная финитная аппроксимируемость соответствует в этом определении предикату равенства. Полугруппу, ф.а. относительно вхождения элемента в подполугруппу, называют финитно отделимой. [6]
Рассмотрим, наконец, связи между финитной аппроксимируемостью, финитной отделимостью и некоторыми алгоритмическими вопросами. [7]
Из теоремы 1 следует, например, финитная аппроксимируемость групп, имеющих конечный нормальный ряд, факторы которого являются конечными, бесконечными циклическими или свободными группами с конечным числом порождающих. [8]
Выше были перечислены известные в литературе достаточные признаки финитной аппроксимируемости отдельных классов групп. Здесь мы добавим несколько замечаний по поводу задачи нахождения классов финитно аппроксимируемых групп и полугрупп. [9]
Другие конструкции, вообще говоря, не сохраняют финитную аппроксимируемость. S индуцируют различные левые н различные правые внутренние сдвиги, в частности, если S с сокращением пли инверсная. [10]
Не известно, влечет ли условие ( 2) финитную аппроксимируемость группы G, однако все известные примеры групп промежуточного роста относятся именно к этому классу групп. Более того, группы, построенные в [11], [12], аппроксимируются конечными р-группами, где р - простое число. В связи с этим уместно поставить следующие вопросы. [11]
С другой стороны, в работе автора [8] была доказана финитная аппроксимируемость матричных групп с конечным числом порождающих, а тем самым и произвольных свободных групп и свободных произведений финитно аппроксимируемых групп. Финитная аппроксимируемость свободных групп была позже независимо доказана К. Финитная аппроксимируемость разрешимых групп с условием максимальности для под-трупп установлена К. [12]
Примеры условий конечности: периодичность ( см. Периодическая полугруппа), локальная конечность ( см. Локально конечная полугруппа), финитная аппроксимируемость ( см. Финитно аппроксимируемая полугруппа), конечная порожденность, конечная определенность. Исследования конечно определенных полугрупп в значительной степени ведутся с точки зрения алгоритмич. [13]
С другой стороны, в работе автора [8] была доказана финитная аппроксимируемость матричных групп с конечным числом порождающих, а тем самым и произвольных свободных групп и свободных произведений финитно аппроксимируемых групп. Финитная аппроксимируемость свободных групп была позже независимо доказана К. Финитная аппроксимируемость разрешимых групп с условием максимальности для под-трупп установлена К. [14]
ПРС, наиболее известна финитная аппроксимируемость. В частности, всякая коммутативная конечно порожденная ( автоматически к. Следующие условия для конечно порожденной полугруппы S эквивалентны: ( 1) S имеет разрешимую ПРС; ( 2) 5 вложима в любую неодноэлементную алгебраически замкнутую полугруппу ( Macintyre A. S вложима в конгруэнц-простой ( конечно порожденный) рекурсивно определенный группоид ( EvansT. [15]