Теорія порядку

Теорія порядку
Досліджує	частковий порядок і частково впорядкована множина
Теорія порядку у Вікісховищі

Тео́рія поря́дку (англ. Order theory) — це галузь математики, яка досліджує інтуїтивне поняття порядку із застосуванням бінарних відношень. Вона забезпечує формальну систему для опису таких тверджень, як «це є меншим за те» або «це передує тому».

Основні означення

Види впорядкування

Використовуючи властивості бінарних відношень описують різні типи впорядкування.

Транзитивні бінарні відношення

	Симетричне	Антисиметричне	Повне	Фундоване	Має поєднання	Має зустріч	Рефлексивне	Антирефлексивне	Асиметричне
Еквівалентність	Так	✗	✗	✗	✗	✗	Так	✗	✗
Передпорядок (Квазіпорядок)	✗	✗	✗	✗	✗	✗	Так	✗	✗
Частковий порядок	✗	Так	✗	✗	✗	✗	Так	✗	✗
Повний передпорядок	✗	✗	Так	✗	✗	✗	Так	✗	✗
Лінійний порядок	✗	Так	Так	✗	✗	✗	Так	✗	✗
Цілковий передпорядок	✗	✗	Так	Так	✗	✗	Так	✗	✗
Цілковий квазіпорядок	✗	✗	✗	Так	✗	✗	Так	✗	✗
Цілковий порядок	✗	Так	Так	Так	✗	✗	Так	✗	✗
Ґратка	✗	Так	✗	✗	Так	Так	Так	✗	✗
Верхня напівґратка	✗	Так	✗	✗	Так	✗	Так	✗	✗
Нижня напівґратка	✗	Так	✗	✗	✗	Так	Так	✗	✗
Строгий частковий порядок	✗	Так	✗	✗	✗	✗	✗	Так	Так
Строгий слабкий порядок	✗	Так	✗	✗	✗	✗	✗	Так	Так
Строгий лінійний порядок	✗	Так	Так	✗	✗	✗	✗	Так	Так
Визначення, для всіх $a,b$ і $S\neq \varnothing$:	${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$	${\begin{aligned}aRb{\text{ і }}&bRa\\\Rightarrow a={}&b\end{aligned}}$	${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ або }}&bRa\end{aligned}}$	${\begin{aligned}\min S\\{\text{існує}}\end{aligned}}$	${\begin{aligned}a\vee b\\{\text{існує}}\end{aligned}}$	${\begin{aligned}a\wedge b\\{\text{існує}}\end{aligned}}$	$aRa$	${\text{не }}aRa$	${\begin{aligned}aRb\Rightarrow \\{\text{не }}bRa\end{aligned}}$
Так вказує на те, що властивість зі стовпця завжди істинна для терміна з відповідного рядка (зліва), тоді як ✗ вказує, що властивість не гарантується в загальному випадку (вона може виконуватися або ні). Наприклад, те, що кожне відношення еквівалентності є симетричним, але не обов'язково антисиметричним, позначається Так у стовпці «Симетричне» та ✗ у стовпці «Антисиметричне» відповідно. Усі визначення неявно вимагають, щоб однорідне відношення $R$ було транзитивним: для всіх $a,b,c$, якщо $aRb$ і $bRc$, то $aRc$. Визначення терміна може вимагати додаткових властивостей, які не перераховані в цій таблиці.

Особливі елементи

• Найбільший та найменший елемент
• Максимальні та мінімальні елементи
• Верхня та нижня межа
• Інфімум та супремум

Операції

• Поєднання та зустріч

Особливі підмножини

• Ланцюг, антиланцюг
• Верхня множина, нижня множина
• Спрямована вверх множина, спрямована вниз множина
• Ідеал, фільтр
• Сильний антиланцюг, загальний фільтр

Висота і ширина

• Шириною посета називається величина максимального антиланцюга. За теоремою Ділуорса ширина рівна мінімальній кількості ланцюгів, на які можна розбити посет.
• Висотою посета називається величина максимального ланцюга. За теоремою Мирського висота рівна мінімальній кількості антиланцюгів, на які можна розбити посет.

Див. також

• Двоїстість (теорія порядку)
• Циклічний порядок
• Послідовно-паралельний частковий порядок

Джерела

• Биркгоф Г. Теория решёток / пер. с англ. В. Н. Салий ; под ред. Л. А. Скорнякова. — 3-е изд. — Москва : Наука, 1984. — 568 с.(рос.)
• Stanley N. Burris, H. P. Sankappanavar. A Course in Universal Algebra. — Berlin, New York : Springer-Verlag, 1981.(англ.)
• Davey, B. A.; Priestley, H. A. (2002). Introduction to Lattices and Order (вид. 2nd). Cambridge University Press. ISBN 0-521-78451-4. (англ.)
• Gierz, G.; Hofmann, K. H.; Keimel, K.; Mislove, M.; Scott, D. S. (2003). Continuous Lattices and Domains. Encyclopedia of Mathematics and its Applications. Т. 93. Cambridge University Press. ISBN 978-0-521-80338-0. (англ.)

Посилання

• Порядки записом ProvenMath [Архівовано 11 жовтня 2006 у Wayback Machine.]: частковий порядок, лінійний порядок, цілком-впорядкованість, початкова ланка; формальні визначення та доведення в межах аксіом теорії множин. (англ.)
• Nagel, Felix (2013). Set Theory and Topology. An Introduction to the Foundations of Analysis [Архівовано 25 січня 2021 у Wayback Machine.] (англ.)