Отношение порядка
—
бинарное отношение
(далее обозначаемое
или
) между элементами данного множества, по своим свойствам сходное со свойствами
отношения неравенства
.
Множество, все элементы которого сравнимы заданным отношением порядка (то есть для любых
либо
, либо
), называется
линейно упорядоченным
, а отношение порядка называется
линейным порядком
. Если же сравнимы не все неравные элементы, порядок называется
частичным
, а множество —
частично упорядоченным
. Различают также
строгий порядок
, при котором
невозможно, и
нестрогий
в противном случае
.
Примеры
.
-
Отношение
для
вещественных чисел
определяет для них нестрогий линейный порядок.
-
Отношение
для вещественных чисел определяет для них строгий линейный порядок.
-
Отношение
делимости
на множестве
натуральных чисел
:
если
является
делителем
Это нестрогий частичный порядок, так как не всякие натуральные числа делятся друг на друга без остатка.
-
Отношение
включения
на множестве
подмножеств
заданного множества также определяет нестрогий частичный порядок.
-
Отношение (предок, потомок) на популяции животных является строгим частичным порядком.
Определения
Отношение нестрогого (рефлексивного) частичного порядка
(
) на
множестве
— это
бинарное отношение
, для которого при любых
из
выполнены следующие условия
:
-
Рефлексивность
:
.
-
Антисимметричность
: если
и
, то
.
-
Транзитивность
: если
и
, то
.
Удобно также дополнительно определить для отношения
отношение строгого (антирефлексивного) порядка
(
) на том же множестве
:
-
если
и при этом
, то
.
Свойства строгого отношения отличаются от свойств нестрогого:
-
Антирефлексивность
:
;
-
Асимметричность
: если
, то
;
-
Транзитивность
: если
и
, то
.
2-е свойство не является независимым, оно следует из антирефлексивности и транзитивности. Поэтому отношение является
отношением строгого порядка
тогда и только тогда, когда оно антирефлексивно и транзитивно.
Множество
, на котором введено отношение строгого или нестрогого порядка, называется
частично упорядоченным
. Если к тому же для любых элементов
дополнительно выполняется одно из условий:
или
то порядок называется
линейным
, а множество —
линейно упорядоченным
.
История
Знаки
и
предложил английский учёный
Томас Хэрриот
в своём сочинении, изданном посмертно в 1631 году
.
Определение частично упорядоченного множества впервые явно сформулировал
Ф. Хаусдорф
, хотя аналогичные аксиомы порядка рассматривались ещё
Г. Лейбницем
около 1690 года. Определение линейно упорядоченного и вполне упорядоченного множеств впервые дано
Г. Кантором
.
Вариации и обобщения
Если упорядоченное множество образует какую-либо алгебраическую структуру, то обычно требуется, чтобы порядок в этой структуре был согласован с алгебраическими операциями. См. об этом статьи:
Иногда полезно рассматривать отношения, для которых выполняются только первая и третья аксиомы (рефлексивность и транзитивность); такие отношения называются
предпорядком
или
квазипорядком
. Если
— квазипорядок, то отношение, заданное формулой
:
-
если
и
будет
отношением эквивалентности
. На
фактормножестве
по этой эквивалентности можно определить нестрогий порядок следующим образом
:
-
если
где
— класс эквивалентности, содержащий элемент
См. также
Примечания
-
↑
, с. 16, 20—22.
-
↑
, с. 78.
-
Александрова Н. В.
. — 3-е изд. —
СПб.
: ЛКИ, 2008. — С.
—112. — 248 с. —
ISBN 978-5-382-00839-4
.
-
Hausdorff F.
Grundzuge der Mengenlehre, Lpz., 1914.
-
Частично упорядоченное множество
// Математическая энциклопедия (в 5 томах). —
М.
:
Советская Энциклопедия
, 1985. — Т. 5. — С. 833—836. — 1248 с.
-
↑
Порядок
// Математическая энциклопедия (в 5 томах). —
М.
:
Советская Энциклопедия
, 1984. — Т. 4. — С. 505. — 1216 с.
Литература
Ссылки на внешние ресурсы
|
|
|
Словари и энциклопедии
|
|
В библиографических каталогах
|
|