The set {(1/2)(p+q)(p+q+1)+q: (p,q∈N)∧(∀x_0,...,x_p∈N ∃y_0,...,y_p∈{0,...,q} ∀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)))} is not recursively enumerable
Let F(x,n) denote the formula ∃ab ∀i⩽n ∃swpq ∀jv ∃eg {(s+w)^2+3w+s=2i ∧ ⟨[j=w ∨ v=q] ∨ [j=3i ∧ v=p+q] ∨ [j=s ∧ (v=p ∨ (i=n ∧ v=q+x))] ∨ [j=3i+1 ∧ v=pq] ⇒ a=v+e+ejb ∧ v+g=b⟩} from J. P. Jones' article in vol. 43 of J. Symbolic Logic. From the results of Jones' article, it follows that the set J={n∈N: ¬F(n,n)} is co-recursively enumerable and not recursively enumerable. We prove that the set W={(1/2)(p+q)(p+q+1)+q: (p,q∈N)∧∀(x_0,...,x_p)∈N^{p+1} ∃(y_0,...,y_p)∈{0,...,q}^{p+1} ((∀j,k∈{0,...,p} (x_j+1=x_k ⇒ y_j+1=y_k)) ∧ (∀i,j,k∈{0,...,p} (x_i \cdot x_j=x_k ⇒ y_i \cdot y_j=y_k)))} is co-recursively enumerable and not recursively enumerable. Let β:N^3→N denote Gödel's β function. For x_1,x_2,x_3∈N, β(x_1,x_2,x_3) equals the remainder after integer division of x_1 by 1+(x_3+1) \cdot x_2. We prove that the set W consists of all n∈N such that ∀u,v∈N ∃a,b,p,q∈N ((2n=(p+q)(p+q+1)+2q) ∧ ∀i,j,k∈{0,...,p} ((β(a,b,i)⩽q) ∧ (β(u,v,j)+1=β(u,v,k) ⇒ β(a,b,j)+1=β(a,b,k)) ∧ (β(u,v,i) \cdot β(u,v,j)=β(u,v,k) ⇒ β(a,b,i) \cdot β(a,b,j)=β(a,b,k)))). We express the above formula in Peano arithmetic.
Authors
- Apoloniusz Tyszka (ORCID: https://orcid.org/0000-0002-2770-5495)
Institutions
- University of Agriculture in Krakow (PL)
Publication Details
- Published
- 2026-11-17
- DOI
- https://doi.org/10.33774/coe-2025-bdt48-v11
- Primary Topic
- Computability, Logic, AI Algorithms
- Type
- preprint