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

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

Примеры .

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

Определения

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

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 }$ ) на том же множестве :

если ${\displaystyle a\preccurlyeq b}$ и при этом ${\displaystyle a\neq b}$ , то ${\displaystyle a\prec 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,}$ то порядок называется линейным , а множество — линейно упорядоченным .

История

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

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

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

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

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

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

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

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

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

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

См. также

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

Примечания

Литература

• Курош А. Г. Лекции по общей алгебре. — 2-е изд. — М. : Физматлит , 1973.
• Нечаев В. И. Числовые системы. — М. : Просвещение, 1975. — 199 с.