Interested Article - Отношение порядка

Отношение порядка бинарное отношение (далее обозначаемое или ) между элементами данного множества, по своим свойствам сходное со свойствами отношения неравенства .

Множество, все элементы которого сравнимы заданным отношением порядка (то есть для любых либо , либо ), называется линейно упорядоченным , а отношение порядка называется линейным порядком . Если же сравнимы не все неравные элементы, порядок называется частичным , а множество — частично упорядоченным . Различают также строгий порядок , при котором невозможно, и нестрогий в противном случае .

Примеры .

  • Отношение для вещественных чисел определяет для них нестрогий линейный порядок.
  • Отношение для вещественных чисел определяет для них строгий линейный порядок.
  • Отношение делимости на множестве натуральных чисел : если является делителем Это нестрогий частичный порядок, так как не всякие натуральные числа делятся друг на друга без остатка.
  • Отношение включения на множестве подмножеств заданного множества также определяет нестрогий частичный порядок.
  • Отношение (предок, потомок) на популяции животных является строгим частичным порядком.

Определения

Отношение нестрогого (рефлексивного) частичного порядка ( ) на множестве — это бинарное отношение , для которого при любых из выполнены следующие условия :

  1. Рефлексивность : .
  2. Антисимметричность : если и , то .
  3. Транзитивность : если и , то .

Удобно также дополнительно определить для отношения отношение строгого (антирефлексивного) порядка ( ) на том же множестве :

если и при этом , то .

Свойства строгого отношения отличаются от свойств нестрогого:

  1. Антирефлексивность : ;
  2. Асимметричность : если , то ;
  3. Транзитивность : если и , то .

2-е свойство не является независимым, оно следует из антирефлексивности и транзитивности. Поэтому отношение является отношением строгого порядка тогда и только тогда, когда оно антирефлексивно и транзитивно.

Множество , на котором введено отношение строгого или нестрогого порядка, называется частично упорядоченным . Если к тому же для любых элементов дополнительно выполняется одно из условий: или то порядок называется линейным , а множество — линейно упорядоченным .

История

Знаки и предложил английский учёный Томас Хэрриот в своём сочинении, изданном посмертно в 1631 году .

Определение частично упорядоченного множества впервые явно сформулировал Ф. Хаусдорф , хотя аналогичные аксиомы порядка рассматривались ещё Г. Лейбницем около 1690 года. Определение линейно упорядоченного и вполне упорядоченного множеств впервые дано Г. Кантором .

Вариации и обобщения

Если упорядоченное множество образует какую-либо алгебраическую структуру, то обычно требуется, чтобы порядок в этой структуре был согласован с алгебраическими операциями. См. об этом статьи:

Иногда полезно рассматривать отношения, для которых выполняются только первая и третья аксиомы (рефлексивность и транзитивность); такие отношения называются предпорядком или квазипорядком . Если — квазипорядок, то отношение, заданное формулой :

если и

будет отношением эквивалентности . На фактормножестве по этой эквивалентности можно определить нестрогий порядок следующим образом :

если

где — класс эквивалентности, содержащий элемент

См. также

Примечания

  1. , с. 16, 20—22.
  2. , с. 78.
  3. Александрова Н. В. . — 3-е изд. — СПб. : ЛКИ, 2008. — С. —112. — 248 с. — ISBN 978-5-382-00839-4 .
  4. Hausdorff F. Grundzuge der Mengenlehre, Lpz., 1914.
  5. Частично упорядоченное множество // Математическая энциклопедия (в 5 томах). — М. : Советская Энциклопедия , 1985. — Т. 5. — С. 833—836. — 1248 с.
  6. Порядок // Математическая энциклопедия (в 5 томах). — М. : Советская Энциклопедия , 1984. — Т. 4. — С. 505. — 1216 с.

Литература

Источник —

Same as Отношение порядка