Ґратка (порядок)

Ґратка — частково впорядкована множина, в якій для кожної пари елементів існує супремум та інфімум.

Ґратка розбиття множини ${\displaystyle ~\{1,2,3,4\}}$

«Ґратко-подібними» структурами є напівґратки, ґратки, булеві алгебри, алгебри Гейтінга.

Всіх їх можна визначити і як алгебраїчні структури, тому теорія ґраток є частиною як теорії порядку, так і універсальної алгебри.

Напівґратка

Напівґратка — частково впорядкована множина, в якій визначена операція join (join-напівґратка) або операція meet (meet-напівґратка).

Бінарні операції join та meet, позначаються ${\displaystyle \lor }$ та ${\displaystyle \land }$ відповідно; очевидно, що вони є комутативними, асоціативними та ідемпотентними операціями.

Обидві операції є монотонними по відношенню до порядку, тобто:

із ${\displaystyle a_{1}\leqslant a_{2}}$ та ${\displaystyle b_{1}\leqslant b_{2}}$ випливає ${\displaystyle (a_{1}\lor b_{1})\leqslant (a_{2}\lor b_{2})}$ та ${\displaystyle (a_{1}\land b_{1})\leqslant (a_{2}\land b_{2}).}$

Ґратка є одночасно join-напівґраткою та meet-напівґраткою.

Операцію join також можна визначити як бінарну операцію супремум(x, y), а операцію meet — інфімум(x, y). В такому разі join-напівгратку називають верхньою піврешіткою, а meet-напівгратку відповідно нижньою.^{[джерело?]}

Тому означення:

• Верхня півґратка — частково впорядкована множина, з точною верхньою гранню (для кожної пари елементів існує супремум)^[1].
• Нижня півґратка — частково впорядкована множина, з точною нижньою гранню (для кожної пари елементів існує інфімум).

Ґратка, як алгебрична структура

Дистрибутивна ґратка
всіх дільників числа 60, впорядкованих за подільністю.

Ґратка може бути визначена як алгебрична структура з двома бінарними операціями (позначаються ${\displaystyle \lor }$ та ${\displaystyle \land }$), що задовольняють тотожностям^[2]:

${\displaystyle a\lor b=b\lor a,}$	${\displaystyle a\land b=b\land a}$	(комутативність)
${\displaystyle a\lor (b\lor c)=(a\lor b)\lor c,}$	${\displaystyle a\land (b\land c)=(a\land b)\land c}$	(асоціативність)
${\displaystyle (a\lor b)\land b=b,}$	${\displaystyle (a\land b)\lor b=b}$	(закон поглинання)

Із закону поглинання слідує не тільки:

${\displaystyle a\lor a=a,\qquad a\land a=a}$ (ідемпотентність)

але і показується дуальність операцій ${\displaystyle \lor }$ та ${\displaystyle \land }$, що обумовлено дуальністю супремума та інфімума.

${\displaystyle \delta }$-ґратка — упорядкована множина, що містить точні межі всіх своїх скінченних і обмежених зліченних підмножин^[3].

${\displaystyle \sigma }$-ґратка — упорядкована множина, що містить точні межі всіх своїх скінченних зліченних підмножин.

Обмежена ґратка — ґратка, в якій існує найбільший та найменший елемент, позначаються ${\displaystyle ~1}$ та ${\displaystyle ~0}$ відповідно. Довільну ґратку можна зробити обмеженою, доповнивши її елементами ${\displaystyle ~1}$ та ${\displaystyle ~0}$.

Очевидно, що всі скінченні ґратки є обмеженими.

Доповнена ґратка — обмежена ґратка, в якій для кожного елемента a існує доповнення, тобто елемент b такий, що:

${\displaystyle a\lor b=1,\qquad a\land b=0.}$

Сюди перенаправляється запит «Дистрибутивна ґратка». На цю тему потрібна окрема стаття.

Дистрибутивна ґратка — ґратка, що задовольняє властивість:

${\displaystyle a\lor (b\land c)=(a\lor b)\land (a\lor c),\qquad a\land (b\lor c)=(a\land b)\lor (a\land c)}$ (дистрибутивність)

Булева алгебра — доповнена дистрибутивна ґратка.

Дистрибутивна напівґратка

Напівґратка теж може бути дистрибутивною: meet-напівґратка є дистрибутивною, якщо для всіх a, b, та x:

Якщо a ∧ b ≤ x тоді існують a' та b' такі, що a ≤ a' , b ≤ b' та x = a' ∧ b' .

Модулярна ґратка — для довільного ${\displaystyle ~x\leqslant b}$ виконується ${\displaystyle x\lor (a\land b)=(x\lor a)\land b.}$

Властивості

• Для довільного ${\displaystyle ~x\leqslant b}$ виконується ${\displaystyle x\lor (a\land b)\leqslant (x\lor a)\land b,}$

це доводиться обчисленням виразу при ${\displaystyle x\leqslant (a\land b)}$ та ${\displaystyle x\not \leqslant (a\land b)}$

Приклади

Діаграма впорядкування за включенням підмножин множини з трьох елементів.

1. множина всіх підмножин даної множини, впорядкована за включенням; ${\displaystyle \sup\{\{x\},\{x,y\}\}=\{x,y\},\inf\{\{x\},\{x,y\}\}=\{x\},sup\{\{x\},\{y,z\}\}=\{x,y,z\},\inf\{\{x\},\{y,z\}\}=\emptyset }$;
2. будь-яка лінійно впорядкована множина; причому якщо ${\displaystyle a\leqslant b}$, то ${\displaystyle \sup(a,b)=b,\inf(a,b)=a}$;
3. множина всіх підпросторів векторного простору, упорядкованих за включенням, де ${\displaystyle \inf }$ — перетин, а ${\displaystyle \sup }$ — сума відповідних підпросторів;
4. множина всіх невід'ємних цілих чисел, упорядкованих за подільністю: ${\displaystyle a\leqslant b}$, якщо ${\displaystyle b=ac}$ для деякого ${\displaystyle c}$. Тут ${\displaystyle \sup }$ — найменше спільне кратне, а ${\displaystyle \inf }$ — найбільший спільний дільник даних чисел;
5. дійсні функції, визначені на проміжку [0, 1], впорядковані умовою ${\displaystyle f\leqslant g}$, якщо ${\displaystyle f(t)\leqslant g(t)}$ для всіх ${\displaystyle t\in [0,1]}$. тут

${\displaystyle \sup(f,g)=u}$, де ${\displaystyle u(t)=\max(f(t),g(t))}$.

Частковий порядок

На ґратці також визначене бінарне відношення ≤, яке має назву відношення нестрогого порядку та задовільняє умовам:

• 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.

Теорема Стоуна

Докладніше: Теорема Стоуна про представлення булевих алгебр

• Ґратка є дистрибутивною тоді і тільки тоді, коли вона ізоморфна деякому кільцю множин.
• Ґратка є булевою алгеброю тоді і тільки тоді, коли вона ізоморфна деякому полю множин.

Примітки

1. Тема 6. Ґратки. Харківський національний університет імені В.Н. Каразіна (PDF). Архів оригіналу (PDF) за 18 квітня 2021. Процитовано 18 квітня 2021. [Архівовано 2021-04-18 у Wayback Machine.]
2. Алгебрична структура (PDF). Архів оригіналу (PDF) за 18 квітня 2021. Процитовано 18 квітня 2021. [Архівовано 2021-04-18 у Wayback Machine.]
3. Юрачківський А. П. Начала функціонального аналізу і теорії інтеграла. — К., 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 с.