UNDECIDABLE EXTENSIONS OF SKOLEM ARITHMET IC

Let < p(2) be the restriction of usual order relation to integers whic h are primes or squares of a prime, and let perpendicular to denote th e coprimeness predicate. The elementary theory of [N; perpendicular to , < p(2)] is undecidable. Now denote by < (Pi) the restriction of orde r to primary numbers. All arithmetical relations restricted to primary numbers are definable in the structure [N; perpendicular to, < (Pi)]. Furthermore, the structure [N; \, < (Pi)], [N; =, x, < (Pi)] adn [N; =, x, +] are inter-definable.