A strong version of Cobham’s theorem

Abstract: Let

k, e l l g e q 2

be two multiplicatively independent integers. Cobham's famous theorem states that a set

X s u b s e t e q m a t h b b N

is both

k

-recognizable and

e l l

-recognizable if and only if it is definable in Presburger arithmetic. Here we show the following strengthening: let

X s u b s e t e q m a t h b b N^{m}

be

k

-recognizable, let

Y s u b s e t e q m a t h b b N^{m}

be

e l l

-recognizable such that both

X

and

Y

are not definable in Presburger arithmetic. Then the first-order logical theory of

(m a t h b b N, +, X, Y)

is undecidable. This is in contrast to a well-known theorem of B"uchi that the first-order logical theory of

(m a t h b b N, +, X)

is decidable.

Cited in

(11)

This page was built for publication: A strong version of Cobham’s theorem