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

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

Множество, все элементы которого сравнимы заданным отношением порядка (то есть для любых $a \ne 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$.

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

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

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

Каждому отношению нестрогого порядка $\preccurlyeq$ взаимо-однозначно соответствует отношение строгого порядка $\prec$, связанное с ним соотношением $$a\prec b$$тогда и только тогда, когда $a\preccurlyeq b$ и $a\ne b$. Обратно отношение нестрогого порядка через соответствуещее отношение строгого порядка можно получить через соотношение $$a\preccurlyeq b$$тогда и только тогда, когда $a\prec b$ или $a=b$.

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

Множество $X$, на котором введено отношение строгого или нестрогого порядка, называется частично упорядоченным. Если к тому же для любых элементов $a \ne 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.^{о книге}
• Jech, Thomas Set Theory: The Third Millennium Edition, Revised and Expanded. — Springer, 2003. — ISBN 3-540-44085-2^{о книге}Свойство «Ссылка/Автор» типа «Страница» со значением «Jech, Thomas» содержит недопустимые символы или неполно и может привести к неожиданным результатам при семантическом аннотировании или запросе.

Разделы математики