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

Определения

Пусть дано множество $X.$

• Бинарное отношение $\preceq$ на $X$ называется предпорядком (или квазипорядком), если оно транзитивно и рефлексивно, то есть
  1. $\forall x,y,z\in X\quad \bigl( x \preceq y \bigr) \wedge \bigl( y \preceq z \bigr) \Rightarrow \bigl( x \preceq z \bigr);$
  2. $\forall x \in X \quad x \preceq x.$
• Бинарное отношение $\preceq$ на $X$ называется отношением нестрогого частичного порядка (или нестрогим порядком) на $X$, если оно транзитивно, антисимметрично и рефлексивно, то есть
  1. $\forall x,y,z\in X\quad \bigl( x \preceq y \bigr) \wedge \bigl( y \preceq z \bigr) \Rightarrow \bigl( x \preceq z \bigr);$
  2. $\forall x,y\in X \quad \bigl( x \preceq y \bigr) \wedge \bigl( y \preceq x \bigr) \Rightarrow \bigl( x = y \bigr);$
  3. $\forall x \in X \quad x \preceq x.$
• Бинарное отношение $\prec$ на $X$ называется отношением строгого частичного порядка (или строгим порядком) на $X$, если оно транзитивно и асимметрично, то есть
  1. $\forall x,y,z\in X\quad \bigl( x \prec y \bigr) \wedge \bigl( y \prec z \bigr) \Rightarrow \bigl( x \prec z \bigr);$
  2. $\forall x,y\in X \quad \bigl( x \prec y \bigr) \Rightarrow \bigl( y \not\prec x \bigr).$
• Множество, на котором определён частичный порядок, называется частично упорядоченным.
• Отношение порядка $\preceq$, являющееся линейным, то есть таким, что

  $\forall x,y\in X \quad \bigl( x\preceq y) \vee (y \preceq x),$

  называется линейным порядком. Множество, на котором определён линейным порядок, называется линейно упорядоченным (или цепью). Отношение порядка $\preceq$, являющееся линейным и имеющее в любой своей цепи (или, что эквивалентно, подмножестве) минимальный её элемент, называется полным порядком. Множество, на котором определён полный порядок, называется вполне упорядоченным.

Свойства

• Полный порядок всегда является нестрогим.
• Если $R$ суть нестрогий порядок, то $R' = R \setminus \{ (x,x) \mid x\in X\}$ суть соответствующий ему строгий порядок.
• Обратно, если $R'$ строгий порядок, то $R = R' \cup \{ (x,x) \mid x \in X\}$ - соответствующий ему нестрогий порядок.

См. также

• Лемма Цорна