UNDECIDABLE EXTENSIONS OF SKOLEM ARITHMETIC

Let <(P2) be the restriction of usual order relation to integers which are primes or squares of primes. and let perpendicular to denote the coprimeness predicate. The elementary theory of [N; perpendicular to, <(P2)] is undecidable. Now denote by <n the restriction of order to pr imary numbers. All arithmetical relations restricted to primary number s are definable in the structure [N; perpendicular to, <(n)]. Furtherm ore, the structures [N; \, <(n)], [N; =, x, <(n)] and [N; =, +, x] are interdefinable.