Abstract

Let $ be the restriction of usual order relation to integers which are primes or squares of primes, and let ⊥ denote the coprimeness predicate. The elementary theory of $\langle\mathbb{N};\bot, , is undecidable. Now denote by $ the restriction of order to primary numbers. All arithmetical relations restricted to primary numbers are definable in the structure $\langle\mathbb{N};\bot, . Furthermore, the structures $\langle\mathbb{N};\mid, and $\langle\mathbb{N};=,+,x\rangle$ are interdefinable