WikiSort.ru - Не сортированное

Говорят, что частичный порядок или линейный порядок < на множестве X плотный, если для всех x и y из X, для которых выполняется x < y, существует элемент z в X, такой что x < z < y.

Пример

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

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

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

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

Обобщения

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

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

Альтернативно, в терминах суперпозиции отношений^[en] R с собой, условие плотности может быть выражено как ${\displaystyle R\subseteq RR}$ ^[3].

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

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

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

Строго частичный порядок < является плотным порядком тогда и только тогда, когда < является плотным отношением. В случае, когда плотное отношение также и транзитивно, говорят, что оно является идемпотентным отношением^[en].

См. также

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

Примечания

Литература

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

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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.