Полупорядок

Полупорядок (Semiorder) — антирефлексивное бинарное отношение [math]\displaystyle{ \,P, }[/math] удовлетворяющее условиям:

(1) [math]\displaystyle{ aPb, \, cPd }[/math] влекут за собой [math]\displaystyle{ \,aPd }[/math] или [math]\displaystyle{ \,cPb; }[/math]

(2) [math]\displaystyle{ \,aPb }[/math] и [math]\displaystyle{ \,bPc }[/math] влекут за собой [math]\displaystyle{ \,aPd }[/math] или [math]\displaystyle{ \,dPc, }[/math]

где [math]\displaystyle{ \,a,b,c,d \in V }[/math] — произвольные (необязательно различные) элементы.

Полупорядок можно также определить как бинарное отношение [math]\displaystyle{ \,P, }[/math] для которого найдется вещественнозначная функция [math]\displaystyle{ \,f }[/math] такая, что [math]\displaystyle{ \,uPv }[/math] имеет место тогда и только тогда, когда [math]\displaystyle{ \,f(u) \gt f(v) + \delta }[/math] для некоторой константы [math]\displaystyle{ \,\delta }[/math] (возможно, равной единице).

Литература

[J. Graph Theory]