A counterexample to Fishburn's conjecture on finite linear qualitative probability

Kraft, Pratt and Seidenberg (Ann. Math. Statist. 30 (1959) 408) provided an infinite set of axioms which, when taken together with de Finetti's axiom, gives a necessary and sufficient set of “cancellation” conditions for representability of an ordering relation on subsets of a set by an order-preserving probability measure. Fishburn (1996) defined f(n) to be the smallest positive integer k such that every comparative probability ordering on an n-element set which satisfies the cancellation conditions C₄,…,C_k is representable. By the work of Kraft, Pratt, and Seidenberg (1959) and Fishburn (J. Math. Psychol. 40 (1996) 64; J. Combin. Design 5 (1997) 353), it is known that n-1?f(n)?n+1 for all n?5. Also Fishburn proved that f(5)=4, and conjectured that f(n)=n-1 for all n?5. In this paper we confirm that f(6)=5, but give counter-examples to Fishburn's conjecture for n=7, showing that f(7)?7. We summarise, correct and extend many of the known results on this topic, including the notion of “almost representability”, and offer an amended version of Fishburn's conjecture.