Решетка конгруэнций - Формационные основы универсальных алгебр

Если - отношение эквивалентности на множестве и, то будем это отношение изображать в виде неориентированного графа

Ris04.eps

Ris05.eps

4.1. Теорема. Множество всех подалгебр, отношений эквивалентности и конгруэнций алгебры, упорядоченных по включению, образуют решетку.

Доказательство.

1) Пусть - подалгебра алгебры, тогда

Inf,

А sup -

Подалгебра, порожденная множеством.

2) Пусть, - отношения эквивалентности на, тогда множество называется произведением отношений и и в общем случае не являются отношением эквивалентности на (рис. 5). Обозначим

Очевидно, что рефлексивно и транзитивно. Пусть. Тогда, как следует, из (рис. 7),

Обозначим =sup. Покажем, что. Пусть.

Так как и, то из (рис. 6) видно, что

,

Т. е. .

Следовательно, и = sup. Очевидно, что = inf и множество всех отношений эквивалентности на образует решетку.

3). Пусть - - арная операция и,=1,2,.., ( рис.8).

Так как и --конгруэнции, то

, .

Следовательно,

И, значит, - подалгебра алгебры. Теперь из 2) следует, что множество всех конгруэнций на алгебре образует решетку. Теорема доказана.

Наименьший элемент решетки конгруэнции будем называть Нулевой конгруэнцией (Нулевым элементом ) и обозначать

,

А наибольший элемент -- единичной конгруэнцией (единичным элементом) и обозначать.

Произведение конгруэнций в общем случае не является конгруэнцией. Поэтому естественно возникает вопрос, когда это возможно?

4.2. Теорема. Произведение двух конгруэнций является конгруэнцией тогда и только тогда, когда они перестановочны.

Доказательство. Пусть и - конгруэнции на алгебре и - конгруэнция на. Тогда из того, что следует, что и. Это означает, что существует такой элемент, что

, т. е..

Итак, . Аналогичным образом показываем, что, т. е. .

Пусть. Так как для любого элемента и, то ( рефлексивность ). Пусть. Так как, то, т. е. для некоторого элемента

,

Но это и означает, что (симметричность).

Пусть

Так как, то для некоторого элемента имеем

.

Следовательно,

(транзитивность).

Пусть - - арная операция и

.

Тогда

,

Для некоторых элементов. Так как и -- конгруэнции, то

,

Т. е. .

Тем самым показано, что - конгруэнция на. Теорема доказана.

Из теорем 4.1 и 4.2 получаем

    4.3. Следствие. Пусть конгруэнции и алгебры перестановочны. Тогда sup 4.4. Пусть - Конгруэнции на алгебре Такие, что И. Тогда говорят, что и Образуют прямое произведение и пишут . 4.5. Лемма. Пусть . Тогда для любого элемента существует единственный элемент такой, что

.

Доказательство.

Пусть

и

Тогда, как видно из рисунка,

,т. е. .

Лемма доказана.

4.6. Теорема. Если контруэнции алгебры перестановочны, то они образуют модулярную решетку.

Доказательство. Пусть, , - конгруэнции по алгебре и. Покажем, что

.

Пусть

.

Тогда

Для некоторого элемента. Так как, то, а так как, то. Итак, , т. е.

.

Пусть теперь. Тогда найдется такой элемент, что

.

Так как, то. Теперь из того, что cледует, что. Итак,

.

Ho, значит,

,т. е. .

Теорема доказана.

Похожие статьи




Решетка конгруэнций - Формационные основы универсальных алгебр

Предыдущая | Следующая