Универсальные хорновы классы и антимногообразия алгебраических систем

Алгебра и логика, 39, N 1 (2000), 3-22

УДК 512.57

УНИВЕРСАЛЬНЫЕ ХОРНОВЫ КЛАССЫ И АНТИМНОГООБРАЗИЯ

АЛГЕБРАИЧЕСКИХ

СИСТЕМ*)

В. А. ГОРБУНОВ, А. В, К Р А В Ч Е Н К О

В работе определяются и изучаются универсальные хорновы классы, двойственные многообразиям кгьк В синтаксическом, так и в семантическом смысле. Такие классы, названные нами антимногообразиями, естествен­ но возникают, например, в теории графов и теории формальных языков (см. [1]). Основными результатами работы являются теорема 1.2 о характеризации антимногообразий, теоремы 2.4, 2.8 о ядрах в аксиоматизируемых цветосемействах и теорема 4.3 о разрешимости универсальных теорий се­ мейств интерпретаций формальных языков.

§ 1. Собственные универсальные хорновы к л а с с ы и антимногообразия Предложение сигнатуры L называется универсальным хорновым, ес­ ли оно является конъюнкцией предложений следующего вида:

(W) («! (х) & . . . & « „ СЮ);

(1)

(yx)fai(S)V...V-am(aO);

(2)

(Vaf) ( a i (ж) & . . .&а*(х) -+ a f c + 1 (x)),

(3)

*) Работа выполнена при финансовой поддержке Российского фонда фундаменталь­ ных исследований, проекты 99-01-000485 и 96-01-00097, а также Немецкого научноисследовательского общества, проект 436 113/2670

©

Сибирский фонд алгебры и логики, 2000

4

В. А. Горбунов, А. В. Кравченко

где а, (х) — атомные формулы сигнатуры L, Класс i-систем называется универсальным хорновым, если он является классом моделей для некото­ рого множества универсальных хорновых предложений. В свою очередь, предложения вида (1), (2), (3) называются соответственно тождествами, антитождествами

и квазитождествами, а классы систем, определяе­

мые посредством этих предложений, — многообразиями,

антимногообра­

зиями и квазимногообразиями. Поскольку любое тождество эквивалентно конъюнкции квазито­ ждеств, многообразия являются квазимногообразиями. Кроме того, лю­ бое антитождество ложно на тривиальной системе, в то время как все квазитождества истинны на такой системе. Поэтому для произвольного универсального хорнова класса К возможны два случая: (1) К содержит тривиальную систему £ L ; (2) К не содержит £/, (такие классы будем называть собственными). В первом случае К представляет собой квазимногообразие, а во вто­ ром случае, добавляя к К тривиальные системы, мы также получим ква­ зимногообразие, которое обозначим К + . Это немедленно вытекает из характеризационной теоремы Мальцева [2, § 11]. Таким образом, изучение универсальных хорновых классов сводится к изучению квазимногообразий. Как мы увидим дальше, в некоторых слу­ чаях удобней и естественней рассматривать произвольные (в частности, собственные) универсальные хорновы классы. Такие классы естествен­ но возникают в различных областях математики: это, например, графы без петель, алгебраические пространства замыкания, канторовы алгебры, нетривиальные кольца с единицей, полугруппы без идемпотентов (см. [1]). Сначала дадим алгебраическую характеризацию собственных уни­ версальных хорновых классов (см. также [3]). Конгруэнции здесь пони­ маются в смысле [4]. Для любого класса К через К~ обозначается класс нетривиальных систем в К. Т Е О Р Е М А 1.1. Для любого универсального хорнова класса L-cuстем К, где L — сигнатура с конечным числом предикатных равносильны следующие условия:

символов,

Антимногообразия алгебраических систем

5

(1) К~ — универсальный хорное класс; (2) тривиальная система ti, не вложима ни в какую систему из

к-; (3) для любой системы Л G К наибольшая конгруэнция

1,д в

Con^-f Л компактна, ДОКАЗАТЕЛЬСТВО. Очевидно, что (1)=>(2). Обратно, пусть класс К удовлетворяет условию (2). Тогда в К~ выполняется бесконечное пред­ ложение {Ух) I V "(G{x,...,z)&x)V \GeLF

V "Я(*,...,а)|, тьР /

где Lp —- множество функциональных символов в L, a Lp — множество предикатных символов в L. Из теоремы компактности следует, что в К " выполняется некоторая конечная часть (р этого предложения. Поэтому К~ = К П Mod(), т. е. (2)^(1). (2)==>(3). Предположим, что существует система Л 6 К, для кото­ рой 1д является некомпактной конгруэнцией в Сопк+ Л. Тогда 1д = (J 0, iei для некоторой цепи (0|)t€i конгруэнции 0, ^ 1,д из Соп к + Л. Следователь­ но, £ L = Л/1.д == Н т Л / 0 | . С другой стороны, limA/Oi принадлежит К~~, получили противоречие. (3)=>(2). Пусть в К"" существует система Л, содержащая тривиаль­ ную подсистему с носителем {е}. Тогда \А\ ^ 2. В прямой степени Аш рас­ смотрим подсистему 33, элементами которой являются функции, принима­ ющие значение е для всех п Е о?, кроме конечного числа. Пусть р; обозна­ чает проектирование системы Ъ на г-ю компоненту, и для всех п £и пусть вп = р | кегр,. Ясно, что {0П : n G CJ} является цепью, Ф/0П — В и вп ф 1$ для всех п. Из определений следует также и равенство ( у Йп)° = 1^, С другой стороны, поскольку Ъ содержит тривиальную подсистему с носите­ лем {е*}, где е*{п) = е для всех n ^ w , имеем Ъ \= Д[е*,... , е*] для любого предикатного символа R. Поэтому фактор-система Ъ/ V вп тривиальна и 1$ = V 0П. Таким образом, 1$ не является компактным элементом в Сопк+В, получили противоречие. П

