# Open problems that concern computable sets X \subseteq \mathbb{N} and cannot be stated formally as they refer to the current mathematical knowledge and require that the finiteness (infiniteness) of X remains conjectured

**Abstract**

Let \beta=((24!)!)!, and let P_{n^2+1} denote the set of all primes of the form n^2+1. Let M denote the set of all positive multiples of elements of the set P_{n^2+1} \cap (\beta,\infty). The set X={0,...,\beta} \cup M satisfies the following conditions: (1) card(X) is greater than a huge positive integer and it is conjectured that X is infinite, (2) we do not know any algorithm deciding the finiteness of X, (3) a known and short algorithm for every n \in \mathbb{N} decides whether or not n \in X, (4) a known and short algorithm returns an integer n such that X is infinite if and only if X contains an element greater than n. The following problem is open: simply define a set X \subseteq \mathbb{N} such that X satisfies conditions (1)-(4), and FOR EVERY FINITE SET T, WE DO NOT KNOW ANY DEFINITION OF X \setminus T SIMPLER THAN THE DEFINITION OF X (5). Let f(3)=4, and let f(n+1)=f(n)! for every integer n \geq 3. For an integer n \geq 3, let \Psi_n denote the following statement: if a system of equations S \subseteq {x_i!=x_{i+1}: 1 \leq i \leq n-1} \cup {x_i \cdot x_j=x_{j+1}: 1 \leq i \leq j \leq n-1} has only finitely many solutions in positive integers x_1,...,x_n, then each such solution (x_1,...,x_n) satisfies x_1,...,x_n \leq f(n). We prove that for every statement \Psi_n the bound f(n) cannot be decreased. The author's guess is that the statements \Psi_3,...,\Psi_9 are true. We prove that the statement Psi_9 implies that the set X of all non-negative integers k whose number of digits belongs to P_{n^2+1} satisfies conditions (1)-(5).

**Keywords**

**Categories**

(categorize this paper)

**PhilPapers/Archive ID**

TYSDAS

**Revision history**

References found in this work BETA

Definability and Decision Problems in Arithmetic.Robinson, Julia

Citations of this work BETA

No citations found.

**Added to PP index**

2017-10-17

**Total views**

671 ( #4,670 of 46,155 )

**Recent downloads (6 months)**

325 ( #1,137 of 46,155 )

How can I increase my downloads?

**Downloads since first upload**

*This graph includes both downloads from PhilArchive and clicks to external links.*