Щільний порядок — бінарне відношення між елементами множин у частковому або лінійному порядку (позначимо його <) на множині X, коли для всіх x і y з X, для яких виконується x < y, існує елемент z в X, такий що x < z < y. Іншими словами, порядок називають щільним, коли немає сусідніх елементів. Оскільки між будь-якими двома елементами щільного порядку є ще хоча б один, будь-який відрізок щільного порядку нескінченний[1].
Приклад
Щільною впорядкованою множиною є дійсні числа і раціональні числа зі звичайним порядком. З іншого боку, звичайний порядок цілих чисел щільним не є.
Єдиність
Георг Кантор довів, що дві будь-які щільні лінійно впорядковані зліченні множини без нижньої і верхньої меж ізоморфні відносно впорядкування[2]. Зокрема, існує ізоморфізм зі збереженням порядку між раціональними числами та іншими щільними зліченними множинами, включно з двійково-раціональними числами й алгебричними числа. У методі підбору[en][3] використовується доведення цього результату.
Для визначення ізоморфізмів порядку між квадратичними алгебричними числами і раціональними числами, а також між раціональними числами і двійково-раціональними числами можна використати функцію Мінковського.
Узагальнення
Бінарне відношення R вважається щільним, якщо для всіх пов'язаних відношенням R x і y, є z, таке що x і z, а також z і y пов'язані відношенням R. Формально:
У термінах суперпозиції відношень[en] R із собою, умову щільності можна альтернативно виразити як [4].
Достатніми умовами до того, що бінарне відношення R на множині X матиме щільний порядок, є випадки коли:
- R рефлексивне;
- R корефлексивне ;
- R квазірефлексивне ;
- R ліво- або правоевклідове;
- R симетричне і напівконексне[en] і X має елементів.
Жодна з них не є необхідною. Непорожнє щільне відношення не може бути антитранзитивним.
Строго частковий порядок < є щільним порядком тоді і тільки тоді, коли < є щільним відношенням. Щільне відношення є ідемпотентним відношенням[en], коли воно також транзитивне.
Див. також
- Щільна множина
- Щільна в собі підмножина[en]
- Семантика Кріпке — щільне відношення досяжності, яке відповідає аксіомі
Примітки
- ↑ Лекция 5: упорядоченные множества (PDF). Математический институт им. В.А. Стеклова Российской академии наук (русский) . 2015. Архів оригіналу (PDF) за 1 листопада 2019. Процитовано 29 червня 2021.
- ↑ Roitman, 1990, с. 123.
- ↑ Dasgupta, 2013, с. 161.
- ↑ Schmidt, 2011, с. 212.
Джерела
- Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)
- Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : ОНТИ , 1937. — 304 с. — ISBN 978-5-382-00127-2.(рос.)
- Judith Roitman. Theorem 27, p. 123 // [1] — John Wiley & Sons, 1990. — Т. 8. — (Pure and Applied Mathematics) — ISBN 9780471635192. Архівовано з джерела 29 червня 2021
- Abhijit Dasgupta. [2] — Springer-Verlag, 2013. — ISBN 9781461488545. Архівовано з джерела 29 червня 2021
- Gunter Schmidt. Relational Mathematics. — Cambridge University Press, 2011. — ISBN 978-0-521-76268-7.
- David Harel, Dexter Kozen, Jerzy Tiuryn. Dynamic logic. — MIT Press, 2000. — С. 6ff. — ISBN 0-262-08289-6.