6

В. А. Горбунову А. В. Кравченко Хорошо известно, что эквациональная логика в языке без функцио­

нальных символов является очень бедной, так как в этом случае отсутству­ ют термы, отличные от переменных. Поэтому эквациональная логика по­ лучила сильное развитие только в случае алгебр. Одна из целей настоящей статьи — показать, что в случае предикатных систем роль многообразий играют, в определенном смысле, антимногообразия. Для класса К через Н _ 1 ( К ) обозначается класс всех гомоморфных прообразов систем из К, a V~ X (K) представляет собой наименьшее ан­ тимногообразие, содержащее К . Следующая теорема является аналогом HSP-теоремы Виркгофа для антимногообразий. Т Е О Р Е М А 1.2. Для произвольного класса К равносильны следую­ щие условия: (1) К — антимногообразие, т. е. К определяется некоторым (воз­ можно, пустым) множеством антигпождеств; (2) К — универсальный хорное класс и Н ^ ^ К ) С К; (3) K ^ H ^ S P ^ K ) . В частности, V " " 1 ^ ) = H - 1 S P * ( K ) для любого класса К . ДОКАЗАТЕЛЬСТВО. Если К совпадает с классом всех систем дан­ ной сигнатуры, то К задается пустым множеством антитождеств. Поэто­ му, не ограничивая общности, предположим противное. Поскольку опера­ тор Н~ х сохраняет антитождества, то (1)=>(2) и, очевидно, (2)=>(3). (3)=^(1). Пусть класс К удовлетворяет условию (3), тогда он замкнут относительно подсистем. Кроме того, К замкнут относительно нетриви­ альных ультрапроизведений. Действительно, если (2i)t€J G К, то для каждого г € / существует гомоморфизм fi из Ъ{ на некоторую систему Л, из S P * ( K ) . Тогда для любого ультрафильтра D над / семейство го­ моморфизмов (fi)i£i индуцирует гомоморфизм из JJ Ъ{/П на

JjAi/D.

Таким образом, К — универсально аксиоматизируемый класс. Пусть К 7 — множество всех конечно-порожденных систем, не принадлежащих К . Со­ гласно предположению, К ' ^ 0 . С каждой системой Л Е К ' свяжем ее

Антимногообразия алгебраических систем

7

представление З^ж, Дд) в порождающих а и докажем, что предложение *A = (VSF) ( V

>(*)]

\^6ДА

/

выполняется в К . Предположим противное, т. е. пусть существует систе­ ма S Е К такая, что все формулы из АА истинны в Ъ при некоторой интерпретации х и 1. Тогда отображение a ь-> b можно продолжить до гомоморфизма из Л в Ъ. Поскольку Н~ 1 (К) С К, то Л £ К, получили противоречие. Далее, так как К аксиоматизируем, по теореме компактности пред­ ложение <рд эквивалентно относительно К некоторой своей конечной ча­ сти ФА. ПО определению ФА является антитождеством. Докажем, что К = = Mod(E), где Е = {ФА : Л £ К ' } . Согласно предыдущему, К С Mod(E). Если это включение является строгим, то найдется конечно-порожденная система Л £ Mod(E) \ К . Тогда Л £ К ' и, следовательно, Л (= ""^л? откуда «А И ~4Vb ч т о противоречит предположению. О Подкласс К 7 класса К называется К-аптпимногообразием, если К ' = = К П Mod(E) для некоторого множества антитождеств Е или, другими словами, если К ' = К П V~ 1 (K / ); К-антимногообразия естественно возни­ кают в теории графов (обобщения понятия раскраски) и теории формаль­ ных языков (понятие интерпретации), см. [1]. Приведем еще один пример, имеющий алгебраическую природу. ПРИМЕР 1.3. Конечная система Л из класса К называется делите­ лем нуля в К, если существуют конечные неизоморфные системы Ъ и С в К такие, что Л X Ъ = Л X С. Для данного простого числа р через Ср обозначается орграф с вершинами 1 , . . . , р, в котором пара (га, т) являет­ ся ребром, если и только если га + 1 = та (mod p). Для любых орграфов Ъ и Q через 3 U С обозначается их раздельное объединение. Согласно тео­ реме Ловаса из [5], конечный орграф Л является делителем нуля в клас­ се D конечных орграфов в том и только в том случае, если существует гомоморфизм из Л в орграф вида CPl U . . . U QPn, где все pi — простые числа. Таким образом, класс делителей нуля в D является D-антимногообразием, порожденным конечными раздельными объединениями графов

В. А. Горбунов, А. В. Кравченко

8

вида Ср, где р — простое число. Отсюда следует, что в классе конечных графов делителями нуля являются в точности 2-раскрашиваемые графы. В [б] дана аналогичная характеризация делителей нуля для произвольных предикатных систем конечной сигнатуры.

§ 2. Цветосемейства и я д р а Для данной системы Л из универсального хорнова класса К через [К -* Л] обозначается класс систем S G K таких, что существует гомомор­ физм из Ъ в Л. Такие классы называются главными цветпосемействами в К, а их конечные объединения, т. е. классы вида [К -* А] = [К -> -» А\] U . . . U [К ~» Л„], где А = { Л ь . . . , Л п } , — цветпосемействами в К . Говорим, что цветосемейство [К —• А] конечно порождено, если все системы из А конечны. Пусть L — класс всех систем сигнатуры L. Тогда для любой L-системы Л имеем [L -> Л] = Н~ 1 8(Л). Отсюда, цветосемейства замкнуты относительно подсистем и нетривиальных прямых произведений. Для ка­ ких систем Л цветосемейство [L -> Л] является антимногообразием? Легко видеть, что для конечных систем это так. Более того, для любой конеч­ ной системы Л существует минимальная подсистема Ъ < А относительно включения такая, что [L -> Ъ] = [L -> Л]. Эта подсистема называет­ ся ядром Л. Если ядро Л совпадает с Л, то сама система Л называется ядром. Приведем некоторые свойства ядер конечных систем. П Р Е Д Л О Ж Е Н И Е 2.1. Пусть А иЪ - конечные системы. Тогда (1) если Ъ — ядро А, то система Ъ является ядром; (2) ядро системы А существует и единственно с точностью до изоморфизма; (3) система Ъ является ядром системы А в том и только в том случае, если Ъ — минимальный по включению ретракт Л; (4) система А является ядром в том и только в том случае, если любой эндоморфизм А является

автоморфизмом;

(5) гомоморфизм из системы А в систему Ъ существует в том и

Антимногообразия алгебраических систем

9

только в том случае, если существует гомоморфизм из ядра системы А в ядро системы Ъ. Все утверждения легко проверяются (см. [7], где приведены дока­ зательства некоторых из них в случае графов). Для бесконечных систем данные утверждения перестают быть верными. Например, бесконечные системы могут не иметь ядер или иметь несколько неизоморфных ядер (см. [7, 8]). Напомним, что система А называется слабо атомно компактной, ес­ ли любое локально совместное в А множество атомных формул (от произ­ вольного числа переменных) является совместным в Л. Следующее утвер­ ждение, отвечающее на вопрос об аксиоматизируемости цветосемейств, служит основой нашего подхода к ядрам бесконечных систем. П Р Е Д Л О Ж Е Н И Е 2.2. Главное цветосемейство [L -> А] являет­ ся антимногообразием или {равносильно) аксиоматизируемым классом в том и только в том случае, если А — слабо атомно компактная систе­ ма, В частности, [L —>• А] = ЛГ~1(А) для любой слабо атомно компакт­ ной системы А. ДОКАЗАТЕЛЬСТВО. Предположим, что [L ~» А] — аксиоматизи­ руемый класс. Пусть Е — локально совместное в А множество атомных формул. Тогда по теореме компактности Е совместно в некоторой уль­ трастепени A1 /D. Поскольку A1 /D € [L ~» Л], существует гомоморфизм A1 /D —> Л; поэтому Е совместно и в Л. Обратно, пусть Л — слабо атомно компактная система. В силу теоремы 1.2 достаточно показать, что [L —У А] замкнут относительно ультрапроизведений. Пусть (Л,) г е/ — семейство систем из [L —> А] и D — произвольный ультрафильтр над I. Легко построить гомоморфизм П Л,-/2? -*• A1 /D, поэтому достаточно показать, что существует гомомор­ фе/ физм A1 /D -> Л. Пусть Е — позитивная диаграмма системы A1 /D. Так как Е совместно в A1 /D и Л — элементарная подсистема системы A1/D, то Е локально совместно в Л. По предположению получаем, что Е совместно в Л, т. е. требуемый гомоморфизм действительно существует. П Следуя [9], будем говорить, что предикатная система Л гомоморфно

10

В. А. Горбунов, А. В. Кравченко

компактна, если S G [L ~> Л] тогда и только тогда, когда любая конечная подсистема системы Ъ принадлежит L -» Л. В [9] доказано, что у гомо­ морфно компактного орграфа ядро всегда существует, и в этом случае ряд свойств ядер конечных систем сохраняется. Из доказательства предложе­ ния 2.2 следует, что предикатная система конечной сигнатуры гомоморфно компактна в том и только в том случае, если она слабо атомно компактна. Очевидно, равенство [L —> Л] = L возможно тогда и только тогда, когда тривиальная система £/, вложима в Л. Поэтому при изучении цветосемейств будем рассматривать системы, не содержащие тривиальных подсистем. Система Л называется ядром, если она слабо атомно компакт­ на и проста в У - ^ Л ) . Как будет видно ниже, это определение совпадает с определением ядра конечной алгебраической системы. П Р Е Д Л О Ж Е Н И Е 2.3. Для любой слабо атомно компактной системы Л без тривиальных подсистем существует ядро Ъ такое, что

V~l(A)=:V-l{fy. ДОКАЗАТЕЛЬСТВО. Покажем сначала, что множество

Р = {0 € Con Л : V-\A)

=

Ух(А/в)}

содержит максимальный элемент. Пусть {0; : г £ / } — произвольная цепь в Р. Согласно [4], возможны два случая: Л / (J0, € V~X{A) либо |J 0, = 1д. На самом деле возможен только первый случай. Действительно, любая локальная подмодель в Л / (J 0; изоморфна локальной подмодели в Л/0, для некоторого г (см. [4]). Поэтому, если £^ = A/\J0i,

то позитивная диа­

грамма J 3 + ( £ L ) локально совместна в l{A/9i : г € 7). По предположению для каждого г 6 I существует гомоморфизм Л/0; —» Л, поэтому £ ) + ( £ L ) локально совместна в Л. Наконец, поскольку Л слабо атомно компактна, D+(£x,) выполняется в Л, постольку £ь < Л, что невозможно. Докажем теперь, что для любого максимального элемента 0о в Р си­ стема Л/0о является ядром. По определению, V " " 1 ^ ) = У"1 (А/во). Пусть / — произвольный гомоморфизм из Л/0о в В б V " 1 ^ ) . Если / не явля­ ется вложением, то 0о С 0', где 0' — ядро композиции гомоморфизмов Л -> Л/0о -> В, и \ г ~ 1 (Л/0') = V " 1 ^ ) , получили противоречие. •

Антимногообр&зия алгебраических систем

11

Т Е О Р Е М А 2.4. ДЛЯ слабо атпомно компактной системы Л без тривиальных подсистем равносильны следующие условия: (1) Л — ядро; (2) Епс1(Л) = AutOA); (3) для любого гомоморфизма f : Л —> Ъ, где В Е У~~г(Л), суще­ ствует гомоморфизм g :Ъ -+ Л такой, что gf = г А • ДОКАЗАТЕЛЬСТВО. (1)=»(2). Пусть Р - совокупность ядер В та­ ких, что V""1 (Л) = V - ^ S ) . Соглгьсно предложению 2.3, Р ф 0 . Более того, Р является множеством. Действительно, любая система В из Р является простой в V " " 1 ^ ) , причем существует гомоморфизм из В в Л, поэтому В < Л. Нетрудно также показать, что Р замкнуто относительно объеди­ нений по цепям. Докажем, что существует ядро С € Р , не имеющее собственных под­ систем, изоморфных С. Предположим противное, т. е. пусть любая систе­ ма из Р имеет собственное изоморфное расширение. Построим цепь си­ стем в Р произвольной длины, полагая, что Ло — произвольная система из Р , Л/3+i — собственное расширение Лр и Лр — собственное расширение U Л а , если /3 является предельным ординалом. Это противоречит тому, что Р — множество. Из определения С получаем End (С) = Aut(S). Осталось проверить, что В Э* С для всех В G Р . Согласно предположению, существуют вложе­ ния / : В —> Q и g : Q —* В. Поскольку fg — автоморфизм 6, / является отображением на С. (2)=>(3). Пусть / : Л -~» В — произвольный гомоморфизм. Если В Е G V " " 1 ^ ) , то существует гомоморфизм h : В -> Л, поэтому Л/ является автоморфизмом Л и гомоморфизм
будет требуемым.

