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

We present a formula F(x,n) in Peano arithmetic from J. P. Jones' article published in 1978. From the results of this article, it follows that the set {n∈N ¬F(n,n)} is non-recursively enumerable and co-recursively enumerable. We prove that the set W={n∈N: ∃p,q∈N ((2n=(p+q)(p+q+1)+2q) ∧ ∀(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)) ∧ (∀i,j,k∈{0,...,p} (x_i \cdot x_j=x_k ⇒ y_i \cdot y_j=y_k))))} is not recursively enumerable. We prove that the set N\W is 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)))). This formula can be easily translated into a formula in Peano arithmetic.

Authors

Publication Details

Published
2026-05-29
DOI
https://doi.org/10.33774/coe-2025-bdt48-v7
Primary Topic
Mathematical and Theoretical Analysis
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

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

Apoloniusz Tyszka
Mathematical and Theoretical Analysis
article

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

Apoloniusz Tyszka
article en

Abstract

We present a formula F(x,n) in Peano arithmetic from J. P. Jones' article published in 1978. From the results of this article, it follows that the set {n∈N ¬F(n,n)} is non-recursively enumerable and co-recursively enumerable. We prove that the set W={n∈N: ∃p,q∈N ((2n=(p+q)(p+q+1)+2q) ∧ ∀(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)) ∧ (∀i,j,k∈{0,...,p} (x_i \cdot x_j=x_k ⇒ y_i \cdot y_j=y_k))))} is not recursively enumerable. We prove that the set N\W is 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)))). This formula can be easily translated into a formula in Peano arithmetic.

Openalex Percentile: Top 3%
Mathematical and Theoretical Analysis
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.