There Exists a Subset of N Which Is Not Recursively Enumerable and Has a Short Description in Terms of Arithmetic
Abstract
We prove that the set {n∈N: ∃p,q∈N ((n=2^p \cdot 3^q) ∧ ∀(x_0,...,x_p)∈N^{p+1} ∃(y_0,...,y_p)∈{0,...,q}^{p+1} ((∀k∈{0,...,p} (1=x_k ⇒ 1=y_k)) ∧ (∀i,j,k∈{0,...,p} (x_i+x_j=x_k ⇒ y_i+y_j=y_k)) ∧ (∀i,j,k∈{0,...,p} (x_i \cdot x_j=x_k ⇒ y_i \cdot y_j=y_k))))} is not recursively enumerable.
Fields of Study & Subjects
Computability
Logic
AI Algorithms
Advanced Topology and Set Theory
semigroups and automata theory
Publication details
- Journal / source
- Preprints.org
- Publication date
- 27 February 2026
- Language
- EN
- Document type
- Preprint