Обобщ нно булевы решетки

СОДЕРЖАНИЕ: Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Вятский государственный гуманитарный университет

Федеральное агентство по образованию

Государственное образовательное учреждение
высшего профессионального образования
Вятский государственный гуманитарный университет

Математический факультет

Кафедра алгебры и геометрии

Выпускная квалификационная работа

Обобщенно булевы решетки

Выполнил:

студент V курса математического факультета

Онучин Андрей Владимирович

Научный руководитель:

к.ф.-м.н., доцент кафедры алгебры и геометрии ВятГГУ
Чермных Василий Владимирович

Рецензент:

д.ф.-м.н., профессор, зав. кафедрой алгебры и геометрии ВятГГУ

Вечтомов Евгений Михайлович

Работа допущена к защите в государственной аттестационной комиссии

«___» __________2005 г. Зав. кафедрой Е.М. Вечтомов

«___»__________2005 г. Декан факультета В.И. Варанкина

Киров

2005

Содержание

Введение.......................................................................................................... 3

Глава 1............................................................................................................. 4

1.1. Упорядоченные множества................................................................... 4

1.2. Решётки.................................................................................................. 5

1.3. Дистрибутивные решётки..................................................................... 7

1.4. Обобщённые булевы решётки, булевы решётки................................. 8

1.5. Идеалы................................................................................................... 9

Глава 2........................................................................................................... 11

2.1. Конгруэнции....................................................................................... 11

2.2. Основная теорема............................................................................... 16

Библиографический список.......................................................................... 22

Введение

Булева решётка представляет собой классический математический объект, который начал интенсивно изучаться в работах М. Стоуна 30-е годы 20-го века, расширением этого понятия до обобщённо булевых решёток занимались Г. Гретцер и Е. Шмидт в своих трудах конца 50-х годов.

Цель данной работы: установление взаимно однозначного соответствия между конгруэнциями и идеалами в обобщённо булевых решётках. (Для булевых решёток это положение доказано в книге [2], кроме того, сформулировано в книге [3] в качестве упражнений). А также – установление связи между обобщённо булевыми решётками и булевыми кольцами.

Данная дипломная работа состоит из двух глав: в первой главе даны основные понятия, а так же содержатся базовые сведения из теории решёток. Кроме того, в первой главе рассмотрено несколько простейших теорем.

Вторая глава представляет собой основную часть данной дипломной работы. Опираясь на работы Гретцера Г., но более подробно, рассмотрены свойства конгруэнций и связь конгруэнций и идеалов в обобщённо булевых решётках (Теоремы 2.1, 2.2, 2.3.). Кроме того реализована основная цель данной дипломной работы: установлена связь между булевыми кольцами и обобщённо булевыми решётками (Основная теорема).

Глава 1

1.1. Упорядоченные множества

Упорядоченным множеством P называется непустое множество, на котором определено бинарное отношение , удовлетворяющее для всех следующим условиям:

1. Рефлексивность: .

2. Антисимметричность. Если и , то .

3. Транзитивность. Если и , то .

Если и , то говорят, что меньше или больше , и пишут или .

Примеры упорядоченных множеств:

1. Множество целых положительных чисел, а означает, что делит .

2. Множество всех действительных функций на отрезке и означает, что для .

Цепью называется упорядоченное множество, на котором для любых имеет место или .

Используя отношение порядка, можно получить графическое представление любого конечного упорядоченного множества P . Изобразим каждый элемент множества P в виде небольшого кружка, располагая x выше y , если . Соединим x и y отрезком. Полученная фигура называется диаграммой упорядоченного множества P .

Примеры диаграмм упорядоченного множества:

1.2. Решётки

Верхней гранью подмножества Х в упорядоченном множестве Р называется элемент a из Р , больший или равный всех x из X .

Точная верхняя грань подмножества X упорядоченного множества P – это такая его верхняя грань, которая меньше любой другой его верхней грани. Обозначается символом sup X и читается «супремум X ».

Согласно аксиоме антисимметричности упорядоченного множества, если точная верхняя грань существует, то она единственна.

Понятия нижней грани и точной нижней грани (которая обозначается inf X и читается «инфинум ») определяются двойственно. Также, согласно аксиоме антисимметричности упорядоченного множества, если точная нижняя грань X существует, то она единственна.

