On diophantine singlefold specifications

Abstract

Consider an (m+1)-ary relation over the set N of natural numbers. Does there exist an arithmetical formula ⏀i(a₀,...,a_m,x₁,...,x_k), not involving universal quantifiers, negation, or implication,
such that representation and univocity conditions are met by each tuple in N^m+1 ?

Even if solely addition and multiplication operators (along with the equality relator and with positive integer constants) are adopted as primitive symbols of the arithmetical signature, the graph of any primitive recursive function is representable; but can representability be reconciled with univocity without calling into play one extra operation, namely ⟨b , n⟩ → bⁿ ? As a preparatory step toward a hoped-for positive answer to this issue, one may consider replacing the exponentiation operator by any exponential-growth relation.

We discuss the said univocity, aka `singlefold-ness', issue–first raised by Yuri Matiyasevich in 1974–, framing it in historical context. Moreover, we spotlight eight exponential-growth relation any of which, if Diophantine, could supersede exponentiation in our quest.