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

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

Ґратка розбиття множини ${\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.

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

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

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