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

• Автор: Шеремет, Михаил Сергеевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Новосибирск
• Количество страниц: 81 с.

Содержание
Введение
Глава 1.
Семантики равенства на частичных алгебрах
1. Основные конструкции на алгебрах
2. Предикатные представления частичных алгебр
3. Определение и простейшие свойства семантик
4. Описание алгебр, заданных соотношениями
на определенность термов
5. Исчисление тождеств для слабой семантики
6. Исчисление тождеств в семантике Эванса
Глава 2.
Разложения в квазимногообразиях частичных алгебр
7. Характеризация квазимногообразий частичных алгебр
8. Неразложимые и подпрямо неразложимые алгебры
9. Конгруэнции
10. Квазимногообразия частичных алгебр,
в которых мощности неразложимых алгебр ограничены
11. Примеры многообразий частичных алгебр, в которых классы подпрямо неразложимых
алгебр не аксиоматизируемы в
Литература
Введение
Началом исследований частичных алгебр можно считать вышедшую в 1951 году работу Эванса [21], в которой он определил понятие истинности тождества на частичной алгебре и доказал, что в многообразии полных алгебр, определенном тождествами Е, однородная проблема равенства разрешима, если любая частичная алгебра, удовлетворяющая Е, вложима в полную алгебру из данного многообразия.
Вообще, широкий круг вопросов связан с изучением частичных алгебр, возникающих как “части” полных алгебр некоторого данного класса, см. [23, глава 2]. С другой стороны, алгебры с частичными операциями совершенно естественно возникают в информатике (см., например, [10], а также пункт 22.2 в [14], посвященный этому вопросу) и их изучение также требовало построения соответствующей теории.
Достаточно быстро стало очевидно, что большинство понятий универсальной алгебры могут быть обобщены на частичный случай множеством способов. Это относится и к определению истинности равенства. Таким образом, в различных работах строились различные теории частичных алгебр, подобные друг другу и существующей универсальной алгебре. Рассмотрим основные результаты, которые были получены к настоящему времени.
Равенство в и 4 называется истинным в слабой семантике в частичной алгебре А при означивании у, если из того, что значения 5' [г] и ЬЛ[и] определены, следует, что они равны. Тождества в слабой семантике рассматривались в работах Поитресс [26], Рудака [28, 29] и Бинчака [12]. В частности, в [28] строится полная и корректная система правил вывода для тождеств в слабой семантике. В [12] дается описание классов частичных алгебр, аксиоматизируемых тождествами в слабой семантике.
Равенство з ~ I называется истинным в семантике Клини в частичной алгебре А при означивании V, если из того, что одно из значений [и] и Р4[г] определено, следует, что определено второе и они равны. Различные вопросы, связанные с тождествами в семантике Клини, изучались в работах Андреки, Крейга и Немети [8], Крейга [19], Робинсона [27] и Бёрнера [13]. В работе [19] детально исследованы исчисления для тождеств в семантике Клини в сигнатуре, расширенной дополни-

тельными логическими символами (например, проекции или пустого отображения). В [27] строится полная и корректная система правил вывода для тождеств в семантике Клини. В [13] дается характеризация в терминах клонов и в терминах алгебраических операторов для классов, аксиоматизируемых тождествами в семантике Клини в сигнатуре с логическим символом для проекции.
Наконец, равенство я ке в частичной алгебре Л при означивании г», если значения л,-д[?;] и Ьл[у] определены и равны. В отличие от всех других семантик, в которых простейшие формулы с равенством интерпретируются как условные, для сильной семантики имеет смысл рассматривать не только тождества, но и произвольные формулы, в частности, квазитождества. В монографии [14], основу которой составляют результаты, полученные Андрекой, Бурмайстером и Немети (ср. [9]. [7]), для различных фрагментов квазиэквациональной логики в сильной семантике приводятся полные и корректные системы правил вывода, а также характеризация классов частичных алгебр, аксиоматизируемых соответствующими предложениями. Заметим, что многообразия частичных алгебр в других семантиках являются квазимногообразиями специального вида в сильной семантике.
В первой главе диссертационной работы изучаются многообразия частичных алгебр в случае произвольной семантики. Изучается вопрос, в каких семантиках многообразия частичных алгебр замкнуты относительно тех или иных алгебраических операций. Строится полная и корректная система правил вывода для тождеств в семантике Эванса.
Во второй главе изучаются структурные свойства квазимногообразий частичных алгебр в сильной семантике. Дается характеризация квазимногообразий частичных алгебр в терминах подпрямых произведений и надпрямых пределов.
Вводятся понятия разложения и частичного разложения. Доказывается, что в квазимногообразиях частичных алгебр существует хорошая структурная теория для (частично) неразложимых алгебр, которая в определенном смысле является частью теории подпрямо неразложимых систем в квазимногообразиях алгебраических систем.

Пусть выполняется (4.3). Тогда каждая переменная, входящая в £, входит в некоторый терм вида го(ж), где х — переменная, входящая в р или в д (т. е. принадлежащая Е+(р, д)). Поскольку множество Е+{р,я) конечно, то согласно предположению Е+(р,д) С С1 е0(&) Для некоторого конечного подмножества Е0 С Е. Положим Е1 = Е0 и {р ~ я}- Тогда Е — (Е')* для некоторого конечного подмножества
к'с ки £€01^(5). □
ЛЕММА 4.3. Пусть Е — множество тождеств, Б — множество термов и пусть £ £ С1 в (Я). Пусть все термы из Б определены в алгебре А при означивании V : X —> А и Е. Тогда значение Ь р также определено.
ДОКАЗАТЕЛЬСТВО. Пусть С1 е(Б) = и„,еы Пп как в определении. Поскольку По = Б, в случае £ 6 По доказывать нечего. Предположим, что утверждение леммы справедливо для любого терма из Н„. Пусть £ £ Пп+1.
Если выполнено условие (4.1), то требуемое сразу получается из предположения для в £ 1/п.
Пусть выполняется (4.2). Тогда для каждого i < т найдутся тождество в^х) « и(х) £ Е* и последовательность термов щ такие, что Рг = з^щ), д, — Получаем, что А в^х) ~ ti(x) и по предполо-
жению значения термов фоО^о), • • • , «т-1(«т-1)), ^(щ), • ■ • Лт-1(йт-х) определены в А при означивании и. Поэтому з^йг)Л[у] = ^(щ)л[у], и значение терма £ = з(до(йо)> • • •, Ут-^т-х)) также определено в А при означивании у.
Пусть выполняется (4.3). Тогда А р и по предположению все термы из множества Е+(р, д) [н] определены в А при означивании у. Пусть У обозначает множество всех переменных, входящих в р или в д. Тогда для каждого у £ У терм ю(у) определен в А при означивании у. Рассмотрим произвольное отображение и' : X -» А такое, что у1 (у) = уи(у)л[у] для всех у £ У. Тогда все термы из К(р, д) будут определены в А при означивании у1. Следовательно, значения р[эд]'4[щ] = рл[и'] и д^-'Чд] = дл[и' также будут определены (и равны). □