Адносіна парадку

Адносі́на пара́дку (упарадкава́насць) — бінарная адносіна на мностве, якая дазваляе ўпарадкаваць яго элементы, гэта значыць задаць правіла, згодна якому адны элементы ідуць перад іншымі.

Фармальна ўпарадкаванасць вызначаецца як адносіна, якая з’яўляецца транзітыўнай ($\forall x,y,z : R(x,y), R(y,z) => R(x,z)$) і антысіметрычнай ($\forall x,y : R(x,y) => \lnot R(y,x)$). Любая адносіна, што валодае гэтымі характарыстыкамі, з’яўляецца адносінай парадку.

Калі адносіна парадку R з’яўляецца рэфлексіўнай (гэта значыць, што $\forall x : R(x,x)$), такую ўпарадкаванасць называюць нястрогай; антырэфлексіўную адносіну парадку (такую, што $\forall x : \lnot R(x,x)$) называюць строгай упарадкаванасцю.

Упарадкаванасць мноства з’яўляецца поўнай, або лінейнай, калі яна ўпарадкоўвае ўсе яго элементы, гэта значыць, для любых двух яго элементаў мае месца або R(x,y), або R(y,x). Калі ж існуе хаця б адна такая пара, для якой не мае месца ні R(x,y), ні R(y,x), то ўпарадкаванасць з'яўляецца частковай.

Цалкам упарадкаваныя мноствы называюцца ланцугамі.

Прыкладам поўнай строгай упарадкаванасці з’яўляецца адносіна «больш» або «менш» між сапраўднымі лікамі.

Прыкладам частковай строгай упарадкаванасці з’яўляецца адносіна «нашчадак» між людзьмі, бо яна транзітыўная (нашчадак нашчадка ёсць нашчадкам), антысіметрычная (людзі не могуць быць начшадкамі адзін аднаго), антырэфлексіўная (чалавек не ёсць нашчадкам самога сябе) і няпоўная (бо, напрыклад, на падмностве братоў адносіна «нашчадак» не вызначаная – ніхто не ёсць нічыім нашчадкам).

У якасці прыклада частковай нястрогай упарадкаванасці можна прывесці адносіну дзялімасці між натуральнымі лікамі. Сапраўды, яна транзітыўная (любы лік дзеліцца на дзельнік свайго дзельніка), антысіметрычная (дзельнік не дзеліцца на сваё дзеліва), рэфлексіўная (любы лік дзеліцца сам на сябе) і няпоўная (напрыклад, на падмностве простых лікаў гэтая адносіна не вызначаная).