Читать онлайн «Внутреннние гомоморфизмы и позитивно-условные термы»

Алгебра и логика, 40, N 2 (2001), 158-173 УДК 512. 57:512. 565. 7 ВНУТРЕННИЕ ГОМОМОРФИЗМЫ И ПОЗИТИВНО-УСЛОВНЫЕ ТЕРМЫ*) А. Г. ПИНУС Понятия условного терма и условно термальной функции были вве­ дены в [1]. Условный терм соответствует понятию программы вычислений на универсальной алгебре. В силу этого, универсальные алгебры, которые заданы на одном и том же основном множестве и совокупности условно термальных функций которых совпадают, суть алгебры с равными про­ граммно вычислительными возможностями. В работах автора [2—12] (об­ зор полученных результатов см. [13]) рассмотрен целый ряд естественных вопросов, связанных с понятием условного терма. В частности, в [3] по­ казано, что для конечных алгебр (для равномерно локально конечных ал­ гебр конечной сигнатуры — в [12]) полугруппы внутренних изоморфизмов играют роль инвариантов отношения условно рациональной эквивалент­ ности на этих алгебрах (т. е. совпадения их программно вычислительных потенциалов). В силу этого результата возникал естественный вопрос о по­ лугруппах внутренних гомоморфизмов алгебр и связанном с совпадением этих полугрупп отношении "близости" между алгебрами. Решению этой проблемы и посвящена данная работа. Напомним, что внутренним изоморфизмом алгебры А = (А;сг) на­ зывается любой изоморфизм между ее подалгебрами. Совокупность всех внутренних изоморфизмов алгебры Л (включая сюда и пустое отображе­ ние 0 ) образует полугруппу (относительно естественным образом опреде- ** Работа выполнена при финансовой поддержке Российского фонда фундаменталь­ ных исследований, проект N 96-01-01675. © Сибирский фонд алгебры и логики, 2001  Внутренние гомоморфизмы и позитивно-условные термы 159 ленной операции суперпозиции), обозначаемую как IsoA. Понятие услов­ ного терма сигнатуры а базируется на понятии условия 7(х) сигнатуры а — конечной конъюнкции равенств и неравенств между термами сигна­ туры а. Конечное множество {7\(х),... ,7k(x)} условий назовем полной к _ системой условий, если формула V 7i(x) общезначима, а для различных р и q формулы 7р(х)к7д(х) невыполнимы. Понятие условного терма сиг­ натуры а определяется стандартной индукцией (как и понятие терма) с дополнительным индукционным шагом: если £i(#),... ,£&(#) — условные термы сигнатуры <7, а множество {7\(х),... ,Tfc(af)} — полная система условий этой сигнатуры, то и ( 7{(х) ->ti(S), W - < (i) [ 7к(х) -* tk(x) будет условным термом этой сигнатуры. Каждому условному терму t(W) сигнатуры а на произвольной уни­ версальной алгебре Л = (А; а) соответствует условно термальная функция (также обозначаемая через t(x)), определяемая естественной индукцией по длине условного терма для тех индуктивных шагов, которые соответ­ ствуют стандартному определению терма; если же t(x) определен согласно правилу (1), для элементов о, Ь алгебры Л равенство t(a) = b соответствует тому, что Л |= 7i(a) и U(a) = b для некоторого г ^ к.