Ґратка — частково впорядкована множина, в якій для кожної пари елементів існує супремум та інфімум.
«Ґратко-подібними» структурами є напівґратки, ґратки, булеві алгебри, алгебри Гейтінга.
Всіх їх можна визначити і як алгебраїчні структури, тому теорія ґраток є частиною як теорії порядку, так і універсальної алгебри.
Напівґратка
Напівґратка — частково впорядкована множина, в якій визначена операція join (join-напівґратка) або операція meet (meet-напівґратка).
Бінарні операції join та meet, позначаються та відповідно; очевидно, що вони є комутативними, асоціативними та ідемпотентними операціями.
Обидві операції є монотонними по відношенню до порядку, тобто:
- із та випливає та
Ґратка є одночасно join-напівґраткою та meet-напівґраткою.
Операцію join також можна визначити як бінарну операцію супремум(x, y), а операцію meet — інфімум(x, y). В такому разі join-напівгратку називають верхньою піврешіткою, а meet-напівгратку відповідно нижньою.[]
Тому означення:
- Верхня півґратка — частково впорядкована множина, з точною верхньою гранню (для кожної пари елементів існує супремум).
- Нижня півґратка — частково впорядкована множина, з точною нижньою гранню (для кожної пари елементів існує інфімум).
Ґратка, як алгебрична структура
Ґратка може бути визначена як алгебрична структура з двома бінарними операціями (позначаються та ), що задовольняють тотожностям:
(комутативність) | ||
(асоціативність) | ||
(закон поглинання) |
Із закону поглинання слідує не тільки:
але і показується дуальність операцій та , що обумовлено дуальністю супремума та інфімума.
-ґратка — упорядкована множина, що містить точні межі всіх своїх скінченних і обмежених зліченних підмножин.
-ґратка — упорядкована множина, що містить точні межі всіх своїх скінченних зліченних підмножин.
Обмежена ґратка — ґратка, в якій існує найбільший та найменший елемент, позначаються та відповідно. Довільну ґратку можна зробити обмеженою, доповнивши її елементами та .
Очевидно, що всі скінченні ґратки є обмеженими.
Доповнена ґратка — обмежена ґратка, в якій для кожного елемента a існує доповнення, тобто елемент b такий, що:
Дистрибутивна ґратка — ґратка, що задовольняє властивість:
Булева алгебра — доповнена дистрибутивна ґратка.
Дистрибутивна напівґратка
Напівґратка теж може бути дистрибутивною: meet-напівґратка є дистрибутивною, якщо для всіх a, b, та x:
- Якщо a ∧ b ≤ x тоді існують a' та b' такі, що a ≤ a' , b ≤ b' та x = a' ∧ b' .
Модулярна ґратка — для довільного виконується
Властивості
- Для довільного виконується
- це доводиться обчисленням виразу при та
Приклади
- множина всіх підмножин даної множини, впорядкована за включенням; ;
- будь-яка лінійно впорядкована множина; причому якщо , то ;
- множина всіх підпросторів векторного простору, упорядкованих за включенням, де — перетин, а — сума відповідних підпросторів;
- множина всіх невід'ємних цілих чисел, упорядкованих за подільністю: , якщо для деякого . Тут — найменше спільне кратне, а — найбільший спільний дільник даних чисел;
- дійсні функції, визначені на проміжку [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.
Теорема Стоуна
- Ґратка є дистрибутивною тоді і тільки тоді, коли вона ізоморфна деякому кільцю множин.
- Ґратка є булевою алгеброю тоді і тільки тоді, коли вона ізоморфна деякому полю множин.
Примітки
Див. також
- Ґратка з діленням
- Ґратка (геометрія)
- (Задачі теорії ґраток)
Джерела
- Hazewinkel, Michiel, ред. (2001), Lattice-ordered group, Математична енциклопедія, , ISBN
- Weisstein, Eric W. Lattice(англ.) на сайті Wolfram MathWorld.
- Биркгоф Г. Теория решёток / пер. с англ. В. Н. Салий ; под ред. Л. А. Скорнякова. — 3-е изд. — Москва : Наука, 1984. — 568 с.(рос.)
- Скорняков Л. А. Элементы теории структур. — М., 1970.
- Гретцер Г. Общая теория решёток. — М.: Мир, 1982. — 456 с.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет