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.
ON DIOPHANTINE SINGLEFOLD SPECIFICATIONS
Eugenio OmodeoUltimo
2024-01-01
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
CCO24.pdf
accesso aperto
Tipologia:
Documento in Versione Editoriale
Licenza:
Creative commons
Dimensione
364.16 kB
Formato
Adobe PDF
|
364.16 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.