АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 1991 г.

УДК 5 1 2 .5 3 2 В.Г.ДУРНЕВ Ярославский университет О ПОЗИТИВНОЙ ТЕОРИИ СВОБОДНОЙ ГРУППЫ В СИГНАТУРЕ, РАСШИРЕННОЙ ФУНКЦИЕЙ ДЛИНЫ В [ I ] обосновывается естественность при изучении теоретико­ модельных свойств свободных произведений групп включать в сигна­ туру функцию длины, а в £2] и £3 ] изучаются 3 -теории свобод­ ных полугрупп и групп в сигнатурах, тесно связанных с функцией длины. Обозначим через Fg = « а , 6 » овободную группу ранга 2 с фик­ сированными свободными образующими <1,6 . Через t x l будем обоз­ начать длину влемеНта х группы F z относительно системы об­ разующих а , 6 , Расширим групповую ойгнатуру группы Fg с вы­ деленными элементами д , 6 , Т ;е . содержащую, как обычно, » . ; , - 1 , 1 , а , 6 , введением функции длины I I . Элементарными формулами в полученной сигнатуре будем считать выражения вида ш^- v и | 26 Г|= )г/|, где ми, I/ — групповые слова от некоторых переменных и констант а , 6 . В £4] доказана неразрешимость элементарной теории группы Fg в расширенной таким образом сигнатуре; Целью настоящей заметки я вл яется получение усиления этого р езультата, а именно, дока­ зател ьство алгоритмической ^разрешимости позитивной 3 V 3 - Теории свободной группы Fg в указанной выше расширенной ои г- натуре. Покажем, что в этой сигнатуре любая формула эквивалентна некоторой позитивной формуле; Для этого воспользуемся следуици- ми эквивалентностями: х i у<=> \х~ 1 у\ъ 1 <=>( 3 в ) ( ^ 6 - б 2 S \ x у IМа 2 |); Ixl <|ук=>(Э2,иХ2Д- a i& u a * a u & l 2 \ * = \г£ и \)\ \ х \ * i ^ l < = > ( U I < l y O v ( i y i < U l ) , Выразим ряд проотых предикатов формулами в введенной в рас­ смотрение расширенной сигнатуре группы Fs < Обозначим через Р(х) предикат, " X - неотрицательная сте­ пень а т .е р ( х ) <-> ( 3<п )((■/£.$' т * 0 Я х - а " 1) - Нетрудно понять, что p f c ) < —y ( x a ^ а х . 8 ( \ x a \ - \ x 6 \) ■