logo
КЛ

§ 7. Решетки (структуры). Изоморфизм

Структура – с латинского языка: расположение, строение. Чтобы определить структуру, задают отношения, в которых находятся элементы множества (типовая характеристика структуры), а затем постулируют, что данные отношения удовлетворяют определенным условиям – аксиомам структуры. Часто под структурами понимают решетки.

Понятие решетки относится к середине Х І Х века. Впервые его ввел немецкий математик Рихард Дедекинд , а термин “решетка” принадлежит американскому ученому Гаррету Биркгофу.

Решеткой (структурой ) называется частично упорядоченное множество, в котором любые два элемента mi , mj имеют единственную наибольшую нижнюю грань, или пересечение , и единственную наименьшую верхнюю грань, или объединение .

Упорядоченное множество , двойственное решетке М , является решеткой, в которой пересечение и объединение меняются ролями.

Решетка может быть определена как алгебра , сигнатура которой обладает следующими свойствами:

1. (идемпотентность);

2. (коммутативность);

3. ,

(ассоциативность);

4. , ( поглощение ).

Здесь - операция взятия наименьшей верхней грани элементов (объединения); - операция взятия наибольшей нижней грани элементов (пересечения ).jqщий на пересечении чно сопоставляют элемент множества -

0000000000000000000000000000000000000000000000000000000000

Решетка, в которой пересечение и объединение существуют для любого подмножества ее элементов, называется полной решеткой (полной структурой).

Объединение всех элементов полной решетки (полной структуры) – это максимальный элемент решетки, называемый единицей решетки (структуры).

Пересечение всех элементов полной решетки (полной структуры) – это минимальный элемент решетки, называемый нулем решетки (структуры).

Упорядоченное множество не является решеткой:

1. когда какие – либо два элемента не имеют верхней или нижней грани;

2. когда для некоторой пары элементов наименьшая верхняя (или наибольшая нижняя) грань не единственна.

Подрешеткой решетки А называется подмножество решетки А , которое вместе с каждой парой элементов тi и mj содержит также и .

Интервалом I , определенным элементами и в решетке А , называется подрешетка решетки А с наименьшим элементом и наибольшим элементом :

В решетке А со структурными нулем и единицей два элемента и называются дополнительными, если и .

Элемент , дополнительный к т , называется также дополнением элемента т в решетке А .

Два элемента, обладающие общим дополнением в решетке А , называются связанными в А .