(3)=>(1). Очевидно. О С Л Е Д С Т В И Е 2.5. Любое ядро Л однозначно определяется мно­ жеством аптитождеств, истинных в Л, т. е. для любых ядер Л и В из У~1(Л) = V~ 1 (B) следует Л == В. В частности, существует не более 2liLil ж)ер сигнатуры L, где \\L\\ = max(u;, |L|). Подсистема В системы Л называется ядром Л, символически В =

В. А. Горбунов, А. В. Кравченко

12

= Соге(Л), если существует гомоморфизм из Л в S, но отсутствуют гомо­ морфизмы из Л в собственные подсистемы системы Ъ. С Л Е Д С Т В И Е 2.6. Любая слабо атомно компактная система А без тривиальных подсистем имеет ядро. Это ядро Core (Л) единственно с точностью до изоморфизма и \r~i(A)

= У~ 1 (Соге(Л)).

ДОКАЗАТЕЛЬСТВО. Из предложения следует, что найдется яд­ ро Ъ, удовлетворяющее V " " 1 ^ ) = У~г(Ъ).

Тогда Ъ < А и для любого

гомоморфизма / : Л ~> С, где С < В, / | $ — автоморфизм 2 , поэтому С = Ъ. Таким образом, Ъ — ядро Л. Пусть Ъ' — другое ядро системы Л. Тогда V~ 1 (S) = V - 1 (!B'), следовательно, Ъ < Ъ1. Поскольку существует гомоморфизм из Л в В, получаем Ъ == Ъ*. • С Л Е Д С Т В И Е 2.7. Пусть А — слабо атомно компактная систе­ ма без тривиальных подсистем. Подсистема Ъ < А является ядром А в том и только в том случае, если Ъ — минимальный ретракт А отно­ сительно

