×

On explicit definability in arithmetic. (English) Zbl 1107.03042

Enayat, Ali (ed.) et al., Logic in Tehran. Proceedings of the workshop and conference on logic, algebra and arithmetic, Tehran, Iran, October 18–22, 2003. Wellesley, MA: AK Peters (ISBN 1-56881-296-5/pbk; 1-56881-295-7/hbk). Lecture Notes in Logic 26, 65-86 (2006).
Summary: We characterize the arithmetic functions in one variable that are explicitly definable from the familiar arithmetic operations. This characterization is deduced from algebraic properties of some nonstandard rings of integers. Elementary model theory is also used to show that the greatest common divisor function and related functions are not explicitly definable from the usual arithmetic operations. It turns out that explicit definability is equivalent to computability with bounded complexity, for the recursive algorithms of Y. Moschovakis and with respect to a certain natural cost function.
For the entire collection see [Zbl 1094.03004].

MSC:

03C98 Applications of model theory
03D15 Complexity of computation (including implicit computational complexity)
11A05 Multiplicative structure; Euclidean algorithm; greatest common divisors
11U09 Model theory (number-theoretic aspects)
PDFBibTeX XMLCite