The definable criterion for definability in Presburger arithmetic and its applications

✍ Scribed by An.A. Muchnik

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 131 KB
• Volume: 290
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00047-6

✦ Synopsis

In Section 1 of present paper we construct a formula 'n(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 deÿnable in Presburger arithmetic (Theorem 2).

This formula is used to prove the following facts: (1) given a ÿnite synchronous automaton recognizing a set of n-tuples of integers written in positional notation one can e ectively decide whether this set is deÿnable in Presburger arithmetic; (2) every predicate (set of n-tuples of integers) recognizable in two essentially di erent positional systems is deÿnable 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 di cult).