ru.wikipedia.org

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

Отношение порядка — бинарное отношение (далее обозначаемое {\displaystyle \preccurlyeq } для нестрогого, {\displaystyle \prec } для строгого) между элементами данного множества, по своим свойствам сходное со свойствами отношения неравенства➤.

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

Примеры[2].

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

  1. Рефлексивность: {\displaystyle a\preccurlyeq a}.
  2. Антисимметричность: если {\displaystyle a\preccurlyeq b} и {\displaystyle b\preccurlyeq a}, то {\displaystyle a=b}.
  3. Транзитивность: если {\displaystyle a\preccurlyeq b} и {\displaystyle b\preccurlyeq c}, то {\displaystyle a\preccurlyeq c}.

Отношение строгого (антирефлексивного, иррефлексивного) частичного порядка ({\displaystyle \prec }) на множестве {\displaystyle X} — это бинарное отношение, для которого при любых {\displaystyle a,b,c} из {\displaystyle X} выполнены следующие условия:[3]

  1. Антирефлексивность (или иррефлексивность): {\displaystyle a\not \prec a};
  2. Транзитивность: если {\displaystyle a\prec b} и {\displaystyle b\prec c}, то {\displaystyle a\prec c}.

Для строгого порядка также выполняется свойство асимметричности (если {\displaystyle a\prec b}, то {\displaystyle b\not \prec a}), однако оно следует из антирефлексивности и транзитивности и поэтому не включается в определение.

Каждому отношению нестрогого порядка {\displaystyle \preccurlyeq } взаимо-однозначно соответствует отношение строгого порядка {\displaystyle \prec }, связанное с ним соотношением[4]

{\displaystyle a\prec b} тогда и только тогда, когда {\displaystyle a\preccurlyeq b} и {\displaystyle a\neq b}.

Обратно отношение нестрогого порядка через соответствуещее отношение строгого порядка можно получить через соотношение[3]

{\displaystyle a\preccurlyeq b} тогда и только тогда, когда {\displaystyle a\prec b} или {\displaystyle a=b}.

Для отношения порядка (строгого {\displaystyle \prec } или нестрогого {\displaystyle \preccurlyeq }) обратное отношение тоже является отношением порядка (строгого или нестрогого соответсвенно) и обозначается как {\displaystyle \succ } или {\displaystyle \succcurlyeq }.[5]

Множество {\displaystyle X}, на котором введено отношение строгого или нестрогого порядка, называется частично упорядоченным. Если к тому же для любых элементов {\displaystyle a\neq b} дополнительно выполняется одно из условий: {\displaystyle a\prec b} или {\displaystyle b\prec a,} то порядок называется линейным, а множество — линейно упорядоченным.[6][4]

Знаки {\displaystyle <} и {\displaystyle >} предложил английский учёный Томас Хэрриот в своём сочинении, изданном посмертно в 1631 году[7].

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

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

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

{\displaystyle a\equiv b,} если {\displaystyle a\prec b} и {\displaystyle b\prec a,}

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

{\displaystyle [a]\preccurlyeq [b],} если {\displaystyle a\prec b,}

где {\displaystyle [x]} — класс эквивалентности, содержащий элемент {\displaystyle x.}

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