A Characterization of First-Order Definable Subsets on Classes of Finite Total Orders
Assaf J. Kfoury, M. Wymann-Boeni · 1993
We give an explicit and easy-to-verify characterization for subsets in finite total orders (infinitely many of them in general) to be uniformly definable by a first-order formula. From this characterization we derive immediately that Beth's definability theorem does not hold in any class of finite total orders, as well as that McColm's first conjecture is true for all classes of finite total orders. Another consequence is a natural 0-1 law for definable subsets on finite total orders expressed as a statement about the possible densities of first-order definable subsets. 1 Introduction Finite Model Theory has arisen as a complement to conventional model theory motivated by the search for models for databases and query languages. Also, the study of finite models can yield many beautiful characterizations of complexity classes in terms of logic. (For the first aspect, see the work of Aho and Ullman [1], Chandra [2], Chandra and Harel [3], Gaifman et. Partly supported by NSF grant CCR-...