включения.

В силу следствия 2.5 мощности ядер данной сигнатуры ограничены сверху. В следующей теореме указана их точная верхняя граница. Т Е О Р Е М А 2.8. Для любого ядра А сигнатуры L имеем \А\ ^ 2HLH. ДОКАЗАТЕЛЬСТВО. Предположим, что \А\ > 2^1

Пусть Ф -

множество позитивно примитивных формул ¥>(ж,у) таких, что Л \= (= (\/х)~^(р(х,х). Для каждой <р £ Ф полагаем А„ = {{а, Ъ} € А'2) : а < Ь и Л |= ф} &]}, где А^2) — множество двухэлементных подмножеств в А и < — некоторый строгий линейный порядок на А. Покажем, что А^

= (J{^9 • ^ G Ф}- Пусть а и Ь — произвольные

элементы в А и а < Ь. Поскольку £ L $( У"1 (А) и Л — простая система в У - ^ Л ) , то множество D+(A) U {са % q>} не имеет модели в V - 1 ( A ) . По теореме компактности найдется конечное подмножество К С D+(A) такое, что Ки{са

« Q,} также не имеет модели в У _ 1 ( Л ) . Тогда формула

(р = (Зг) /С л (х, у, ~z) (где /*ГЛ является конъюнкцией формул из К} в кото-

Антимногообразия алгебраических систем

13

рых са и сь заменены на х и у соответственно, а оставшиеся константные символы — на 1) принадлежит Ф, и A f= (p[a, b]. По теореме Эрдеша — Радо [10] найдутся формула <р € Ф и беско­ нечное подмножество В С А такие, что В^

С А^. Пусть X — множество

переменных, мощность которого больше |А|, и пусть Е = {<р(х, у) : х,у Е X их < у}. Тогда £ локально совместно в Л, а поскольку А — слабо атомно компактная система, Е выполнимо в Л. В силу того, что \Х\ > |А|, имеем Л j= (Эж)<^(х,а:), получили противоречие. • ЗАМЕЧАНИЕ 2.9. В случае предикатных систем понятие ядра совпа­ дает с понятием минимальной компактной системы, которое рассматривал Тейлор [11]. Бослаф [8, 9] дал определение ядра гомоморфно компактного орграфа и доказал предложение 2.3 и следствие 2.5 для случая орграфов. Отметим также, что теорема 2.8 отвечает на вопрос 3 из [9].

§ 3. Конечно-порожденные цветосемейства Пусть L — предикатная сигнатура, Л — конечная L-система и К = = [L ~> Л]. Поскольку цветосемейство К однозначно определяется ядром системы Л, можно считать, что Л является ядром. Набор ( a i , . . . , ап) эле­ ментов из А называется R-ребром, где R 6 L, если Л |= i?[ai,... , a n ]. Через ER(A) обозначается множество Л-ребер системы Л, а через Е(А) = — U ER(A) — множество всех ребер системы Л. Напомним, что универсальный хорнов класс К называется конечно-порожденным, если К = = 8Р*(Лх,... , Л ш ) для некоторых конечных систем Л,-, г ^ т . Т Е О Р Е М А 3.1* Пусть А — конечная предикатная система сигна­ туры L. Цветосемейство К = [L -» Л] является

конечно-порожденным

универсальным хорновым классом в том и только в том случае, если множество ребер системы А конечно. ДОКАЗАТЕЛЬСТВО. Пусть Л имеет лишь конечное число ребер, и арности предикатов, к которым относятся эти ребра, ограничены некото­ рым натуральным числом п. Покажем, что любая система в К аппрокси­ мируется системами из К, мощности которых не превосходят |А| -f п.

В. А. Горбунов, А. В. Кравченко

14

Пусть Ъ £ К и / — гомоморфизм из Ъ в Л. Предположим также, что £ ф У € В и /(ж) = /(у) = а. Построим систему С следующим образом: основным множеством является С = Аи{а'}, где а' £ А, а предикаты опре­ деляются по правилу С (= Р[Ь] тогда и только тогда, когда С {= Р[&*], где 6* обозначает кортеж, полученный из Ь заменой каждого а1 на а. Определим отображение д из В в С следующим образом: ^(х) = а' и #(Ь) = /(b) для всех Ь ^ ж. Из построения системы С следует, что д — гомоморфизм, при­ чем, д(х) ф д(у). Рассмотрим теперь произвольный кортеж (&i,... , Ьт) на В, не являющийся Р-ребром системы В, где Р £ L. Пусть /(6,-) = а,, г ^ т , и ( a i , . . . , а т ) —- Р-ребро системы Л. Рассмотрим множество { c i , . . . , ст} элементов, не принадлежащих А, где с, = Cj в том и только в том случае, если bi == bj. Построим систему С следующим образом: основным множе­ ством является С = A U {с, : г ^ га}, кортеж с = ( c i , . . . , c m ) не является Р-ребром системы С, а для любой пары (6, Р) ^ (с, Р), где Ь — кортеж на С и Р £ L, имеем С |= Р[6] тогда и только тогда, когда Л (= Р[Ь*], где Ь* получается из b заменой каждого с, на а,, « ^ т. Очевидно, что С £ К и |С| ^ |А| + п. Определим отображение р : В -> С, полагая #(Ь) = /(b) для всех Ь ^ {Ьх,... , Ь т } и то по определению системы С имеем S \= P[i;i,... , v*] Ф> Л [= P [ / ( u i ) , . . . ,/(зд)]. Поскольку / — гомоморфизм, д также является гомоморфизмом. Остается заметить, что Q\=-R\s(bi),...,g{bm)]. По данному Р-ребру aR — ( a i , . . . , a„), где Р £ L, системы Л постро­ им систему Л (OR) следующим образом: (а) A{UR) — A U {а' х ,... , а^}, где а[ £ А, г ^ п, причем а< = а^ тогда и только тогда, когда щ = aJ?

(б)Л(а я )Н"Ж^--Х], (в) если Р £ £ \ { Р } или b ф (а[,...

, а'п), то Ъ £ Р л ( а я) тогда и только

тогда, когда Ь* £ Р л , где кортеж Ь* получается из кортежа Ъ заменой каждого а\ на а,. Из определения легко следует, что Л — ядро системы А(ац). Петлей называется Р-ребро а системы Л, если а = ( а , . . . , а). Пока-

Антимногообразия алгебраических систем

15

жем, что если Л -— конечное ядро и a — Д-ребро Л, которое не является петлей, то система A((LR) подпр>ямо неразложима в К. Пусть д —- гомоморфизм из А(ал) на, некоторую систему Ъ £ К . Через / обозначим гомоморфизм из Ъ в Л. Пусть |А(ад)| - |Л| = s. То­ гда найдутся различные пары элементов х\ ф j / i , . . . , х8 ф у8 такие, что fgfai) = / # Ы - Очевидно, s ^ 2. С л у ч а й 1. Пусть для некоторого г ^ s найдется j ^ n такое, что {*•,&•} = {а^,а£}. Тогда (a[,... , < ) £

(keifg)(R).

С л у ч а й 2. Пусть для любого i ^ s множество {ж,-,у,} отлично от всех {о,, ay}, j ^ п. Если Xi,yi G А, то через h обозначим тождественное вложение Л в А(ая); если |{ж»,г/«} П {<4,... , « ^ } | = 1 и х%; = а'^ то че­ рез h обозначим вложение Л в А{ац), переводящее a,j В a'j и оставляющее остальные элементы на месте. В первом варианте, (х,-,*/,) £ (кег/^/г)(?^), а во втором — (yi,a,j) £ (ker fgh)(tt),

т. е. в обоих вариантах при эндо­

морфизме fgh отождествляются некоторые два элемента из А. Поэтому fgh £ Аи1;(Л). Так как Л — ядро, получили противоречие с предложени­ ем 2.1. Пусть Xi = a'j и у{ = а\, где aj ф щ. Если s ^ 3, то отображение h из А в А(оя), переводящее aj в а^-, а/ в а\ и оставляющее остальные элементы на месте, является вложением. Как и выше, fgh £ Aut(^l), по­ лучили противоречие. Наконец, пусть s = 2. Тогда х\ = о^, j/i = а^ (или наоборот). Так как {хХ) уг} ф {х2, У2}, имеем | { х ь у{\ П {ж2, у2}\ ^ 1» Если {xi,t/i} П {#2,2/2} ^ 0 > т о Х2)У2 € А, что невозможно в силу доказанного выше. Если же |{xi,yi} Г) {а^Уг}! = 1? то> к а к

и в

рассмотренном выше

случае \{х^ yi} П {а' 1? ... , а'п}\ = 1, имеем противоречие. Таким образом, если а не является Д-петлей, то любая ненулевая К-конгруэнция на A(UR) содержит кортеж (а'1У... ,а^), не являющийся R-ребром. Следовательно, система Л{ац) подпрямо неразложима в К . Пусть Л -- конечная система, имеющая бесконечное множество ре­ бер. Если Л содержит бесконечное множество ребер, не являющихся петля­ ми, то по доказанному выше в К существует бесконечное семейство неизо-

16

В. Л. Горбунов, А. В. Кравченко

морфных подпрямо неразложимых систем, и в этом случае универсальный хорнов класс К не является конечно-порожденным. Пусть система Л имеет лишь конечное число ребер, не являющихся петлями. В силу конечности А существуют элемент a £ А и бесконечное семейство предикатов (R%)i^i в L такие, что ( а , . . . , а) является Д,-ребром для всех г g J. Пусть Л,- = Л(а7я.), а( обозначает элемент а' в A,, a oj — набор ( а , . . . , а) в А,-. Покажем, что подпрямо К-разложимых систем среди А% лишь конечное число. Пусть fi — произвольный гомоморфизм из Д, на систему S; £ К , а gi — гомоморфизм из В,- в Л. Поскольку Л является ядром, i) = Sjfj(aj)

= ж- Если х ф а, то по построению системы Л,- для лю­

бых предикатного символа Р и набора элементов Ь, кроме случая Р = Щ и Ь = (ж,... , я), из Ъ 6 Р л следует Ь* £ Р л , где 6* получается из Ь заменой всех вхождений а на ж. Аналогичное утверждение верно для системы Aj, поэтому для любых предикатного символа Р и набора элементов Ъ справед­ ливо Ь* £ Р 4 , если Ь £ Р л . В частности, отображение, отождествляющее элементы а и ж, является гомоморфизмом из Л на собственную подсистему с носителем А \ {а}, что невозможно. Таким образом, для всех i £ / , за исключением не более чем \А\ — 1, ker #,/, = Ол U {(а,-, а(-)«, (о(-,... , а^яЛПри этом (at-,a() £ (ker/,•)(«) влечет (а(,... , а£) £ (ker/;)(JR t ). Поскольку /,- — произвольный гомоморфизм, для всех г £ J, кроме конечного числа, система Л, является подпрямо неразложимой в К. • ЗАМЕЧАНИЕ 3.2. В монографии [12] приводится другое доказатель­ ство этой теоремы, предложенное Ю. Л. Ершовым. В качестве следствия получаем, что для любых антимногообразия К систем конечной предикатной сигнатуры и конечной системы Л 6 К цветосемейство [К —» Л] резидуально конечно. Более точно, из доказа­ тельства теоремы 3.1 следует, что если \А\ = п и все символы из L имеют арность меньше т , то [К —>• Л] резидуально меньше п + т. Однако условие, что К представляет собой антимногообразие, не яв­ ляется необходимым. Действительно, рассмотрим класс С орграфов, опре-

Антимногообразия алгебраических систем

17

деленный предложениями (ЧхуУР(х,х), (Vxyz) Р{х, у) к Р(х, *) - • у = z, (Vxyz) Р(г/, х) к P(z, х) -> у = я, и семейством антитождеств (Va?i ...хп)

"(Р(я?1, х2) к Р{х2}

х3)к... ... &P(sn_i,sn)&P(xnia:i)),

п ^ 2.

Через £ п обозначим систему с носителем { a i , . . . , a n } , в которой Р[щ, a,j] выполняется тогда и только тогда, когда j = i + l, l ^ i ^ n — 1. Пусть &п + ^ « обозначает непересекающееся объединение двух изоморфных ко­ пий системы /Сп. Ясно, что никакая система Ln((flt>ui+i)p)» 1 ^

х

^

п

~~ 1*

не

принад­

лежит [С -> £ п ] . Однако этот универсальный хорнов класс порождается одной системой £ „ + &„ (см. [13]). С другой стороны, требование, чтобы сигнатура была предикатной, существенно. Действительно, пусть L = {Р}, где F — унарный функцио­ нальный символ. Рассмотрим цветосемейство К = [L -> Сг], где для fc ^ 2 система Cjt определяется следующим образом: носителем является мно­ жество { a i , . . . ,ajt}, а операция Р определена по правилу P(a t ) = a t +i, i ^ n - 1, и P ( a n ) = oi. Очевидно, для любого простого числа р > 2 си­ стема 62Р принадлежит цветосемейству К. С другой стороны, нетрудно видеть, что у всех систем вида Q2p решетка К+-конгруэнций изоморфна 3-элементной цепи, поэтому все они подпрямо неразложимы в К + . Значит, цветосемейство К, порожденное конечной системой 62? не является резидуально конечным. Переходя к графикам систем, получим пример ква­ зимногообразия орграфов К такого, что для некоторой конечной системы Л 6 К цветосемейство [К —> А] не является резидуально конечным. В связи с этим представляет интерес вопрос о нахождении какихлибо условий, гарантирующих конечную или бесконечную порожденность цветосемейств в данном собственном универсальном хорновом классе.

18

В. А. Горбунов, А. В. Кравченко § 4. Цветосемейства ф о р м а л ь н ы х я з ы к о в Сначала напомним некоторые определения из теории формальных

языков (см. [14, 15]). Алфавит А — это непустое множество (обычно в теории формальных языков рассматривают только конечные алфавиты, но мы будем допус­ кать также случай, когда алфавит А бесконечен). Пусть А* — свободный моноид с порождающим множеством А. Единица свободного моноида А* называется пустым словом и обозначается А, остальные элементы в А* — словами. Для. каждого непустого слова w длина \w\ определяется как чис­ ло к такое, что w = Х\ ...Xk, где я, G А, Ц

i О - Д л я пустого слова А

полагаем |А| = 0. Пусть А, В — алфавиты, морфизмом называется отображение h : А* —»• U* такое, что h(uv) = h(u)h(v) для всех и) v E А* (т. е. это обычный гомоморфизм свободных моноидов). Для подмножества L в А определим h(L) = {h(w) : w G L}. Морфизм h называется побуженным, если h(A) С СВ. Формальным языком над А называется пара (A, L), где L С А*. Язык (A, L) является конечным, если множества А и L конечны. Для данных языков (A, L) и (В, К) побуквенный морфизм h : А* —> JB* называется гштерпретацией (A, L) в (В, К"), если /i(L) С К. Будем использовать запись L < К, если существует интерпретация (A,L) в

(В,К).

С языком (A, L) над конечным алфавитом свяжем три языковых се­ мейства: 0) Loo(L) = {К : К < L}; (2) -С (!) = {К : К < L,K — язык над конечным алфавитом}; (3) £ F ( £ ) = { # : К < L,K — конечный язык}. Очевидно, для любых языков L\, L £ (£i) = £ (£2) =^ =Ф £ F ( £ I ) = £ F ( ^ 2 ) . Maypep, Саломаа и Вуд [16] доказали, что выпол­ няется также импликация H>F(LI) = ^ F ( ^ 2 ) =* ^oo(^i) = ^00(^2), т. е. все

Антимногообразия алгебраических систем

19

указанные равенства эквивалентны. Используя результаты предыдущего параграфа, дадим другое доказательство этого факта. Сначала установим соответствие между языками и предикатными системами специального вида. Рассмотрим предикатную сигнатуру R = = {Rn : п < а;}, где Rn — это n-местный предикатный символ. С формаль­ ным языком (A, L) свяжем систему Ль сигнатуры R, носителем которой является алфавит А, а предикаты интерпретируются следующим образом: Ль \= Л„[а ь • • • 1fln]^ o i . . . a n € L. Л Е М М А 4 . 1 . Пусть (А,Х) — лзшгс над конечным алфавитом. Существует интерпретация (В, К) в (A, L) тогда и только тогда, когда существует гомоморфизм из Ък в ЛьДОКАЗАТЕЛЬСТВО. Пусть К < L и h - соответствующий морфизм. Поскольку h — побуквенный морфизм, он задает отображение ал­ фавитов, которое будем обозначать также через h. Теперь h : В -> А — ото­ бражение из Вк в Аь такое, что из Ък [= iZ n [ai,... , а„], в силу включения h(K) С L и определения морфизма, получаем Ль (= Rn[h(ai)1...

, /i(a n )],

т. е. это гомоморфизм предикатных систем. Обратно, пусть h : Ък —> Ль — гомоморфизм. Продолжим его до гомоморфизма из В* в А* (обозначим его также /г). Поскольку В* и А* — свободные моноиды, h сохраняет длины слов. Теперь из определения си­ стем Ль и Ък получаем, что а\ ...апЕКп a

том и только в том случае,

если Ък И Rn[au • • • > n]- Отсюда /2n[M i)> * • • » Ma*0] выполняется в Ль тогда и только тогда, когда h(a\). ,.h(an)

a

G L, т. е. h(K) С L и К < L. П

Согласно лемме 4.1, формальные языки можно рассматривать как предикатные системы счетной сигнатуры R = {Rn : n £ и } . Поэтому к ним применимы многие алгебраические конструкции. Например, для фор­ мальных языков (A,L) и (B,2i) их прямое произведение (А х В, К х L) представляет собой множество слов (ai, &i)... (a n , Ь„) над алфавитом Ах В таких, что a i . . .a n 6 I и b i . . .Ь п G А'. Язык (A, L) является подъязыком (J3, К"), если А С В и I С / { . Кроме того, для формальных языков можно определить понятие истинности формул сигнатуры R (формула <р истинна

20

В. А. Горбунов, А. В. Кравченко

в языке (A, L) в том и только в том случае, если <р истинна в соответству­ ющей предикатной системе Аь) и говорить об аксиоматизируемых классах формальных языков. Поскольку для любой конечной системы Аь сигнатуры R класс [R —у —> Аь] является универсальным хорновым классом, этот класс определя­ ется своими конечными системами, что в силу леммы 4.1 дает утверждение теоремы Маурера—Саломаа—Вуда. Т Е О Р Е М А 4.2. Для любого языка (A, L) над конечным алфавитом языковое семейство £>oo(L) определяется своей конечной частью т. е. если &р(Ьх) = Яр{Ь2) для двух языков над конечными

&p(L),

алфавитами,

то Loo{Li) = /Соо(Ь2). Наконец, теорема дает следующую алгебраическую характеризацию цветосемейств формальных языков. Т Е О Р Е М А 4.3. Для любого конечного языка (A, L) £»оо(£) является

семейство

конечно-порожденным универсальным хорновым клас­

сом с разрешимой универсальной теорией. Более того, по данному языку (A, L) можно эффективно найти конечные языки, порождающие Loo(L). ДОКАЗАТЕЛЬСТВО. Из леммы 4.1 следует, что (В, К) G £«>(.£) в том и только в том случае, если Ък 6 [R —> Аь\. Поскольку (A, L) — конечный язык, то по теореме 3.1 цветосемейство [R —> Аь] является ко­ нечно-порожденным универсальным хорновым классом. Кроме того, со­ гласно доказательству этой теоремы по данной системе Аь можно эффек­ тивно указать порождающие для класса [R —> Аь]- Наконец, поскольку в Аь множество ребер конечно, найдется число т такое, что системы из [R —> Аь] не имеют J?n-pe6ep для всех п > т . Следовательно, не огра­ ничивая общности, можно считать, что сигнатура системы Аь конечна. Тогда по теореме Бурриса—Вернера [17] класс [R -» Аь] имеет модельный компаньон К, а по теореме Бурриса [18] элементарная теория класса К разрешима. Осталось заметить, что универсальные теории классов К и [R -> Аь] совпадают. •

Антимногообразия алгебраических систем

21

ЛИТЕРАТУРА 1. V. Л. Gorbunov, A. V. Kravchenko, Universal Horn logic, colour-families and formal languages, Proc. Conf. General Algebra and Discrete Math., Shaker Verlag, Aachen, 1997, 77-91. 2. А, И. Мальцеву Алгебраические системы, М., Наука, 1970. 3. В. л . Горбунов, Мощности подпрямо неразложимых систем в квазимного­ образиях, Алгебра и логика, 25, N 1 (1986), 3—50. 4. В. А. Горбунов, Б. И. Туманов, Строение решеток квазимногообразий, в кн. "Математическая логика и теория алгоритмов" (Труды Ин-та матем. СО АН СССР, 2), Новосибирск, Наука, 1982, 12-44. 5. L< Lovdsz, On the cancellation law among finite relational structures, Period. Math. Hung., 1, N 2 (1971), 145-156. 6. R. R. Appleson, L. Lovdsz, A characterization of cancellable fc-ary strutures, Period. Math. Hung., 6, N 1 (1975), 17-19. 7. P. Hell, J. Nesetfil, The core of a graph, Discrete Math., 109, N 1-3 (1992), 117-126. 8. B. Bauslaugh, Core-like properties of infinite graphs and structures, Discrete Math., 138, N 1-3 (1995), 101-112. 9. B. L. Bauslaugh, Compactness and finite equivalence of infinite digraphs, Discrete Math., 167/168 (1997), 115-126. 10. P. Erdos, R. Rado, A partition calculus in set theory, Bull. Am. Math. Soc, 62 (1956), 427-489. 11. W. Taylor, Some constructions of compact algebras, Ann. Math. Logic, 3, N 4 (1971), 395-435. 12. В. А. Горбунов, Алгебраическая теория квазимногообразий, Новосибирск, Научная книга, 1999. 13. л . В. Кравченко, О решеточной сложности квазимногообразий графов и эндографов, Алгебра и логика, 36, N 3 (1997), 273—281. 14. л . Salomaa, Formal Languages, New York—London, Academic Press, 1973. 15. А. Саломаа, Жемчужины теории формальных языков, М., Мир, 1986. 16. Н. A. Maurer, A. Salomaa, D. Wood, Finitary and infinitary interpretations of languagues, Math. Syst. Theory, 15, N 3 (1981/82), 251-265.

22

В. А. Горбунов, А, В.

Кравченко

17. S. Burris, H. Werner, Sheaf constructions and their elementary properties, Trans. Am. Math. Soc, 248, N 2 (1979), 269-309. 18. 5. Burris, Model companions for finitely generated universal Horn classes, J. Symb. Log,, 49, N 1 (1984), 68-74.

Адрес автора: К Р А В Ч Е Н К О Александр Владимирович, РОССИЯ, 630090, г. Новосибирск, пр. Акад. Коптюга, 4, Институт математики СО РАН. e-mail: [email protected]

Поступило 23 ф е в р а л я 1999 г.