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

Алгебра и логика, 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]. Таким образом, изучение универсальных хорновых классов сводится к изучению квазимногообразий. Как мы увидим дальше, в некоторых слу­ чаях удобней и естественней рассматривать произвольные (в частности, собственные) универсальные хорновы классы.