Weakly maximal decidable structures

LACL Technical Report 2007-06

WEAKLY MAXIMAL DECIDABLE STRUCTURES

`s 1 and Patrick Ce ´gielski 1 Alexis Be Abstract. We prove that there exists a structure M whose monadic second order theory is decidable, and such that the elementary theory of every expansion of M by a constant is undecidable.

hal-00155281, version 1 - 17 Jun 2007

1991 Mathematics Subject Classification. 03B25, 03C57, 03D05.

Introduction In [3], Elgot and Rabin ask whether there exist maximal decidable structures, i.e. structures M whose elementary theory is decidable and such that the elementary theory of any expansion of M by a non-definable predicate is undecidable. As far as we know, the only related results were obtained by Soprunov in [8], where he proves (by a forcing argument) that every structure in which a regular ordering is interpretable is not maximal. A partial ordering (B,