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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Напівґратка[ред.ред. код]

Напівґратка — частково впорядкована множина, в якій визначена операція 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:

Якщо abx тоді існують a' and b' такі, що aa' , bb' та 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)).

Частковий порядок[ред.ред. код]

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

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

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

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

Теорема Стоуна[ред.ред. код]

Джерела[ред.ред. код]

  • Биркгоф Г.en (1984). Теория решёток. Переклад с англ. В. Н. Салий; Под ред. Л. А. Скорнякова. Москва: Наука. с. 566.  9400 экз.
  • Скорняков Л. А. Элементы теории структур. — М., 1970.
  • Гретцер Г. Общая теория решёток. — М.: Мир, 1982. — 456 с.