Positive Existential Definability with Unit, Addition and Coprimeness
Mikhail R. Starchak · 2021
We consider positively existentially definable sets in the structure {Ζ; 1, +,⊥}. It is well known that the elementary theory of this structure is undecidable while the existential theory is decidable. We show that after the extension of the signature with the unary '-' functional symbol, binary symbols for dis-equality ≠ and GCD (.,.)=d for every fixed positive integer d, every positive existential formula in this extended language is equivalent in Ζ to some positive quantifier-free formula.