Stephen George Simpson. with definition 1.2.3 and the discussion following it. For example, taking 90(n) to be the formula n §E Y, we have an instance of comprehension, VYEIXVn(n€X<—>n¢Y), asserting that for any given set Y there exists a ...

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.

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.

We give a simple proof characterizing the complexity of Presburger arithmetic augmented with additional predicates. We show that Presburger arithmetic with additional predicates is Π 1 1 complete. Adding one unary predicate is enough to get Π 1 1 hardness, while adding more predicates (of any arity) does not make the complexity any worse.

In this paper, we are concerned with the arithmetical definability of certain notions of integers and rationals in terms of other notions. The results derived will be applied to obtain a negative solution of corresponding decision problems.In Section 1, we show that addition of positive integers can be defined arithmetically in terms of multiplication and the unary operation of successorS(whereSa=a+ 1). Also, it is shown that both addition and multiplication can be defined arithmetically in terms of successor and the relation (...) of divisibility | (wherex|ymeansxdividesy). (shrink)