Решёткой называется упорядоченное множество L , в котором любые два элемента x и y имеют точную нижнюю грань, обозначаемую , и точную верхнюю грань, обозначаемую .

Примеры решёток:

Примечание. Любая цепь является решёткой, т.к. совпадает с меньшим, а с большим из элементов .

Наибольший элемент, то есть элемент, больший или равный каждого элемента упорядоченного множества, обозначают 1, а наименьший элемент, то есть меньший или равный каждого элемента упорядоченного множества, обозначают 0.

На решётке можно рассматривать две бинарные операции:

- сложение и

- произведение

Эти операции обладают следующими свойствами:

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

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

3. , ассоциативность;

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

ТЕОРЕМА 1.1. Пусть L - множество с двумя бинарными операциями , обладающими свойствами (1) – (4). Тогда отношение (или ) является порядком на L , а возникающее упорядоченное множество оказывается решёткой, причём: и .

Доказательство. Рефлексивность отношения вытекает из свойства (1). Заметим, что оно является следствием свойства (4):

Если и , то есть и , то в силу свойства (2), получим . Это означает, что отношение антисимметрично.

Если и , то применяя свойство (3), получим: , что доказывает транзитивность отношения .

Применяя свойства (3), (1), (2), получим:

,

.

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

Если и , то используя свойства (1) – (3), имеем:

, т.е. .

По определению точней верхней грани убедимся, что .

Из свойств (2), (4) вытекает, что и .

Если и , то по свойствам (3), (4) получим:

.

Отсюда по свойствам (2) и (4) следует, что

.

Таким образом, .

Пусть L решётка, тогда её наибольший элемент 1 характеризуется одним из свойств:

1. .

2. .

Аналогично характеризуется наименьший элемент :

1.

2. .

1.3. Дистрибутивные решётки

Решётка L называется дистрибутивной , если для любых выполняется:

D1. .

D2. .

В любой решётке тождества D1 и D2 равносильны. Доказательство этого факта содержится в книге [2], стр. 24.

Примеры дистрибутивных решёток:

1. Множество целых положительных чисел, означает, что делит . Это решётка с операциями НОД и НОК.

2. Любая цепь является дистрибутивной решёткой.

ТЕОРЕМА 1.2. Решётка L с 0 и 1 является дистрибутивной тогда и только тогда, когда она не содержит подрешёток вида

Доказательство этой теоремы можно найти в книге [1].

1.4. Обобщённо булевы решётки, булевы решётки

Всюду далее под словом «решётка» понимается произвольная дистрибутивная решётка с 0.

Решётка L называется обобщённой булевой , если для любых элементов и d из L , таких что существует относительное дополнение на интервале , т.е. такой элемент из L , что и .

(Для , , интервал |; для , можно так же определить полуоткрытый интервал |).

ТЕОРЕМА 1.3. (О единственности относительного дополнения в обобщённо булевой решётке). Каждый элемент обобщённо булевой решётки L имеет только одно относительное дополнение на промежутке.

Доказательство. Пусть для элемента существует два относительных дополнения и на интервале . Покажем, что . Так как относительное дополнение элемента на промежутке , то и , так же относительное дополнение элемента на промежутке , то и .

Отсюда

,

таким образом , т.е. любой элемент обобщённой булевой решётки имеет на промежутке только одно относительное дополнение.

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

ТЕОРЕМА 1.4. (О единственности дополнения в булевой решётке). Каждый элемент булевой решётки L имеет только одно дополнение.

Доказательство аналогично доказательству теоремы 1.3.

ТЕОРЕМА 1.5. (О связи обобщённо булевых и булевых решёток).

Любая булева решётка является обобщённо булевой, обратное утверждение не верно.

Доказательство. Действительно, рассмотрим произвольную булеву решётку L . Возьмём элементы a и d из L , такие что . Заметим, что относительным дополнением элемента a до элемента d является элемент , где a ’ – дополнение элемента a в булевой решётке L . Действительно, , кроме того . Отсюда следует, что решётка L является обобщённо булевой.

1.5. Идеалы

Подрешётка I решётки L называется идеалом , если для любых элементов и элемент лежит в I . Идеал I называется собственным, если . Собственный идеал решётки L называется простым , если из того, что и следует или .

