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

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

Пример

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

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

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

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

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

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

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

Обобщения

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

\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, которое не рефлексивно, но плотно.Непустое и плотное отношение не может быть антитранзитивным .

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

См. также

Плотное множество - подмножество топологического пространства, замыканием которого является все пространство.
Плотный сам по себе - подмножество $A$ топологического пространства такого, что $A$ не содержит изолированной точки
Семантика Крипке - плотное отношение доступности соответствует аксиоме $\Box \Box A\rightarrow \Box A$

Ссылки

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

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

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

[1] Ройтман, Джудит (1990), «Теорема 27, стр. 123», Введение в современную теорию множеств , Чистая и прикладная математика, том. 8, Джон Уайли и сыновья, ISBN 9780471635192 .

[2] Дасгупта, Абхиджит (2013), Теория множеств: введение в наборы реальных точек , Springer-Verlag, стр. 161, ИСБН 9781461488545 .

[3] Гюнтер Шмидт (2011) Реляционная математика , стр. 212, Cambridge University Press ISBN 978-0-521-76268-7

[1]

[2]

[3]

v т и Теория порядка
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice