Threshold-Bounded Interval Orders and a Theory of Picycles
Peter C. Fishburn · SIAM Journal on Algebraic and Discrete Methods · 1983
Given $1\leqq m\leqq n$ with m and n relatively prime if $m\geqq 2$, let $\mathcal{P} [ m,n ]$ be the class of finite partially ordered sets $( A,P )$ whose points $a,b, \cdots $ can be mapped into closed intervals with lengths in $[ m,n ]$ such that, for all $a,b \in A,aPb$ if and only if a’s interval lies completely to the right of b’s interval. A theory of picycles based on a mixture of algebraic and combinatorial ideas leads to the conclusion that each $\mathcal{P} [ m,n ]$ is axiomatizable by a universal sentence of first-order logic. Necessary and sufficient conditions for membership in $\mathcal{P} [ m,n ]$ are specified. The present results lie in sharp contrast to an earlier conclusion that the class $\mathcal{P}_n $ of finite interval orders which can be represented using no more than n interval lengths is not axiomatizable by a universal sentence when $n\geqq 2$.