There exists a subset of N which is not listable and has a short description in terms of arithmetic

Apoloniusz Tyszka

doi:10.33774/coe-2025-bdt48-v3

Mathematics

Search within Mathematics

There exists a subset of N which is not listable and has a short description in terms of arithmetic

26 February 2026, Version 3

Working Paper

Apoloniusz Tyszka

Show author details

This content is an early or alternative research output and has not been peer-reviewed by Cambridge University Press at the time of posting.

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 listable.

Keywords

arithmetic of N

computable function

eventual domination

Hilbert’s 10th problem

limit-computable function

listable subset of N

undecidable decision problem

Comments

Comments are not moderated before they are posted, but they can be removed by the site moderators if they are found to be in contravention of our Commenting and Discussion Policy - please read this policy before you post. Comments should be used for scholarly discussion of the content in question. You can find more information about how to use the commenting feature here .

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

useful sources of literature are indicated