A Characterization of First-Order Definable Subsets on Classes of Finite Total Orders
Files
Main report
Date
1993-08
DOI
Authors
Kfoury, A.J.
Wymann-Böni, M.
Version
OA Version
Citation
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.