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

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

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

Примеры^[1].

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

Определения

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

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

если ${\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,}$ то порядок называется линейным, а множество — линейно упорядоченным^[2].

История

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

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

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

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

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

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

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

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

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

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

См. также

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

Примечания

Литература

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

Эта страница в последний раз была отредактирована 3 января 2024 в 12:45.