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

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

ПримерПравить

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

ЕдинственностьПравить

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

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

ОбобщенияПравить

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

 

В терминах суперпозиции отношений[en] R с собой, условие плотности может быть альтернативно выражено как  [4].

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

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

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

См. такжеПравить

ПримечанияПравить

  1. Лекция 5: упорядоченные множества (рус.) ?. Математический институт им. В.А. Стеклова Российской академии наук (2015). Дата обращения: 16 февраля 2021. Архивировано 1 ноября 2019 года.
  2. Roitman, 1990, с. 123.
  3. Dasgupta, 2013, с. 161.
  4. Schmidt, 2011, с. 212.

ЛитератураПравить

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

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