Numerical representation of semiorders (Q2376915): Difference between revisions

A total preorder \(\mathcal{R}\) on \(X\) is representable in \(\mathbb{R}\) if and only if there exists a map \(u:X\rightarrow \mathbb{R}\) with \(x \mathcal{R} y \iff u(x) \leq u(y)\). An interval order \(\mathcal{R}\) on \(X\) is representable in \(\mathbb{R}\) if and only if there exists a pair of maps \(u, v:X\rightarrow \mathbb{R}\) such that \(x \mathcal{R} y \iff u(x) \leq v(y)\). If the interval order is a semiorder, it is Scott-Suppes representable if it is representable by maps \(u\) and \(v\) which satisfy \(x \mathcal{R}y \iff u(x) \leq v(y) + k\) for some fixed constant \(k > 0\). Representability in the extended real line \(\overline{\mathbb{R}}\) is defined analogously, with \(\mathbb{R}\) replaced by \(\overline{\mathbb{R}}\). A semiorder is typical if it is not a total preorder. The canonical interval order \(\sqsubseteq\) on the set \(\mathcal{Y} = \{ [a,b] : a \leq b\) in \(\overline{\mathbb{R}}\}\) of closed intervals in the extended real line is defined by \([a,b] \not\sqsubseteq [c,d]\) if and only if \([a,b]\) lies to the right of \([c,d]\) (that is, if and only if \(d<a\)). The authors say an interval order \(\mathcal{R}\) on \(X\) is representable in \(\mathcal{Y}\) if and only if there exists a map \(f:X \rightarrow \mathcal{Y}\) such that \(x \mathcal{R} y \iff f(x) \sqsubseteq f(y)\). They show that interval orders are representable in \(\mathbb{R}\) if and only if they are representable in \(\mathcal{Y}\). For total preorders (respectively, typical semiorders), representability in \(\mathbb{R}\) (respectively, \(\overline{\mathbb{R}}\)) is shown to be equivalent to representability in \(\mathcal{Y}\) through a function \(f:X\rightarrow \mathcal{Y}\) which only assumes values of degenerate intervals \([a,a]\) (respectively, intervals \([a,a+1]\) of length \(1\)). Conditions are given for semiorders to be Scott-Suppes representable in \(\mathbb{R}\) or \(\overline{\mathbb{R}}\).