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

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

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

Примеры.

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

Определения

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

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

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

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

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

Каждому отношению нестрогого порядка $\preccurlyeq$ взаимо-однозначно соответствует отношение строгого порядка $\prec$, связанное с ним соотношениемШаблон:Sfn

$a\prec b$ тогда и только тогда, когда $a\preccurlyeq b$ и $a\ne b$.

Обратно отношение нестрогого порядка через соответствующее отношение строгого порядка можно получить через соотношениеШаблон:Sfn

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

Для отношения порядка (строгого $\prec$ или нестрогого $\preccurlyeq$) обратное отношение тоже является отношением порядка (строгого или нестрогого соответсвенно) и обозначается как $\succ$ или $\succcurlyeq$.Шаблон:Sfn

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

История

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

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

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

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

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

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

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

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

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

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга