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

В математике частичный порядок или полный порядок < на множестве называется плотным , если для всех и в для которых существует в такое, что . То есть для любых двух элементов, один из которых меньше другого, между ними есть другой элемент. Для полных порядков это можно упростить до «для любых двух различных элементов между ними есть другой элемент», поскольку все элементы полного порядка сравнимы . ${\displaystyle X}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle X}$ ${\displaystyle x<y}$ ${\displaystyle z}$ ${\displaystyle X}$ ${\displaystyle x<z<y}$

Пример

Рациональные числа как линейно упорядоченное множество являются плотно упорядоченным множеством в этом смысле, как и алгебраические числа , действительные числа , двоичные рациональные числа и десятичные дроби . Фактически, каждое архимедово упорядоченное расширение кольца целых чисел является плотно упорядоченным множеством. ${\displaystyle \mathbb {Z} [x]}$

Доказательство

Для элемента , в силу архимедова свойства, если , существует наибольшее целое число с , а если , , и существует наибольшее целое число с . В результате . Для любых двух элементов с , и . Поэтому является плотным. ${\displaystyle x\in \mathbb {Z} [x]}$ ${\displaystyle x>0}$ ${\displaystyle n<x}$ ${\displaystyle n<x<n+1}$ ${\displaystyle x<0}$ ${\displaystyle -x>0}$ ${\displaystyle m=-n-1<-x}$ ${\displaystyle -n-1<-x<-n}$ ${\displaystyle 0<x-n<1}$ ${\displaystyle y,z\in \mathbb {Z} [x]}$ ${\displaystyle z<y}$ ${\displaystyle 0<(x-n)(y-z)<y-z}$ ${\displaystyle z<(x-n)(y-z)+z<y}$ ${\displaystyle \mathbb {Z} [x]}$

С другой стороны, линейный порядок целых чисел не является плотным.

Уникальность для полных плотных заказов без конечных точек

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

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

Обобщения

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

${\displaystyle \forall x\ \forall y\ xRy\Rightarrow (\exists z\ xRz\land zRy).}$Альтернативно, в терминах композиции R с самим собой, плотное состояние может быть выражено как R ⊆ ( R  ; R ). ^[3]

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

• R является рефлексивным ;
• R является корефлексивным ;
• R является квазирефлексивным ;
• R — левое или правое евклидово ; или
• R симметричен и полусвязан , а X имеет не менее 3 элементов.

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

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

Смотрите также

• Плотное множество — подмножество топологического пространства, замыканием которого является всё пространство.
• Плотное в себе — подмножество топологического пространства, не содержащее изолированных точек. ${\displaystyle A}$ ${\displaystyle A}$
• Семантика Крипке — плотное отношение доступности соответствует аксиоме ${\displaystyle \Box \Box A\rightarrow \Box A}$

Ссылки

1. Ройтман, Джудит (1990), «Теорема 27, стр. 123», Введение в современную теорию множеств, Чистая и прикладная математика, т. 8, John Wiley & Sons, ISBN 9780471635192.
2. Дасгупта, Абхиджит (2013), Теория множеств: с введением в действительные точечные множества, Springer-Verlag, стр. 161, ISBN 9781461488545.
3. Гюнтер Шмидт (2011) Реляционная математика , стр. 212, Cambridge University Press ISBN 978-0-521-76268-7 

Дальнейшее чтение

• Дэвид Харел , Декстер Козен , Ежи Тюрин, Динамическая логика , MIT Press, 2000, ISBN 0-262-08289-6 , стр. 6 и далее