Consider an (m + 1)-ary relation R over the set N of natural numbers. Does there exist an arithmetical formula φ(a0,...,am,x1,...,xκ), not involving universal quantifiers, negation, or implication, such that the 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 prim- itive symbols of the arithmetical signature, the graph R of any primi- tive recursive function is representable; but can representability be reconciled with univocity without calling into play one extra operation, namely ⟨b , n⟩ 7→ bn (maybe with a fixed integer value > 1 for 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.
