Перегляд вихідного коду сторінки Ґратка (порядок)

{{Алгебричні структури|lattice}}
[[Файл:Lattice of partitions of an order 4 set.svg|right|thumb|260px|Ґратка [[розбиття множини]] <math>~\{1,2,3,4\}</math> ]]
'''Ґратка'''&nbsp;— [[частково впорядкована множина]], в якій для кожної пари елементів існує [[супремум]] та [[інфімум]].

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

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

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

[[Бінарна операція|Бінарні операції]] '''join''' та '''meet''', позначаються <math> \lor </math> та <math> \land </math> відповідно; очевидно, що вони є [[комутативна операція|комутативними]], [[асоціативна операція|асоціативними]] та [[ідемпотентна операція|ідемпотентними]] операціями.

Обидві операції є [[монотонна функція|монотонними]] по відношенню до порядку, тобто:
: із <math>a_1 \leqslant a_2</math> та <math>b_1 \leqslant b_2</math> випливає <math>(a_1 \lor b_1) \leqslant (a_2 \lor b_2)</math> та <math>(a_1 \land b_1) \leqslant (a_2 \land b_2).</math>

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

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

Тому означення:
* Верхня півґратка&nbsp;— [[частково впорядкована множина]], з [[точна верхня грань|точною верхньою гранню]] (для кожної пари елементів існує супремум)<ref>{{Cite web |url=https://kvmimath.univer.kharkov.ua/doc/Роб_прогр_теорія_множ_філ_19_20.pdf |title=Тема 6. Ґратки. Харківський національний університет імені В.Н. Каразіна |accessdate=18 квітня 2021 |archive-date=18 квітня 2021 |archive-url=https://web.archive.org/web/20210418030827/https://kvmimath.univer.kharkov.ua/doc/Роб_прогр_теорія_множ_філ_19_20.pdf }} {{Webarchive|url=https://web.archive.org/web/20210418030827/https://kvmimath.univer.kharkov.ua/doc/Роб_прогр_теорія_множ_філ_19_20.pdf |date=2021-04-18 }}</ref>.
* Нижня півґратка&nbsp;— [[частково впорядкована множина]], з [[точна нижня грань|точною нижньою гранню]] (для кожної пари елементів існує інфімум).

== Ґратка, як алгебрична структура ==
[[Файл:Lattice of the divisibility of 60.svg|right|thumb|220px|Дистрибутивна ґратка<br/> всіх дільників числа 60, впорядкованих за [[подільність|подільністю]].]]
Ґратка може бути визначена як [[алгебрична структура]] з двома [[бінарна операція|бінарними операціями]] (позначаються <math> \lor </math> та <math> \land </math>), що задовольняють тотожностям<ref>{{Cite web |url=http://www.uuooidata.org/course/es2/LF/Lecture%2012.%20Algebraic%20structures.pdf |title=Алгебрична структура |accessdate=18 квітня 2021 |archive-date=18 квітня 2021 |archive-url=https://web.archive.org/web/20210418030823/http://www.uuooidata.org/course/es2/LF/Lecture%2012.%20Algebraic%20structures.pdf }} {{Webarchive|url=https://web.archive.org/web/20210418030823/http://www.uuooidata.org/course/es2/LF/Lecture%2012.%20Algebraic%20structures.pdf |date=2021-04-18 }}</ref>:
{| cellpadding=5
|-
|<math> a \lor b = b \lor a, </math>
|<math> a \land b = b \land a </math>
| ([[комутативність]])
|-
|<math> a \lor (b \lor c) = (a \lor b) \lor c, </math>
|<math> a \land (b \land c) = (a \land b) \land c </math>
| ([[асоціативність]])
|-
|<math> (a \lor b) \land b = b, </math>
|<math> (a \land b) \lor b = b </math>
| ([[закон поглинання]])
|}
Із закону поглинання слідує не тільки:
: <math>a \lor a = a, \qquad a \land a = a</math> ([[ідемпотентність]])

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

'''<math>\delta</math>-ґратка'''&nbsp;— упорядкована множина, що містить точні межі всіх своїх скінченних і обмежених зліченних підмножин<ref>''Юрачківський А.&nbsp;П.''&nbsp;Начала функціонального аналізу і теорії інтеграла.&nbsp;— К., 2012.&nbsp;— 243 с.</ref>.

'''<math>\sigma</math>-ґратка'''&nbsp;— упорядкована множина, що містить точні межі всіх своїх скінченних зліченних підмножин.

'''Обмежена ґратка'''&nbsp;— ґратка, в якій існує найбільший та [[Найбільший та найменший елемент|найменший елемент]], позначаються <math>~1</math> та <math>~0</math> відповідно. Довільну ґратку можна зробити обмеженою, доповнивши її елементами <math>~1</math> та <math>~0</math>.

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

'''Доповнена ґратка'''&nbsp;— обмежена ґратка, в якій для кожного елемента ''a'' існує '''доповнення''', тобто елемент ''b'' такий, що:
: <math>a \lor b =1, \qquad a \land b = 0.</math>

{{falseredirect|Дистрибутивна ґратка}}
'''[[Дистрибутивна ґратка]]'''&nbsp;— ґратка, що задовольняє властивість:
: <math>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) </math> ([[дистрибутивність]])

[[Булева алгебра (структура)|'''Булева алгебра''']]&nbsp;— доповнена дистрибутивна ґратка.

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

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

'''[[Модулярна ґратка]]'''&nbsp;— для довільного <math>~x \leqslant b</math> виконується <math>x \lor (a \land b) = (x \lor a) \land b.</math>

== Властивості ==
* Для довільного <math>~x \leqslant b</math> виконується <math>x \lor (a \land b) \leqslant (x \lor a) \land b,</math>
: це доводиться обчисленням виразу при <math>x \leqslant (a \land b)</math> та <math>x \not\leqslant (a \land b)</math>

== Приклади ==
[[Файл:Hasse diagram of powerset of 3.svg|right|thumb|240px|Діаграма впорядкування за включенням підмножин множини з трьох елементів.]]

# множина всіх [[підмножина|підмножин]] даної множини, впорядкована за включенням; <math>\sup\{ \{x\}, \{x,y\} \} = \{x,y\}, \inf\{ \{x\}, \{x,y\} \} = \{x\}, sup\{ \{x\}, \{y,z\} \} = \{x,y,z\}, \inf\{ \{x\}, \{y,z\} \} = \emptyset</math>;
# будь-яка [[лінійно впорядкована множина]]; причому якщо <math>a\leqslant b</math>, то <math>\sup(a,b) = b, \inf(a,b) = a</math>;
# множина всіх підпросторів [[Векторний простір|векторного простору]], упорядкованих за включенням, де <math>\inf</math>&nbsp;— перетин, а <math>\sup</math>&nbsp;— сума відповідних підпросторів;
# множина всіх невід'ємних [[Ціле число|цілих чисел]], упорядкованих за подільністю: <math>a\leqslant b</math>, якщо <math>b = ac</math> для деякого <math>c</math>. Тут <math>\sup</math>&nbsp;— [[найменше спільне кратне]], а <math>\inf</math>&nbsp;— [[найбільший спільний дільник]] даних чисел;
# [[Дійсне число|дійсні]] [[Функція (математика)|функції]], визначені на проміжку [0, 1], впорядковані умовою <math>f\leqslant g</math>, якщо <math>f(t)\leqslant g(t)</math> для всіх <math>t\in [0,1]</math>. тут
:: <math>\sup(f,g) = u</math>, де <math>u(t) =\max (f(t),g(t))</math>.

== Частковий порядок ==
На ґратці також визначене [[бінарне відношення]] ≤, яке має назву [[відношення нестрогого порядку]] та задовільняє умовам:
* 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''.

== Теорема Стоуна ==
{{main|Теорема Стоуна про представлення булевих алгебр}}
* Ґратка є дистрибутивною [[Тоді й лише тоді|тоді і тільки тоді]], коли вона [[ізоморфізм (математика)|ізоморфна]] деякому [[кільце множин|кільцю множин]].
* Ґратка є булевою алгеброю тоді і тільки тоді, коли вона ізоморфна деякому [[поле множин|полю множин]].

== Примітки ==
{{примітки}}

==Див. також==
* [[Ґратка з діленням]]
* [[Ґратка (геометрія)]]
* [[Задачі теорії ґраток]]

== Джерела ==
* {{springer|title=Lattice-ordered group|id=p/l057670}}
* {{Mathworld|urlname=Lattice|title=Lattice}}
* {{Биркгоф.Теория решёток}}
* ''Скорняков Л. А.'' Элементы теории структур.&nbsp;— М., 1970.
* ''Гретцер Г.'' Общая теория решёток.&nbsp;— М.: Мир, 1982.&nbsp;— 456 с.

{{Теорія порядку|state=expanded}}
{{Портали|Математика}}
[[Категорія:Теорія ґраток|*]]
[[Категорія:Математичні структури]]