A Characterization of First-Order Definable Subsets on Classes of Finite Total Orders
Permanent Link
https://hdl.handle.net/2144/1472Citation (published version)
Kfoury, A.J.; Wymann-Boeni, M.. "A Characterization of First-Order Definable Subsets on Classes of Finite Total Orders", Technical Report BUCS-1993-009, Computer Science Department, Boston University, August 1993. [Available from: http://hdl.handle.net/2144/1472]Abstract
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.
Collections