Так как непустое пересечение любого числа идеалов снова будет идеалом, то мы можем определить идеал, порождённый множеством H в решётке L , предполагая, что H не совпадает с пустым множеством. Идеал, порождённый множеством H будет обозначаться через ( H ] . Если , то вместо будем писать и называть главным идеалом .

ТЕОРЕМА 1.5. Пусть L – решётка, а H и I – непустые подмножества в L , тогда I является идеалом тогда и только тогда, когда если , то , и если , то .

Доказательство. Пусть I – идеал, тогда влечёт за собой , так как I – подрешётка. Если , то и условия теоремы проверены.

Обратно, пусть I удовлетворяет этим условиям и . Тогда и так как , то , следовательно, I – подрешётка. Наконец, если и , то , значит, и I является идеалом.

Глава 2

2.1. Конгруэнции

Отношение эквивалентности (т.е. рефлексивное, симметричное и транзитивное бинарное отношение) на решётке L называется конгруэнцией на L , если и совместно влекут за собой и (свойство стабильности) . Простейшими примерами являются , , определённые так:

() ; () для всех .

Для обозначим через смежный класс , содержащий элемент , т.е. |

Пусть L – произвольная решётка и . Наименьшую конгруэнцию , такую, что для всех , обозначим через и назовём конгруэнцией, порождённой множеством .

ЛЕММА 2.1. Конгруэнция существует для любого .

Доказательство. Действительно, пусть Ф = | для всех . Так как пересечение в решётке совпадает с теоретико-множественным пересечением, то для всех . Следовательно, Ф =.

В двух случаях мы будем использовать специальные обозначения: если или и - идеал, то вместо мы пишем или соответственно. Конгруэнция вида называется главной; её значение объясняется следующей леммой:

ЛЕММА 2.2. =|.

Доказательство. Пусть , тогда , отсюда . С другой стороны рассмотрим , но тогда . Поэтому и .

Заметим, что - наименьшая конгруэнция, относительно которой , тогда как - наименьшая конгруэнция, такая, чтосодержится в одном смежном классе. Для произвольных решёток о конгруэнции почти ничего не известно. Для дистрибутивных решёток важным является следующее описание конгруэнции :

ТЕОРЕМА 2.1. Пусть - дистрибутивная решётка, и . Тогда и .

Доказательство. Обозначим через Ф бинарное отношение, определённое следующим образом: и .

Покажем, что Ф – отношение эквивалентности:

1) Ф – отношение рефлексивности: x · a = x · a ; x + b = x + b ;

2) Ф – отношение симметричности:

x·a = y·a и x+b = y+b y·a = x·a и y+b = x+b ;

3) Ф – отношение транзитивности.

Пусть x· a = y · a и x + b = y + b и пусть y ·с = z ·с и y + d = z + d . Умножим обе части x · a = y · a на элемент с , получим x · a · c = y · a · c . А обе части y ·с = z ·с умножим на элемент a , получим y · c · a = z · c · a . В силу симметричности x · a · c = y · a · c = z · a · c . Аналогично получаем x + b + d = y + b + d = z + b + d . Таким образом .

Из всего выше обозначенного следует, что Ф – отношение эквивалентности.

Покажем, что Ф сохраняет операции. Если и zL , то ( x + z ) · a = ( x · a ) + ( z · a ) = ( y · a ) + ( z · a ) = ( y + z ) · a и ( x + z )+ b = z +( x + b ) = z +( y + b ) ; следовательно, . Аналогично доказывается, что и, таким образом, Ф – конгруэнция.

Наконец, пусть - произвольная конгруэнция, такая, что , и пусть . Тогда x · a = y · a , x + b = y + b , и . Поэтому вычисляя по модулю , получим

, т.е. , и таким образом, .

СЛЕДСТВИЕ ИЗ ТЕОРЕМЫ 2.1. Пусть I – произвольный идеал дистрибутивной решётки L . Тогда в том и только том случае, когда для некоторого . В частности, идеал I является смежным классом по модулю .

Доказательство. Если , то и элементы x · y · i , i принадлежат идеалу I .

Действительно .

Покажем, что .

