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 Omodeo
Ultimo
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 in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11368/3101478
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact