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

УДК 519.5 В. Г. ДУРНЕВ Ярославский университет НЕРАЗРЕШИМОСТЬ ПОЗИТИВНОЙ 3 -ТЕОРИИ СВОБОДНОЙ АБЕЛЕВОЙ ПОЛУГРУППЫ В СИГНАТУРЕ < • t < ц , а-2 , С > Обозначим через А \ свободную абелеву полугруппу с образую­ щ и е @ 1 ,. .Д п • Введем в рассмотрение предикат С ( « , $ ) > который, ю определению,будем считать истинным для элементов д . , Ц полугрушш тогда к только тогда, когда Ц есть степень J- в (ш придерживаемся мультипликативной систеш обозначе­ н а I, при аддитивной системе обозначений следовало бы говорить, что элемент к V - кратен £ ). Хорошо известно, что элементарная теория полугруппы j \ n в сигнатуре <•, ClL, разрешима. Кроме того, известно, что пози­ тивная. 3 - теория полугруппы А 1 в сигнатуре< . , <X L, С > тоже разрешив [ ±] t [ 2 ] . Цблью настоящей работы является доказательство алгоритмичес­ кой неразрешимости позитивной 3 - теории полугрушш у^ 5 в сигнатуре < • , Q t } й г • Как следствие этого факта будет полу- ченб доказательство алгоритмической неразрешимости одной проблемы для линейных диофактовых систем. Рассмотрим, следуя А.И. Гальцеву предикаты М 4 ( х ) * ( 3 1 } ) ( у =а ; а С ( # , * ) ) , Т ( Ъ , Хх ) * ( A l Ц ( Х Д ) A ( 3 x l t i J f a = a A А /> C(tl t l %j), TT tj , A j f - S C ^ й 2 = т ,а г А С ( у , 1 ))У Лекажем, что для : A , b 7(j,i) « зуществует такое натуральное число m , что П = Q.J* , к =- Q * . В самом деле, если ^ i ( t , к ) , то сущмтвуют такие натуральные числа m и I , что £ = Q * , / =г &}* . Остается показать, что м = ^ . Так как А х 1= 2/. =■ йх А A Z x = $ к А С ( л , то для некоторого натурального числа i имеем ОА&1 = (С1 1 & iY . Отсюда сразу получаем, что п - ^ / Остается заметить, что для любого натурального числа ш 50