Воспользуемся тем, что (*), заметим, что и , поэтому мы можем прибавить к тождеству (*) или , и тождество при этом будет выполняться.

Прибавим : , получим .

Прибавим : , получим .

Отсюда . Таким образом,.

Обратно согласно лемме 2, |

Однако и поэтому |

Если , то откуда

.

Действительно, (**).

Рассмотрим правую часть этого тождества:

Объединим первое и второе слагаемые –

.

Объединим первое и третье слагаемые –

,

таким образом (***)

Заметим, что , поэтому прибавим к обеим частям выражения (***) y :

Но , отсюда .

Следовательно, условие следствия из теоремы 2.1. выполнено для элемента . Наконец, если и , то , откуда и , т.е. является смежным классом.

ТЕОРЕМА 2.2. Пусть L – булева решётка. Тогда отображение является взаимно однозначным соответствием между конгруэнциями и идеалами решётки L . (Под понимаем класс нуля по конгруэнции , под понимаем решётку конгруэнций.)

Доказательство. В силу следствия из теоремы 2.1. это отображение на множество идеалов; таким образом мы должны только доказать, что оно взаимно однозначно, т.е. что смежный класс определяет конгруэнцию . Это утверждение, однако, очевидно. Действительно тогда и только тогда, когда (*), последнее сравнение в свою очередь равносильно сравнению , где с – относительное дополнение элемента в интервале .

Действительно, помножим выражение (*) на с :

, но, а , отсюда .

Таким образом, в том и только том случае, когда .

Примечание. Приведённое доказательство не полностью использует условие, что L – дистрибутивная решётка с дополнениями. Фактически, мы пользовались только тем, что L имеет нуль и является решёткой с относительными дополнениями. Такая решётка называется обобщённой булевой решёткой.

ТЕОРЕМА 2.3 (Хасимото [1952]). Пусть L – произвольная решётка. Для того, чтобы существовало взаимно однозначное соответствие между идеалами и конгруэнциями решётки L , при котором идеал, соответствующий конгруэнции , являлся бы смежным классом по , необходимо и достаточно, чтобы решётка L была обобщённой булевой.

Доказательство. Достаточность следует из доказательства теоремы 2.2. Перейдём к доказательству необходимости.

Идеалом, соответствующим конгруэнции , должен быть (0] ; следовательно, L имеет нуль 0.

Если L содержит диамант , то идеал ( a ] не может быть смежным классом, потому что из следует и . Но , значит, любой смежный класс, содержащий , содержит и , и .

Аналогично, если L содержит пентагон и смежный класс содержит идеал , то и , откуда . Следовательно, этот смежный класс должен содержать и .

Итак, решётка L не содержит подрешёток, изоморфных ни диаманту, ни пентагону. Поэтому, по теореме 1.2., она дистрибутивна.

Пусть и . Согласно следствию из теоремы 2.1., для конгруэнции идеал так же является смежным классом, следовательно, , откуда . Опять применяя следствие из теоремы 2.1. получим, для некоторого . Так как , то и . Следовательно, о полу орого ледствие 4 получим, цииодержать , соответствующим конгруэнции образом мы должны только доказать, ______________ и , т.е. элемент является относительным дополнением элемента в интервале .

2.2. Основная теорема

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

(2) Пусть - булево кольцо. Определим бинарные операции и на , полагая, что и . Тогда - обобщённая булева решётка.

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

(1) Покажем, что - кольцо.

Напомним определение. Кольцо - это непустое множество с заданными на нём двумя бинарными операциями , которые удовлетворяют следующим аксиомам:

1. Коммутативность сложения: выполняется ;

2. Ассоциативность сложения: выполняется ;

3. Существование нуля, т.е. , ;

4. Существование противоположного элемента, т.е. , , ;

5. Ассоциативность умножения: , ;

6. Закон дистрибутивности.

Проверим, выполняются ли аксиомы кольца:

1. Относительным дополнением до элемента будет элемент , а относительным дополнением элемент . В силу того, что , а так же единственности дополнения имеем .

2. Покажем, что .

Рассмотрим все возможные группы вариантов:

1) Пусть , тогда (Далее везде под элементом x будем понимать сумму ).

Аналогично получаем в случаях , , , и . Заметим, что когда один из элементов равен нулю (например, c ) , то получаем тривиальные варианты (a+ b = a + b ).

