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

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Дистрибутивна ґратка)
Перейти до навігації Перейти до пошуку
Ґратка розбиття множини

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

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

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

Напівґратка

[ред. | ред. код]

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

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

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

із та випливає та

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

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

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

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

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

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

(комутативність)
(асоціативність)
(закон поглинання)

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

(ідемпотентність)

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

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

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

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

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

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

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

(дистрибутивність)

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

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

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

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

Модулярна ґратка — для довільного виконується

Властивості

[ред. | ред. код]
  • Для довільного виконується
це доводиться обчисленням виразу при та

Приклади

[ред. | ред. код]
Діаграма впорядкування за включенням підмножин множини з трьох елементів.
  1. множина всіх підмножин даної множини, впорядкована за включенням; ;
  2. будь-яка лінійно впорядкована множина; причому якщо , то ;
  3. множина всіх підпросторів векторного простору, упорядкованих за включенням, де  — перетин, а  — сума відповідних підпросторів;
  4. множина всіх невід'ємних цілих чисел, упорядкованих за подільністю: , якщо для деякого . Тут  — найменше спільне кратне, а  — найбільший спільний дільник даних чисел;
  5. дійсні функції, визначені на проміжку [0, 1], впорядковані умовою , якщо для всіх . тут
, де .

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

[ред. | ред. код]

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

Зв'язок між різними визначеннями встановлюється формулами:

ab = sup{a, b}, ab = inf{a, b}.

Та виконанням умови: якщо ab, то: a ∧ b = a, ab = b.

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

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. Тема 6. Ґратки. Харківський національний університет імені В.Н. Каразіна (PDF). Архів оригіналу (PDF) за 18 квітня 2021. Процитовано 18 квітня 2021.
  2. Алгебрична структура (PDF). Архів оригіналу (PDF) за 18 квітня 2021. Процитовано 18 квітня 2021.
  3. Юрачківський А. П. Начала функціонального аналізу і теорії інтеграла. — К., 2012. — 243 с.

Див. також

[ред. | ред. код]

Джерела

[ред. | ред. код]