
doi: 10.4418/2024.79.2.18
handle: 11368/3101478
Summary: Consider an \((m+1)\)-ary relation \(\mathcal{R}\) over the set \(\mathbb{N}\) of natural numbers. Does there exist an arithmetical formula \(\varphi (a_0, \ldots, a_m, x_1, \ldots, x_k)\), not involving universal quantifiers, negation, or implication, such that representation and univocity conditions, viz., \[ \begin{aligned} \mathcal{R}(\boldsymbol{\vec{a}}) \Leftrightarrow \exists x_1 \cdots \exists x_k \varphi (\boldsymbol{\vec{a}}, x_1, \ldots, x_k) \text{ and } \\ \exists x_1 \cdots \exists x_k \forall y_1 \cdots \forall y_k [\varphi (\boldsymbol{\vec{a}}, y_1, \ldots, y_k) \Rightarrow \&^k_{i=1} (y_i = x_i)], \end{aligned} \] are met by each tuple \(\boldsymbol{\vec{a}}=\langle\boldsymbol{a}_0, \ldots, \boldsymbol{a}_m\rangle \in \mathbb{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 \(\mathcal{R}\) of any primitive recursive function is representable; but can representability be reconciled with univocity without calling into play one extra operation, namely \(\langle b, n \rangle \mapsto b^n\) (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.
Recursively (computably) enumerable sets and degrees, rule-them-all equation, Heegner number, Undecidability and degrees of sets of sentences, singlefold/finitefold Diophantine representation, Hilbert’s 10th problem, Pell’s equation, Cubic and quartic Diophantine equations, Pell's equation, Hilbert’s 10th problem; exponential-growth relation; singlefold/finitefold Diophantine representation; rule-them-all equation; Pell’s equation; Heegner number, exponential-growth relation, Hilbert's \(10^{\text{th}}\) problem, Exponential Diophantine equations, Diophantine equations in many variables
Recursively (computably) enumerable sets and degrees, rule-them-all equation, Heegner number, Undecidability and degrees of sets of sentences, singlefold/finitefold Diophantine representation, Hilbert’s 10th problem, Pell’s equation, Cubic and quartic Diophantine equations, Pell's equation, Hilbert’s 10th problem; exponential-growth relation; singlefold/finitefold Diophantine representation; rule-them-all equation; Pell’s equation; Heegner number, exponential-growth relation, Hilbert's \(10^{\text{th}}\) problem, Exponential Diophantine equations, Diophantine equations in many variables
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
