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

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

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

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

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

Напівґратка

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

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

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

із $a_1 \le a_2$ та $b_1 \le b_2$ випливає $(a_1 \lor b_1) \le (a_2 \lor b_2)$ та $(a_1 \land b_1) \le (a_2 \land b_2).$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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' and b' такі, що a ≤ a' , b ≤ b' та x = a' ∧ b' .

Модулярна ґратка — для довільного $~x \le b$ виконується $x \or (a \and b) = (x \or a) \land b.$

Властивості

• Для довільного $~x \le b$ виконується $x \or (a \and b) \le (x \or a) \land b,$

доводиться обчисленням виразу при: $x \le (a \and b)$ та $x \not\le (a \and b)$

Приклади

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

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

$\sup(f,g) = u$, де $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.

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

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

Джерела

• Биркгоф Г. (1984). Теория решёток. Москва: Наука. с. 568. 
• Скорняков Л. А. Элементы теории структур. — М., 1970.
• Гретцер Г. Общая теория решёток. — М.: Мир, 1982. — 456 с.