Отношение порядка
Отношение порядка — бинарное отношение (далее обозначаемое [math]\displaystyle{ \preccurlyeq }[/math] или [math]\displaystyle{ \prec }[/math]) между элементами данного множества, по своим свойствам сходное со свойствами отношения неравенства.
Множество, все элементы которого сравнимы заданным отношением порядка (то есть для любых [math]\displaystyle{ a \ne b }[/math] либо [math]\displaystyle{ a \preccurlyeq b }[/math], либо [math]\displaystyle{ b \preccurlyeq a }[/math]), называется линейно упорядоченным, а отношение порядка называется линейным порядком. Если же сравнимы не все неравные элементы, порядок называется частичным, а множество — частично упорядоченным. Различают также строгий порядок [math]\displaystyle{ \prec }[/math], при котором [math]\displaystyle{ a \prec a }[/math] невозможно, и нестрогий [math]\displaystyle{ \preccurlyeq }[/math] в противном случае[1].
Примеры[1].
- Отношение [math]\displaystyle{ \leqslant }[/math] для вещественных чисел определяет для них нестрогий линейный порядок.
- Отношение [math]\displaystyle{ \lt }[/math] для вещественных чисел определяет для них строгий линейный порядок.
- Отношение делимости на множестве натуральных чисел: [math]\displaystyle{ a|b, }[/math] если [math]\displaystyle{ a }[/math] является делителем [math]\displaystyle{ b. }[/math] Это нестрогий частичный порядок, так как не всякие натуральные числа делятся друг на друга без остатка.
- Отношение включения на множестве подмножеств заданного множества также определяет нестрогий частичный порядок.
- Отношение (предок, потомок) на популяции животных является строгим частичным порядком.
Определения
Отношение нестрогого (рефлексивного) частичного порядка ([math]\displaystyle{ \preccurlyeq }[/math]) на множестве [math]\displaystyle{ X }[/math] — это бинарное отношение, для которого при любых [math]\displaystyle{ a,b,c }[/math] из [math]\displaystyle{ X }[/math] выполнены следующие условия[2]:
- Рефлексивность: [math]\displaystyle{ a\preccurlyeq a }[/math].
- Антисимметричность: если [math]\displaystyle{ a\preccurlyeq b }[/math] и [math]\displaystyle{ b\preccurlyeq a }[/math], то [math]\displaystyle{ a= b }[/math].
- Транзитивность: если [math]\displaystyle{ a\preccurlyeq b }[/math] и [math]\displaystyle{ b\preccurlyeq c }[/math], то [math]\displaystyle{ a\preccurlyeq c }[/math].
Удобно также дополнительно определить для отношения [math]\displaystyle{ \preccurlyeq }[/math] отношение строгого (антирефлексивного) порядка ([math]\displaystyle{ \prec }[/math]) на том же множестве[1]:
- [math]\displaystyle{ a \prec b }[/math], если [math]\displaystyle{ a \preccurlyeq b }[/math] и при этом [math]\displaystyle{ a \ne b. }[/math]
Свойства строгого отношения отличаются от свойств нестрогого:
- Антирефлексивность: [math]\displaystyle{ a\not\prec a }[/math];
- Асимметричность: если [math]\displaystyle{ a\prec b }[/math], то [math]\displaystyle{ b\not\prec a }[/math];
- Транзитивность: если [math]\displaystyle{ a\prec b }[/math] и [math]\displaystyle{ b\prec c }[/math], то [math]\displaystyle{ a\prec c }[/math].
2-е свойство не является независимым, оно следует из антирефлексивности и транзитивности. Поэтому отношение является отношением строгого порядка тогда и только тогда, когда оно антирефлексивно и транзитивно.
Множество [math]\displaystyle{ X }[/math], на котором введено отношение строгого или нестрогого порядка, называется частично упорядоченным. Если к тому же для любых элементов [math]\displaystyle{ a \ne b }[/math] дополнительно выполняется одно из условий: [math]\displaystyle{ a\prec b }[/math] или [math]\displaystyle{ b\prec a, }[/math] то порядок называется линейным, а множество — линейно упорядоченным[2].
История
Знаки [math]\displaystyle{ \lt }[/math] и [math]\displaystyle{ \gt }[/math] предложил английский учёный Томас Хэрриот в своём сочинении, изданном посмертно в 1631 году[3].
Определение частично упорядоченного множества впервые явно сформулировал Ф. Хаусдорф [4], хотя аналогичные аксиомы порядка рассматривались еще Г. Лейбницем около 1690 года. Определение линейно упорядоченного и вполне упорядоченного множеств впервые дано Г. Кантором[5].
Вариации и обобщения
Если упорядоченное множество образует какую-либо алгебраическую структуру, то обычно требуется, чтобы порядок в этой структуре был согласован с алгебраическими операциями. См. об этом статьи:
Иногда полезно рассматривать отношения, для которых выполняются только первая и третья аксиомы (рефлексивность и транзитивность); такие отношения называются предпорядком или квазипорядком. Если [math]\displaystyle{ \prec }[/math] — квазипорядок, то отношение, заданное формулой[6]:
- [math]\displaystyle{ a \equiv b, }[/math] если [math]\displaystyle{ a \prec b }[/math] и [math]\displaystyle{ b \prec a, }[/math]
будет отношением эквивалентности. На фактормножестве по этой эквивалентности можно определить нестрогий порядок следующим образом[6]:
- [math]\displaystyle{ [a] \preccurlyeq [b], }[/math] если [math]\displaystyle{ a \prec b, }[/math]
где [math]\displaystyle{ [x] }[/math] — класс эквивалентности, содержащий элемент [math]\displaystyle{ x. }[/math]
См. также
Примечания
- ↑ 1,0 1,1 1,2 Курош, 1973, с. 16, 20—22.
- ↑ 2,0 2,1 Нечаев, 1975, с. 78.
- ↑ Александрова Н. В. История математических терминов, понятий, обозначений: Словарь-справочник. — 3-е изд. — СПб.: ЛКИ, 2008. — С. 111—112. — 248 с. — ISBN 978-5-382-00839-4.
- ↑ Hausdorff F. Grundzuge der Mengenlehre, Lpz., 1914.
- ↑ Частично упорядоченное множество // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1985. — Т. 5. — С. 833—836. — 1248 с.
- ↑ 6,0 6,1 Порядок // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1984. — Т. 4. — С. 505. — 1216 с.
Литература
- Курош А. Г. Лекции по общей алгебре. — 2-е изд. — М.: Физматлит, 1973.
- Нечаев В. И. Числовые системы. — М.: Просвещение, 1975. — 199 с.