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

Алгебра и логика, 39, N 1 (2000), 23-46 УДК 512. 57 ХОРНОВЫ КЛАССЫ ПРЕДИКАТНЫХ СИСТЕМ И М Н О Г О О Б Р А З И Я Ч А С Т И Ч Н Ы Х АЛГЕБР*) В- А. ГОРБУНОВ, М . С . Ш Е Р Е М Е Т В работе предлагается подход, позволяющий для частичных алгебр применять методы теории квазимногообразий предикатных систем. Для всякой частичной алгебры Л рассматриваем два ее предикатных пред­ ставления. Первое — это график алгебры Л, в котором основными от­ ношениями являются графики ее основных операций. Второе получается из графика алгебры Л, если в качестве основных отношений добавляются области определения ее операций. Выбор представления зависит от рас­ сматриваемого типа вложения для частичных алгебр. Переход к графи­ кам сохраняет основные алгебраические конструкции и позволяет исполь­ зовать стандартные методы теории алгебраических систем. С другой сто­ роны, понятия подалгебры и конгруэнции, дословно переносимые с алгебр на предикатные системы, теряют свою силу. Более адекватное определе­ ние конгруэнции на алгебраической системе дано Горбуновым и Тумано­ вым в [1]. Понятие оператора порождения, вводимое в настоящей работе, для предикатных систем представляет собой возможный аналог обычной операции порождения для алгебр. Отметим, что существует другой подход, предложенный в работах Андрека, Немети [2] и Бурмайстера [3]. В его основе лежит идея переноса "' Работа выполнена при финансовой поддержке Госкомитета РФ по высшему обра­ зованию, проект 1998 г. , совместной поддержке Российского фонда фундаментальных исследований, проект 96-01-00097, и Немецкого научно-исследовательского общества, проект 436113/2670, а также при поддержке ФЦП "Интеграция", проект 274. © Сибирский фонд алгебры и логики, 2000 24 В. А. Горбунов, М. С. Шеремет существующей теории для полных алгебр на частичные с помощью тео­ рии категорий. При таком подходе главным становится вопрос о том, что является действительным аналогом обычных тождеств в случае частич­ ных алгебр. В [2, 3] было найдено несколько исчислений, для которых, в частности, доказаны теоремы полноты и аналоги HSP-теоремы Биркгофа. Те же исследования показали, что сходство между частичными и полны­ ми алгебрами достаточно ограниченно. И именно с точки зрения теории категорий частичные алгебры обладают многими "плохими64 свойствами, характерными для предикатных систем, а не для полных алгебр. Мы считаем, что в случае частичных операций возможно несколько в равной мере естественных интерпретаций равенства. Изучение частичных алгебр с различных точек зрения приводит к необходимости рассматри­ вать различные семантики равенства: семантика Эванса возникла в связи с исследованием проблемы равенства слов и связанной с ней проблемы вложения [4], истинность тождеств в семантике К лини связана со строе­ нием клонов частичных операций [5], а эквациональная логика в сильной семантике наиболее близка к эквациональной логике полных алгебр [2, 3].