Функциональные представления ограниченных дистрибутивных решеток

дипломная работа

1. Основные определения

1.1 Решетка

Def1. Алгебраическая система называется решеткой, если выполняются:

аксиомы идемпотентности

; ;

аксиомы коммутативности

аксиомы ассоциативности

законы поглощения

;

Решетка называется дистрибутивной, если

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

В дальнейшем будут рассматриваться только ограниченные дистрибутивные решетки.

Пример 1. Легко проверить, что следующие объекты являются ограниченными дистрибутивными решетками:

Def2. Непустое подмножество дистрибутивной решетки называется идеалом решетки , если

Идеал дистрибутивной решетки называется собственным, если .

Собственный идеал дистрибутивной решетки называется простым, если .

Для любого идеала множество называется 0-компонентой идеала .

Пример 2. Простым идеалом решетки (пример 1, рисунок 2) является решетка (рис. 3):

0-компонентой идеала в решетке является множество

Def3. Бинарное отношение ~ в решетке называется конгруэнцией, если выполняются свойства:

1) ~ является отношением рефлексивности, симметричности и транзитивности;

2) ~ сохраняет операции:

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

Доказательство. Операции и определяются через представителей классов, и необходимо показать их корректность, т.е. независимость результатов от выбора представителей. Это вытекает в силу гомоморфности

операции и ассоциативны, т.к. ассоциативны операции в , также сохраняются идемпотентность, коммутативность, законы поглощения и дистрибутивности. Классы [0] и [1] будут нейтральными элементами относительно и соответственно. Предложение доказано.

Пример 3. Конгруэнции на решетках.

1) Конгруэнция Ламбека ().

Для некоторого простого идеала решетки и отношение

называется конгруэнцией Ламбека по простому идеалу решетки .

Теорема Отношение конгруэнция на решетке

Доказательство. Рефлексивность и симметричность отношения очевидны. Пусть и , т.е. и для некоторых . В силу простоты идеала найдется такой элемент , что элемент не лежит в . Из равенства в силу определения решетки следует и учитывая, что , получаем, что , что доказывает транзитивность отношения .

Докажем сохранение операций. Пусть , , что означает для подходящих , а для некоторого . Из первого равенства получаем , а из второго . Почленно сложив равенства, получим , т.е. . Умножим на , а на и получим , откуда или .

2) Конгруэнция Корниша ().

Для некоторого простого идеала решетки и отношение

называется конгруэнцией Корниша по простому идеалу решетки .

Теорема Отношение конгруэнция на решетке

Доказательство. Рефлексивность и симметричность очевидны. Покажем транзитивность. Пусть и . Это значит, по определению конгруэнции Корниша, что и для некоторых . Прибавив к первому равенству получим

.

Осталось показать, что и . Это следует из определения : , для некоторых . Рассмотрим выражение .

Для рассуждения аналогичны.

Докажем сохранение операций.

Сложение: Пусть для некоторых . Требуется доказать, что . По определению конгруэнции: .

Складывая эти равенства, получаем:

,

Где . Тем самым, сохранение операции сложения доказано.

Умножение: Умножая равенства , получаем:

,

откуда очевидно, что операция умножения также сохраняется при этой конгруэнции.

Для некоторого простого идеала решетки и отношение

также определяет конгруэнцию Корниша.

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

· - очевидно.

: Пусть для некоторого простого идеала решетки и выполняется отношение , где для некоторых . Тогда , где по определению простого идеала. Или, .

Прибавляя к равенству получим: , что означает выполнимость .

В качестве иллюстрации рассмотрим фактор-решетки и (решетка из примера 2):

Делись добром ;)