Ґратка (порядок)
Алгебричні структури |
---|
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b2/Lattice_of_partitions_of_an_order_4_set.svg/260px-Lattice_of_partitions_of_an_order_4_set.svg.png)
Ґратка — частково впорядкована множина, в якій для кожної пари елементів існує супремум та інфімум.
«Ґратко-подібними» структурами є напівґратки, ґратки, булеві алгебри, алгебри Гейтінга.
Всіх їх можна визначити і як алгебраїчні структури, тому теорія ґраток є частиною як теорії порядку, так і універсальної алгебри.
Напівґратка — частково впорядкована множина, в якій визначена операція join (join-напівґратка) або операція meet (meet-напівґратка).
Бінарні операції join та meet, позначаються та відповідно; очевидно, що вони є комутативними, асоціативними та ідемпотентними операціями.
Обидві операції є монотонними по відношенню до порядку, тобто:
- із та випливає та
Ґратка є одночасно join-напівґраткою та meet-напівґраткою.
Операцію join також можна визначити як бінарну операцію супремум(x, y), а операцію meet — інфімум(x, y). В такому разі join-напівгратку називають верхньою піврешіткою, а meet-напівгратку відповідно нижньою.[джерело?]
Тому означення:
- Верхня півґратка — частково впорядкована множина, з точною верхньою гранню (для кожної пари елементів існує супремум)[1].
- Нижня півґратка — частково впорядкована множина, з точною нижньою гранню (для кожної пари елементів існує інфімум).
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/51/Lattice_of_the_divisibility_of_60.svg/220px-Lattice_of_the_divisibility_of_60.svg.png)
всіх дільників числа 60, впорядкованих за подільністю.
Ґратка може бути визначена як алгебрична структура з двома бінарними операціями (позначаються та ), що задовольняють тотожностям[2]:
(комутативність) | ||
(асоціативність) | ||
(закон поглинання) |
Із закону поглинання слідує не тільки:
але і показується дуальність операцій та , що обумовлено дуальністю супремума та інфімума.
-ґратка — упорядкована множина, що містить точні межі всіх своїх скінченних і обмежених зліченних підмножин[3].
-ґратка — упорядкована множина, що містить точні межі всіх своїх скінченних зліченних підмножин.
Обмежена ґратка — ґратка, в якій існує найбільший та найменший елемент, позначаються та відповідно. Довільну ґратку можна зробити обмеженою, доповнивши її елементами та .
Очевидно, що всі скінченні ґратки є обмеженими.
Доповнена ґратка — обмежена ґратка, в якій для кожного елемента a існує доповнення, тобто елемент b такий, що:
Дистрибутивна ґратка — ґратка, що задовольняє властивість:
Булева алгебра — доповнена дистрибутивна ґратка.
Дистрибутивна напівґратка
Напівґратка теж може бути дистрибутивною: meet-напівґратка є дистрибутивною, якщо для всіх a, b, та x:
- Якщо a ∧ b ≤ x тоді існують a' та b' такі, що a ≤ a' , b ≤ b' та x = a' ∧ b' .
Модулярна ґратка — для довільного виконується
- Для довільного виконується
- це доводиться обчисленням виразу при та
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Hasse_diagram_of_powerset_of_3.svg/240px-Hasse_diagram_of_powerset_of_3.svg.png)
- множина всіх підмножин даної множини, впорядкована за включенням; ;
- будь-яка лінійно впорядкована множина; причому якщо , то ;
- множина всіх підпросторів векторного простору, упорядкованих за включенням, де — перетин, а — сума відповідних підпросторів;
- множина всіх невід'ємних цілих чисел, упорядкованих за подільністю: , якщо для деякого . Тут — найменше спільне кратне, а — найбільший спільний дільник даних чисел;
- дійсні функції, визначені на проміжку [0, 1], впорядковані умовою , якщо для всіх . тут
- , де .
На ґратці також визначене бінарне відношення ≤, яке має назву відношення нестрогого порядку та задовільняє умовам:
- x≤x (рефлексивність)
- якщо x≤y та y≤x, то x=y (антисиметричність)
- якщо x≤y та y≤z, то x≤z (транзитивність)
Зв'язок між різними визначеннями встановлюється формулами:
- a ∨ b = sup{a, b}, a ∧ b = inf{a, b}.
Та виконанням умови: якщо a ≤ b, то: a ∧ b = a, a ∨ b = b.
- Ґратка є дистрибутивною тоді і тільки тоді, коли вона ізоморфна деякому кільцю множин.
- Ґратка є булевою алгеброю тоді і тільки тоді, коли вона ізоморфна деякому полю множин.
- ↑ Тема 6. Ґратки. Харківський національний університет імені В.Н. Каразіна (PDF). Архів оригіналу (PDF) за 18 квітня 2021. Процитовано 18 квітня 2021.
- ↑ Алгебрична структура (PDF). Архів оригіналу (PDF) за 18 квітня 2021. Процитовано 18 квітня 2021.
- ↑ Юрачківський А. П. Начала функціонального аналізу і теорії інтеграла. — К., 2012. — 243 с.
- Hazewinkel, Michiel, ред. (2001), group Lattice-ordered group, Математична енциклопедія, Springer, ISBN 978-1-55608-010-4
- Weisstein, Eric W. Lattice(англ.) на сайті Wolfram MathWorld.
- Биркгоф Г. Теория решёток / пер. с англ. В. Н. Салий ; под ред. Л. А. Скорнякова. — 3-е изд. — Москва : Наука, 1984. — 568 с.(рос.)
- Скорняков Л. А. Элементы теории структур. — М., 1970.
- Гретцер Г. Общая теория решёток. — М.: Мир, 1982. — 456 с.