2) Пусть , а элемент c не сравним с ними. Возможны следующие варианты:

Нетрудно заметить, что во всех этих случаях , кроме того:

если c=a+b , то (a+b)+c=0=a+(b+c) ;

если c =0 , то получаем тривиальный вариант.

Вариант, когда c равен наибольшему элементу решётки d , мы уже рассматривали.

Если c=b , то (a+b)+c=(a+b)+b=a и a+(b+c)=a+(b+b)=a.

Если c=a, то (a+b)+c=(a+b)+a=b и a+(b+c)=a+(b+a)=b .

Аналогично для случаев , , , и .

3) Под элементами нижнего уровня будем понимать элементы , , , , , , , , т.е. те элементы 4-х мерного куба, которые образуют нижний трёхмерный куб.

Под элементами верхнего уровня будем понимать элементы , , , , , , , , т.е. те элементы 4-х мерного куба, которые образуют верхний трёхмерный куб.

Под фразой «элемент верхнего уровня, полученный из элемента нижнего уровня сдвигом по соответствующему ребру» будем понимать элемент верхнего уровня.

Пусть a , b , c несравнимы. Рассмотрим следующие варианты: и .

Пусть . Заметим, что это возможно только в случаях, когда принадлежат нижнему уровню, причём лежат на позициях элементов (рис. 1). Либо a , b остаются на своих позициях, элемент c сдвигается на верхний уровень по соответствующему ребру (рис. 2). Либо элемент a остаётся на своей позиции, элементы b , c сдвигаются на верхний уровень по соответствующему ребру (рис 3).

Нетрудно заметить, что во всех этих случаях .

Пусть , здесь так же .

Таким образом мы рассмотрели все основные группы вариантов расположения элементов a , b , c и во всех этих случаях ассоциативность сложения выполняется.

3. Рассмотрим в решётке элемент , к нему существует относительное дополнение до элемента , т.е. и . Учитывая, что в решётке и , имеем следующее: и . Отсюда .

4. Рассмотрим относительное дополнение элемента до , это элемент . Таким образом: и . Учитывая, что в решётке выполняются тождества и имеем следующее: и . Отсюда .

5. Так как в решётке выполняется ассоциативность , а так же имея , то .

6. Докажем дистрибутивность или что то же самое

(*).

Докажем, что дополнения левой и правой частей выражения (*) до верхней грани совпадают.

Нетрудно заметить, что дополнением правой части выражения (*) до элемента будет являться элемент .

Покажем это:

, по определению относительного дополнения элемента (), где за приняли элемент , а элемент за .

, по определению относительного дополнения элемента () , где за приняли элемент , а элемент за .

Покажем, что и для левой части (*) элемент будет являться относительным дополнением до верхней грани :

, т.к. .

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

Таким образом, для все аксиомы кольца выполняются.

Заметим, что выполняется в силу того, что , а в решётке .

Также выполняется , потому что .

Таким образом, - булево кольцо.

Доказательство (2). Частичную упорядоченность имеем исходя из того, что исходное булево кольцо - частично упорядоченное множество. Кроме того - решётка, т.к. существуют sup(x , y ) и inf(x , y ), заданные соответствующими правилами: и .

Покажем, что решётка дистрибутивна, т.е. что выполняется тождество (*)

Рассмотрим левую часть выражения (*):

.

Рассмотрим правую часть выражения (*):

,

т.о. тождество верно, т.е. решётка является дистрибутивной.

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

Рассмотрим элемент булева кольца (в решётке лежит соответствующий ему элемент), заметим, что

и .

Поэтому элемент будет являться в дистрибутивной решётке относительным дополнением до верхней грани .

Таким образом, будет являться дистрибутивной решёткой с относительными дополнениями (обобщённой булевой).

Библиографический список

1. Гретцер, Г. Общая теория решёток [Текст] / Г. Гретцер. – М.: Мир, 1982.

2. Биркгоф, Г. Теория решёток [Текст] / Г. Биркгоф. – М.: Наука, 1984.

3. Скорняков, Л.А. Элементы алгебры [Текст] / Л.А. Скорняков. – М.: Наука, 1989.

Скачать архив с текстом документа