Proposition. For every set XX and preorder \to on XX, exists a set SS and function s:X2Ss : X \to 2^S such that xyx \to y iff s(x)s(y)s(x) \subseteq s(y) Proof. Take (X,)(X, \to). For xXx \in X, let s(x)s(x) denote the set of values yXy \in X with yxy \to x. Note that ss is of type s:XP(X)=2Xs : X \to \mathcal P(X) = 2^X, as promised. I claim that xy    s(x)s(y)x \to y \iff s(x) \subseteq s(y): ()(\Rightarrow) Take xyx \to y and zs(x)z \in s(x). Then zxz \to x so by transitivity zyz \to y so zs(y)z \in s(y). Thus s(x)s(y)s(x) \subseteq s(y). ()(\Leftarrow) Take s(x)s(y)s(x) \subseteq s(y). Note xxx \to x so xs(x)x \in s(x) so xs(y)x \in s(y) so xyx \to y. #onwards Referenced by: