First-order definability on finite structures

Abstract

If k is a fixed positive integer, G is a graph with n vertices,υ1, υ2∈G then the property dG(υ1, υ2)≤k can be easily defined by a first-order formula with at most 2+2log2k quantifiers. Let M be a finite structure with n elements. We may consider G as a binary relation on the universe M. Using the relations of M may help to define the given property of G. (E.g. the number k may be coded by one of the relations.) However, we prove that if n is sufficiently large compared to k, then the given property cannot be defined by a first-order formula whose length does not depend on k even if we are allowed to use in this formula the arbitrary relations given on M. This result implies that the existential first-order formulas form a nontrivial hierarchy on finite structures in a strong sense. © 1989.