Упорядоченное множество
Упоря́доченное мно́жество, множество, на котором задано отношение порядка (линейного или частичного, строгого или нестрогого). При этом отношением порядка на множестве называется бинарное отношение (соответствие), обычно обозначаемое символом и обладающее следующими свойствами:
1) (рефлексивность);
2) если и , то (транзитивность);
3) если и , то (антисимметричность).
Если является отношением порядка, то отношение , определяемое условием и , называется строгим порядком. Запись обычно читается как « меньше или равно » или « больше или равно », а – как « меньше » или « больше » (иногда говорят также « следует за » или « предшествует »).
Порядок называется линейным, если для любых либо , либо . В этом случае множество называется линейно упорядоченным или цепью. Пример линейно упорядоченного множества даёт действительная прямая с естественным отношением порядка на ней.
Если же в допускаются и несравнимые между собой элементы, то порядок называется частичным, а множество – частично упорядоченным. Примерами частично упорядоченного множества являются множество всех действительных функций на отрезке, где означает, что для всех точек этого отрезка, и множество всех подмножеств данного множества, где означает, что содержится в .
Определение частично упорядоченного множества впервые явно сформулировал Ф. Хаусдорф (1914), хотя входящие в определение порядка аксиомы рассматривались ещё Г. В. Лейбницем (1690).