Плотный порядок

Плотный порядок — это отношение между элементами множеств в частичном или линейном порядке (обозначим его <) на множестве X, когда для всех x и y из X, для которых выполняется x < y, существует элемент z в X, такой что x < z < y. Иными словами, порядок называют плотным, когда нет соседних элементов. Поскольку между любыми двумя элементами плотного порядка есть ещё хотя бы один, любой отрезок плотного порядка бесконечен.

Пример

Плотным упорядоченным множеством являются вещественные числа и рациональные числа с обычным порядком. С другой стороны, обычный порядок целых чисел плотным не является.

Единственность

Георг Кантор доказал, что два любых плотных линейно упорядоченных счётных множества без нижней и верхней границ изоморфны относительно упорядочения. В частности, существует изоморфизм с сохранением порядка между рациональными числами и другими плотными счётными множествами, включая двоично-рациональные числа и алгебраические числа. В методе подбора используется доказательство этого результата.

Функция Минковского может быть использована для определения изоморфизмов порядка между квадратичными алгебраическими числами и рациональными числами, а также между рациональными числами и двоично-рациональными числами.

Обобщения

Бинарное отношение R считается плотным, если для всех связанных отношением R x и y, имеется z, такое что x и z, а также z и y связаны отношением R. Формально:

$\forall x\ \forall y\ xRy\Rightarrow (\exists z\ xRz\land zRy).$

В терминах суперпозиции отношений R с собой, условие плотности может быть альтернативно выражено как $R\subseteq RR$.

Достаточными условиями к тому, что бинарное отношение R на множестве X будет иметь плотный порядок, являются случаи когда:

• R рефлексивно;
• R корефлексивно;
• R квазирефлексивно;
• R лево- или право-евклидово;
• R симметрично и полуконнексно и X имеет $\geqslant 3$ элементов.

Ни одно из них не является необходимым. Непустое плотное отношение не может быть антитранзитивным.

Строго частичный порядок < является плотным порядком тогда и только тогда, когда < является плотным отношением. Плотное отношение является идемпотентным отношением, когда оно также транзитивно.

См. также

• Плотное множество
• Плотное в себе подмножество
• Семантика Крипке — плотное отношение достижимости, которое соответствует аксиоме $\Box \Box A\rightarrow \Box A$

Литература

• Judith Roitman. Theorem 27, p. 123 // Introduction to Modern Set Theory. — John Wiley & Sons, 1990. — Т. 8. — (Pure and Applied Mathematics). — ISBN 9780471635192.
• Abhijit Dasgupta. Set Theory: With an Introduction to Real Point Sets. — Springer-Verlag, 2013. — ISBN 9781461488545.
• Gunter Schmidt. Relational Mathematics. — Cambridge University Press, 2011. — ISBN 978-0-521-76268-7.

Литература для дальнейшего чтения

• David Harel, Dexter Kozen, Jerzy Tiuryn. Dynamic logic. — MIT Press, 2000. — С. 6ff. — ISBN 0-262-08289-6.