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

Отношение нестрогого (рефлексивного) частичного порядка (${\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 \preccurlyeq }$ отношение строгого (антирефлексивного) порядка (${\displaystyle \prec }$) на том же множестве^[1]:

${\displaystyle a\prec b}$, если ${\displaystyle a\preccurlyeq b}$ и при этом ${\displaystyle a\neq b.}$

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

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

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

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

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

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

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

• Упорядоченная группа
• Упорядоченное кольцо
• Упорядоченное поле

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

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

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

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

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