Title: A Characterization of First-Order Definable Subsets on Classes of Finite Total Orders 
Author: A.J. Kfoury and M. Wymann-Boeni, Boston University 
Date: August 1993


Abstract:

We give an explicit and easy-to-verify characterization for subsets in
finite total orders (infinitely many of them in general) to be definable by
the same first-order formula over any class of finite total orders.

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.