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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Примеры[1].

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

Определения[править | править код]

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

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

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

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

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

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

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

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

История[править | править код]

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

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

Вариации и обобщения[править | править код]

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

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

если и

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

если

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

См. также[править | править код]

Примечания[править | править код]

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

Литература[править | править код]