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

Отношение порядка — бинарное отношение (далее обозначаемое ${\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 \leqslant }$ для вещественных чисел определяет для них нестрогий линейный порядок.
• Отношение ${\displaystyle <}$ для вещественных чисел определяет для них строгий линейный порядок.
• Отношение делимости на множестве натуральных чисел: ${\displaystyle a|b,}$ если ${\displaystyle a}$ является делителем ${\displaystyle b.}$ Это нестрогий частичный порядок, так как не всякие натуральные числа делятся друг на друга без остатка.
• Отношение включения на множестве подмножеств заданного множества также определяет нестрогий частичный порядок.
• Отношение (предок, потомок) на популяции животных является строгим частичным порядком.

Отношение нестрогого (рефлексивного) частичного порядка (${\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.}$

• Теорема Шпильрайна

• Курош А. Г. Лекции по общей алгебре. — 2-е изд. — М.: Физматлит, 1973.
• Jech, Thomas. Set Theory: The Third Millennium Edition, Revised and Expanded. — Springer, 2003. — ISBN 3-540-44085-2.