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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

  1. Лекция 5: упорядоченные множества (рус.). Математический институт им. В.А. Стеклова Российской академии наук (2015).
  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.