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

Download Edit this record How to cite View on PhilPapers
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).
PhilPapers/Archive ID
Revision history
First archival date: 2017-10-17
Latest version: 102 (2020-02-09)
View upload history
References found in this work BETA

Add more references

Citations of this work BETA

No citations found.

Add more citations

Added to PP index

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.