Теория порядков - NiNa.Az

Отношение порядка — бинарное отношение (далее обозначаемое ${\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 \prec }$) на множестве ${\displaystyle X}$ — это бинарное отношение, для которого при любых ${\displaystyle a,b,c}$ из ${\displaystyle X}$ выполнены следующие условия:

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

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

Каждому отношению нестрогого порядка ${\displaystyle \preccurlyeq }$ взаимо-однозначно соответствует отношение строгого порядка ${\displaystyle \prec }$, связанное с ним соотношением

${\displaystyle a\prec b}$ тогда и только тогда, когда ${\displaystyle a\preccurlyeq b}$ и ${\displaystyle a\neq b}$.

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

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

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

Множество ${\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.}$

См. также

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

Примечания

1. Курош, 1973, с. 16, 20—22.
2. Курош, 1973, с. 16, 20—22.
3. Jech, 2003, с. 17.
4. Курош, 1973, с. 21.
5. Курош, 1973, с. 16-17,21.
6. Jech, 2003, с. 17.
7. Александрова Н. В. История математических терминов, понятий, обозначений: Словарь-справочник. — 3-е изд. — СПб.: ЛКИ, 2008. — С. 111—112. — 248 с. — ISBN 978-5-382-00839-4.
8. Hausdorff F. Grundzuge der Mengenlehre, Lpz., 1914.
9. Частично упорядоченное множество // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1985. — Т. 5. — С. 833—836. — 1248 с.
10. Порядок // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1984. — Т. 4. — С. 505. — 1216 с.

Литература

• Курош А. Г. Лекции по общей алгебре. — 2-е изд. — М.: Физматлит, 1973.
• Jech, Thomas. Set Theory: The Third Millennium Edition, Revised and Expanded. — Springer, 2003. — ISBN 3-540-44085-2.