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

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

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

Примеры.

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

Определения

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

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

Удобно также дополнительно определить для отношения $\preccurlyeq$ отношение строгого (антирефлексивного) порядка ($\prec$) на том же множестве:

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

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

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

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

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

История

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

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

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

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

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

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

$a\equiv b,$ если $a\prec b$ и $b\prec a,$

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

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

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

См. также

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

Литература

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