Дипломная работа на тему "Обобщённо булевы решетки"
Главная → Математика → Обобщённо булевы решетки
Страшно ошибиться с выбором, кому доверить написание своей дипломной /курсовой работы/диссертации?
МЫ ЗАМОРОЗИЛИ ЦЕНЫ + СКИДКИ!
Для вас:
- только проверенные авторы;
- работа со всеми системами антиплагиата (до 98%);
- соблюдение сроков;
- бесплатные доработки;
- ведение до защиты.
***
Дипломные - с ВЫГОДОЙ 15% - промокод dpl15
***
Курсовые с ВЫГОДОЙ 10% - промокод kyr10
Узнать стоимость и оформить заказ
Профессиональная помощь с диссертацией - кликайте сюда!
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
Вятский государственный гуманитарный университет
Математический факультет
Кафедра алгебры и геометрии
Выпускная квалификационная работа
Обобщенно булевы решетки
Выполнил:
студент V курса математического факультета
Онучин Андрей Владимирович
Научный руководитель:
к. ф.-м. н., доцент кафедры алгебры и геометрии ВятГГУ
Чермных Василий Владимирович
Рецензент:
д. ф.-м. н., профессор, зав. кафедрой алгебры и геометрии ВятГГУ
Вечтомов Евгений Михайлович
Работа допущена к защите в государственной аттестационной комиссии
Заказать дипломную - rosdiplomnaya.com
Специальный банк готовых оригинальных дипломных работ предлагает вам приобрести любые работы по требуемой вам теме. Мастерское выполнение дипломных работ на заказ в Новокузнецке и в других городах России.
«___» __________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.
--------------------------------------------------
---------------------------------------------------------
|
--------------------------------------------------------- --------------------------------------------------
Примеры диаграмм упорядоченного множества:
Верхней гранью подмножества Х в упорядоченном множестве Р называется элемент 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.
.
Решётка 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 является обобщённо булевой.
Подрешётка I решётки L называется идеалом если для любых элементов и
элемент
лежит в I. Идеал I называется собственным, если
. Собственный идеал решётки L называется простым, если из того, что
и
следует
или
.
Так как непустое пересечение любого числа идеалов снова будет идеалом, то мы можем определить идеал, порождённый множеством H в решётке L, предполагая, что H не совпадает с пустым множеством. Идеал, порождённый множеством H будет обозначаться через (H]. Если , то вместо
будем писать
и называть
главным идеалом.
ТЕОРЕМА 1.5. Пусть L – решётка, а H и I – непустые подмножества в L, тогда I является идеалом тогда и только тогда, когда если , то
, и если
, то
.
Доказательство. Пусть I – идеал, тогда влечёт за собой
, так как I – подрешётка. Если
, то
и условия теоремы проверены.
Обратно, пусть I удовлетворяет этим условиям и . Тогда
и так как
, то
, следовательно, I – подрешётка. Наконец, если
и
, то
, значит,
и I является идеалом.
Отношение эквивалентности (т. е. рефлексивное, симметричное и транзитивное бинарное отношение) на решётке 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. Таким образом
.
Из всего выше обозначенного следует, что Ф – отношение эквивалентности.
Покажем, что Ф сохраняет операции. Если и z
L, то (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. это отображение на множество идеалов; таким образом мы должны только доказать, что оно взаимно однозначно, т. е. что смежный класс
определяет конгруэнцию
Здесь опубликована для ознакомления часть работы "Обобщённо булевы решетки". Эта работа найдена в открытых источниках Интернет. А это значит, что если попытаться её защитить, то она 100% не пройдёт проверку российских ВУЗов на плагиат и её не примет ваш преподаватель!