The definable criterion for definability in Presburger arithmetic and its applications
In Section 1 of present paper we construct a formula 9,,(A) of Presburger arithmetic (integers with addition and order) with additional n-ary predicate variable A. This formula is true if and only if predicate A is definable in Presburger arithmetic (Theorem 2). This formula is used to prove the following facts: (1) given a finite synchronous automaton recognizing a set of n-tuples of integers written in positional notation one can effectively decide whether this set is definable in Presburger arithmetic; (2) every predicate (set of n-tuples of integers) recognizable in two essentially different positional systems is definable in Presburger arithmetic. The last result was proved by Cobham (Math. Systems Theory, 3(2) (1969) 186) for the case n = 1. In general case both (1) and (2) were proved by Semenov (Ph.D. Thesis, Moscow State University; Siberian Math. J. 18(2) (1977) 403) (Semenov's proofs are very difficult). (C) 2002 Elsevier Science B.V. All rights reserved.
definability presburger arithmetic cobham-semenov theorem