There exists a non-recursively enumerable subset of N which has a short description in terms of arithmetic

Let [\cdot] denote the integer part of the argument. We show that decision problems (1)-(3) are algorithmically undecidable when n∈N. (1) ∃p,q∈N ((n=2^p \cdot 3^q)∧∀(x_0,...,x_p)∈N^{p+1} ∃(y_0,...,y_p)∈{0,...,q}^{p+1} ∀i,j,k∈{0,...,p} (((x_j+1=x_k)⇒(y_j+1=y_k))∧((x_i \cdot x_j=x_k)⇒(y_i \cdot y_j=y_k)))). (2) ∀(x_0,...,x_{n−[\sqrt{n}]^2})∈N^{n+1−[\sqrt{n}]^2} ∃(y_0,...,y_{n−[\sqrt{n}]^2})∈{0,...,|n−[\sqrt{n}]^2−[\sqrt{n}]|}^{n+1-[\sqrt{n}]^2} ∀i,j,k∈{0,...,n−[\sqrt{n}]^2} (((x_j+1=x_k)⇒(y_j+1=y_k))∧((x_i \cdot x_j=x_k)⇒{y_i \cdot y_j=y_k))). (3) ∃(y_0,...,y_n)∈N^{n+1} ∀i,j,k∈{0,...,n} (((2^{2^{2^j \cdot 3^k}}+1 divides n) ⇒ (y_j+1=y_k))∧((2^{2^{2^i \cdot 3^j \cdot 5^{k+1}}}+1 divides n)⇒(y_i \cdot y_j=y_k))). We prove that the sets {n∈N: n satisfies condition (1)} and {n∈N: n satisfies condition (2)} are not recursively enumerable. We prove that the set {n ∈N: n does not satisfy condition (3)} is not recursively enumerable. For n∈N, let E_n={1=x_k, x_i+x_j=x_k, x_i \cdot x_j=x_k: i,j,k∈{0,...,n}}. For n∈N, f(n) denotes the smallest b∈N such that if a system of equations S⊆E_n has a solution in N^{n+1}, then S has a solution in {0,...,b}^{n+1}. The author proved earlier that the function f:N→N is computable in the limit and eventually dominates every computable function g:N→N. We present a short program in MuPAD which for n∈N prints the sequence {f_i(n)}_{i=0}^∞ of non-negative integers converging to f(n). For n∈N, β(n) denotes the smallest b∈N such that if a system of equations S⊆E_n has a unique solution in N^{n+1}, then this solution belongs to {0,...,b}^{n+1}. The author proved earlier that the function β:N→N is computable in the limit and eventually dominates every function δ:N→N with a single-fold Diophantine representation. We present a short program in MuPAD which for n∈N prints the sequence {β_i(n)}_{i=0}^∞ of non-negative integers converging to β(n). Supplementary Material File (a_tyszka_mar_16.pdf) - Download - 611.27 KB Information & Authors Information Version history Copyright This work is licensed under a Non Exclusive No Reuse License.

Authors Metrics & Citations Metrics Article Usage 101views 37downloads Citations Download citation Apoloniusz Tyszka. There exists a non-recursively enumerable subset of N which has a short description in terms of arithmetic. Authorea. 17 March 2026. DOI: https://doi.org/10.22541/au.177377142.25850015/v1 DOI: https://doi.org/10.22541/au.177377142.25850015/v1 If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download. For more information or tips please see 'Downloading to a citation manager' in the Help menu.