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

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

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

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

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

Напівґратка

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

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

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

із $a_1⩽a_2$ та $b_1⩽b_2$ випливає $(a_1\vee b_1)⩽(a_2\vee b_2)$ та $(a_1\wedge b_1)⩽(a_2\wedge b_2).$

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

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

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

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

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

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

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

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

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

$a\vee a=a,a\wedge a=a$ (ідемпотентність)

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

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

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

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

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

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

$a\vee b=1,a\wedge b=0.$

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

$a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c),a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$ (дистрибутивність)

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

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

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

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

Модулярна ґратка — для довільного $x⩽b$ виконується $x\vee (a\wedge b)=(x\vee a)\wedge b.$

Властивості

• Для довільного $x⩽b$ виконується $x\vee (a\wedge b)⩽(x\vee a)\wedge b,$

це доводиться обчисленням виразу при $x⩽(a\wedge b)$ та $x⩽̸(a\wedge b)$

Приклади

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

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

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

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

Див. також

• Ґратка з діленням
• Ґратка (геометрія)
• Задачі теорії ґраток

Джерела

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