Abstract

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