Cтраница 3
Очевидно, что если ( Л) имеет дыру, то ( А) не является ни верхней, ни нижней полурешеткой. [31]
У имеет базис из гомотипных тождеств; ( 2) все тождества из щТ гомотипны; ( 3) Т содержит многообразие всех полурешеток. У состоит из архимедовых полугрупп ] ( см. [44], с. Тождество и и называется уравновешенным, если каждая буква входит в слова ы и с; одинаковое число раз. У имеет базис из уравновешенных тождеств; ( 2) все тождества из eqV уравновешенные; ( 3) У содержит многообразие всех коммутативных полугрупп. В силу ( 3) многообразия с указанными свойствами называют надкоммутатив-ными. Многообразие не будет надкоммутативным тогда и только тогда, когда оно состоит из периодических полугрупп. Если многообразие У содержится в классе полугрупп. [32]
Таким образом, качум Я является категорией с [ конечными ] произведениями тогда и только тогда, когда Я - полная [ обычная ] полурешетка относительно пересечений. [33]
Вторым фундаментальным фактом, касающимся структур степеней Тьюринга, является то обстоятельство, что они так же как и m - степени, образуют верхнюю полурешетку. [34]
Лемма 1.10.5. Если полугруппа S k - тестируема для некоторого положительного целого k, то для любого идемпотента е е 5 моноид eSe является полурешеткой. [35]
В силу замеченного выше об изоморфизмах подалгебр алгебры А в сигнатуре а и сигнатуре (), а также свойства sij совокупности основных множеств подалгебр алгебры А и полурешетки ( А Л) совпадают, совпадают также и совокупности изоморфизмов между этими подалгебрами в сигнатурах а и () соответственно. [36]
При и 3 шкалы ( РСТ ( п); ), ( Э СТ ( п); ), ( ЕСТ ( п) ]) не являются ни верхней ни нижней полурешетками. [37]
Теорема 1.10. Язык LsA локально тестируем тогда и только тогда, когда его синтаксическая полугруппа S ( L) конечна, и для любого идемпотента eeS ( L) моноид eS ( L) e является полурешеткой. [38]
Пусть В ( В ] Л) - некоторая полурешетка и условный терм t ( x, у) сигнатуры ( Л) таков, что ( B t ( x, у)), снова является полурешеткой. [39]
В силу отмеченного выше, если на га-элементной алгебре А - ( А а выполнены условия si) - s s) то Для любых a, b Е А имеет место равенство а Л b - inf a, b и, значит, алгебра В - ( А ] Л) является полурешеткой. [40]
Полурешетки называются также полуструктурами. [41]
Идемпотенты в 7 в имеют вид a - kak ma-m. Полурешетка EI ( а) изоморфна полурешетке, полученной отбрасыванием наибольшего элемента из прямого произведения двух цепей целых отрицательных чисел. [42]
После определения той или иной сводимости ее изучение развивается в основном в двух направлениях. Первое связано с вопросами описания верхней полурешетки степеней относительно введенной сводимости. Известным примером проблемы такого типа явилась проблема Поста [1]: верно ли, что все рекурсивно перечислимые нерекурсивные множества имеют одну и ту же степень неразрешимости. Или, другими словами, верно ли, что полурешетка рекурсивно перечислимых степеней неразрешимости состоит лишь из двух элементов. Решения этих вопросов о строении верхних полурешеток рекурсивно перечислимых т -, U - и Г - степеней являются определенными вехами в изучении сводимостей. Позднее выяснилось, что этот факт не имеет места для Ьи - и более слабых сводимостой. Установлено, что элементарные теории полурешеток т -, Ьи -, U -, Т - и нек-рых других степеней попарно различны. [43]
Идемпотенты в 7 в имеют вид a - kak ma-m. Полурешетка EI ( а) изоморфна полурешетке, полученной отбрасыванием наибольшего элемента из прямого произведения двух цепей целых отрицательных чисел. [44]
Пусть задана некоторая Г - алгебра В и / - множество всех ее конечно порожденных подалгебр. Тогда / является частично упорядоченным множеством и верхней полурешеткой. [45]