Отношение порядка — бинарное отношение (далее обозначаемое для нестрогого, для строгого) между элементами данного множества, по своим свойствам сходное со свойствами отношения неравенства➤.
Множество, все элементы которого сравнимы заданным отношением порядка (то есть для любых либо , либо ), называется линейно упорядоченным, а такое отношение порядка называется линейным порядком. Если же сравнимы не все неравные элементы, порядок называется частичным, а множество — частично упорядоченным. Различают также строгий порядок, при котором невозможно, и нестрогий в противном случае[1].
Отношение для вещественных чисел определяет для них нестрогий линейный порядок.
Отношение для вещественных чисел определяет для них строгий линейный порядок.
Отношение делимости на множестве натуральных чисел: если является делителем Это нестрогий частичный порядок, так как не всякие натуральные числа делятся друг на друга без остатка.
Отношение включения на множестве подмножеств заданного множества также определяет нестрогий частичный порядок.
Отношение (предок, потомок) на популяции животных является строгим частичным порядком.
Отношение нестрогого (рефлексивного) частичного порядка () на множестве — это бинарное отношение, для которого при любых из выполнены следующие условия[2]:
Отношение строгого (антирефлексивного, иррефлексивного) частичного порядка () на множестве — это бинарное отношение, для которого при любых из выполнены следующие условия:[3]
Для строгого порядка также выполняется свойство асимметричности (если , то ), однако оно следует из антирефлексивности и транзитивности и поэтому не включается в определение.
Каждому отношению нестрогого порядка взаимо-однозначно соответствует отношение строгого порядка , связанное с ним соотношением[4]
тогда и только тогда, когда и .
Обратно отношение нестрогого порядка через соответствуещее отношение строгого порядка можно получить через соотношение[3]
тогда и только тогда, когда или .
Для отношения порядка (строгого или нестрогого ) обратное отношение тоже является отношением порядка (строгого или нестрогого соответсвенно) и обозначается как или .[5]
Множество , на котором введено отношение строгого или нестрогого порядка, называется частично упорядоченным. Если к тому же для любых элементов дополнительно выполняется одно из условий: или то порядок называется линейным, а множество — линейно упорядоченным.[6][4]
История
Знаки и предложил английский учёный Томас Хэрриот в своём сочинении, изданном посмертно в 1631 году[7].
Определение частично упорядоченного множества впервые явно сформулировал Ф. Хаусдорф[8], хотя аналогичные аксиомы порядка рассматривались ещё Г. Лейбницем около 1690 года. Определение линейно упорядоченного и вполне упорядоченного множеств впервые дано Г. Кантором[9].
Вариации и обобщения
Если упорядоченное множество образует какую-либо алгебраическую структуру, то обычно требуется, чтобы порядок в этой структуре был согласован с алгебраическими операциями. См. об этом статьи:
Иногда полезно рассматривать отношения, для которых выполняются только первая и третья аксиомы (рефлексивность и транзитивность); такие отношения называются предпорядком или квазипорядком. Если — квазипорядок, то отношение, заданное формулой[10]: