Федеральне агентство з освіти
Державна освітня установа
вищої професійної освіти
Вятский державний гуманітарний університет
Математичний факультет
Кафедра алгебри та геометрії
Випускна кваліфікаційна робота
Узагальнено булеві решітки
Виконав:
студент V курсу математичного факультету
Онучин Андрій Володимирович
Науковий керівник:
к.ф.-м.н., доцент кафедри алгебри та геометрії ВятГГУ
Чермний Василь Володимирович
Рецензент:
д.ф.-м.н., професор, зав. кафедрою алгебри і геометрії ВятГГУ
Вечтомов Євген Михайлович
Робота допущена до захисту в державної атестаційної комісії
«___» __________2005 Р. Зав. кафедрою Є.М. Вечтомов
«___»__________ 2005 Декан факультету В.І. Варанкіна
Кіров
2005
Зміст
Вступ 3
Глава 1 Квітня
1.1. Впорядковані множини 4
1.2. Грати 5
1.3. Дистрибутивні решітки 7
1.4. Узагальнені булеві решітки, булеві грати 8
1.5. Ідеали 9
Глава 11 лютого
2.1. Конгруенції 11
2.2. Основна теорема 17
Бібліографічний список 27
Введення
Булева грати є класичний математичний об'єкт, який почав інтенсивно вивчатися в роботах М. Стоуна 30-ті роки 20-го століття, розширенням цього поняття до узагальнено булевих решіток займалися Г. Гретцер і Е. Шмідт у своїх працях кінця 50-х років.
Мета даної роботи: встановлення взаємно однозначної відповідності між конгруенції та ідеалами в узагальнено булевих гратах. (Для булевих решіток це положення доведено в книзі [2], крім того, сформульовано в книзі [3] в якості вправ). А також - встановлення зв'язку між узагальнено булевими гратами і булевими кільцями.
Дана дипломна робота складається з двох глав: в першому розділі дано основні поняття, а так само містяться базові відомості з теорії грат. Крім того, в першому розділі розглянуто кілька найпростіших теорем.
Другий розділ представляє собою основну частину даної дипломної роботи. Спираючись на роботи Гретцера Г., але більш докладно, розглянуті властивості конгруенції і зв'язок конгруенції та ідеалів в узагальнено булевих гратах (Теореми 2.1, 2.2, 2.3.). Крім того реалізована основна мета даної дипломної роботи: встановлено зв'язок між булевими кільцями і узагальнено булевими гратами (Основна теорема).
Глава 1
1.1. Впорядковані множини
Впорядкованим безліччю P називається непорожня безліч, на якому визначено бінарне відношення , Що задовольнить для всіх таким умовам:
1. Рефлексивність: .
2. Антисиметричність. Якщо і , То .
3. Транзитивність. Якщо і , То .
Якщо і , То говорять, що менше або більше , І пишуть або .
Приклади впорядкованих множин:
Безліч цілих позитивних чисел, а означає, що ділить .
Безліч всіх дійсних функцій на відрізку і означає, що для .
Ланцюгом називається упорядкований безліч, на якому для будь-яких має місце або .
Використовуючи відношення порядку, можна отримати графічне представлення будь-якого кінцевого упорядкованої множини 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 називається дистрибутивної, якщо для будь-яких виконується:
D 1. .
D 2. .
У будь решітці тотожності D 1 і D 2 рівносильні. Доказ цього факту міститься в книзі [2], стор 24.
Приклади дистрибутивних решіток:
Безліч цілих позитивних чисел, означає, що ділить . Це решітка з операціями НОД і НОК.
Будь ланцюг є дистрибутивної гратами.
ТЕОРЕМА 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. Таким чином .
З усього вище зазначеного випливає, що Ф - відношення еквівалентності.
Покажемо, що Ф зберігає операції. Якщо і 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. (Під розуміємо клас нуля по конгруенції , Під розуміємо грати конгруенції.)
Дійсно, множитимемо вираз (*) на з:
, Але , А , Звідси .
Таким чином, в тому і тільки тому випадку, коли .
Примітка. Наведене доказ не повністю використовує умова, що L - Дистрибутивная решітка з доповненнями. Фактично, ми користувалися тільки тим, що L має нуль і є гратами з відносними доповненнями. Такі грати називається узагальненої булевой гратами.
ТЕОРЕМА 2.3 (Хасімото [1952]). Нехай L - довільна решітка. Для того, щоб існувало взаємно однозначна відповідність між ідеалами і конгруенції решітки L, при якому ідеал, відповідний конгруенції , Був би суміжних класом по , Необхідно і достатньо, щоб грати L була узагальненої булевої.
Ідеалом, відповідним конгруенції , Повинен бути (0]; отже, L має нуль 0.
Аналогічно, якщо L містить пентагон і суміжний клас містить ідеал , То і , Звідки . Отже, цей суміжний клас повинен містити і .
Отже, грати L не містить підграток, ізоморфних ні діаманти, ні Пентагону. Тому, по теоремі 1.2., Вона дистрибутивна.
Нехай і . Згідно слідству з теореми 2.1., Для конгруенції ідеал так само є суміжним класом, отже, , Звідки . Знову застосовуючи наслідок з теореми 2.1. отримаємо, для деякого . Так як , То і . Отже, про підлозі орого ледствии 4 отримали, цііодержать, відповідним конгруенції чином ми повинні тільки довести, і , Тобто елемент є відносним доповненням елемента в інтервалі .
2.2. Основна теорема
Нехай - Узагальнена булева решітка. Визначимо бінарні операції на B, вважаючи і позначаючи через відносне доповнення елемента в інтервалі . Тоді - Булево кільце, тобто (Асоціативне) кільце, яке задовольняє тотожність (А отже і тождествам , ).
Нехай - Булево кільце. Визначимо бінарні операції і на , Вважаючи, що і . Тоді - Узагальнена булева решітка.
Доказ.
Покажемо, що - Кільце.
Нагадаємо визначення. Кільце - Це непорожня множина із заданими на ньому двома бінарними операціями , Які задовольняють наступним аксіомам:
Комутативність складання: виконується ;
Асоціативність складання: виконується ;
Існування нуля, тобто , ;
Існування протилежного елемента, тобто , , ;
Асоціативність множення: , ;
Закон дистрибутивності.
Перевіримо, чи виконуються аксіоми кільця:
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 непорівнянні. Розглянемо наступні варіанти: і .
Неважко помітити, що у всіх цих випадках .
Нехай , Тут так само .
Таким чином ми розглянули всі основні групи варіантів розташування елементів a, b, c і у всіх цих випадках асоціативність складання виконується.
3. Розглянемо в решітці елемент , До нього існує відносне доповнення до елемента , Тобто і . Враховуючи, що в решітці і , Маємо наступне: і . Звідси .
4. Розглянемо відносне доповнення елемента до , Це елемент . Таким чином: і . Враховуючи, що в решітці виконуються тотожності і маємо наступне: і . Звідси .
5. Так як в решітці виконується асоціативність , А так само маючи , То .
6. Доведемо дистрибутивність або що те ж саме
(*).
Доведемо, що доповнення лівої і правої частин виразу (*) до верхньої межі збігаються.
Неважко помітити, що доповненням правій частині виразу (*) до елемента буде елемент .
Покажемо це:
, За визначенням відносного додатки елемента ( ), Де за взяли елемент , А елемент за .
, За визначенням відносного додатки елемента ( ), Де за взяли елемент , А елемент за .
Покажемо, що і для лівої частини (*) елемент буде відносним доповненням до верхньої межі :
, Тому що .
Ми показали, що доповнення елементів і до верхньої межі збігаються, отже, в силу єдиності додатки . А значить і , Тобто дистрибутивність доведена.
Таким чином, для всі аксіоми кільця виконуються.
Зауважимо, що виконується в силу того, що , А в гратах .
Також виконується , Тому що .
Таким чином, - Булево кільце.
Доказ (2). Часткову впорядкованість маємо виходячи з того, що вихідне булево кільце - Частково упорядкований безліч. Крім того - Грати, тому що існують sup (x, y) і inf (x, y), задані відповідними правилами: і .
Покажемо, що грати дистрибутивно, тобто що виконується тотожність (*)
Розглянемо ліву частину виразу (*):
.
Розглянемо праву частину виразу (*):
,
т.ч. тотожність вірно, тобто решітка є дистрибутивної.
Покажемо, що у кожного елемента в дистрибутивної решітці є відносне доповнення. Для цього розглянемо довільні елементи , Але вони так само повинні бути елементами решітки , Отже, в ній повинні лежати і , Яким в кільці відповідають .
Розглянемо елемент булева кільця (В решітці лежить відповідний йому елемент), зауважимо, що
і .
Тому елемент буде в дистрибутивної решітці відносним доповненням до верхньої межі .
Таким чином, буде дистрибутивної гратами з відносними доповненнями (узагальненої булевої).
Бібліографічний список
Гретцер, Г. Загальна теорія решіток [Текст] / Г. Гретцер. - М.: Мир, 1982.
Біркгоф, Г. Теорія решіток [Текст] / Г. Біркгоф. - М.: Наука, 1984.
Кушнірів, Л.А. Елементи алгебри [Текст] / Л.А. Кушнірів. - М.: Наука, 1989.