Answer to a problem raised by J. Robinson: The arithmetic of positive or negative integers is definable from successor and divisibility. (English) Zbl 0612.03009

Richard, Denis

J. Symb. Log. 50, 927-935 (1985).

Julia Robinson proved that in the positive integers \(+\) and \(\cdot\) are definable from S and \(|\) where S is the successor function and \(|\) is the divisibility relation. The author extends this result to Z, the set of positive and negative integers. As a corollary he gets that the theory of (Z,S,\(|)\) is undecidable. An important tool in the proof is a number theoretic result originally due to Zsigmondy and rediscovered by Birkhoff and Vandiver.
From the author’s introduction: ”First we \(\{\) S,\(| \}\)-define the relation \(z=\pm xy\); to this effect we have to develop some sort of finite set theory (in Ackermann’s way) via some codings depending heavily on the ZBV-theorem. Then we \(\{\) S,\(| \}\)-define a subset of the multiplication which suffices to get an \(\{\) S,\(| \}\)-definition of the whole addition. Lastly using Lagrange’s theorem we get the relation \(x\geq 0\) and the principal result”.

Reviewer: J.M.Plotkin

MSC:

03B25	Decidability of theories and sets of sentences
11U05	Decidability (number-theoretic aspects)

Keywords:

arbitrary integers; successor function; divisibility

References:

[1]	DOI: 10.1007/BF01692444 · JFM 24.0176.02 · doi:10.1007/BF01692444
[2]	Definability and decision problems in arithmetic 14 pp 98– (1949) · Zbl 0034.00801
[3]	A mathematical introduction to logic (1970)
[4]	Proceedings of the Cambridge Philosophical Society 58 pp 555– (1962)
[5]	Orders: description and roles 23 pp 287– (1984)
[6]	Comptes Rendus des Séances de l’Académie des Sciences. Série I: Mathématique 294 pp 143– (1982)
[7]	DOI: 10.2307/2007263 · JFM 35.0205.01 · doi:10.2307/2007263
[8]	Discrete Mathematics (1982) · Zbl 0531.00010