Statements and open problems on decidable sets X \subseteq N that contain informal notions and refer to the current knowledge on X

 Tyszka, Apoloniusz

Full PDF


For a set {\mathcal X} \subseteq {\mathbb N} whose infiniteness is false or unproven, we define which elements of {\mathcal X} are classified as known. No known set {\mathcal X} \subseteq {\mathbb N} satisfies Conditions~ (1)-(4) and is widely known in number theory or naturally defined, where this term has only informal meaning.
(1)~A~known algorithm with no input returns an integer n satisfying
{\rm card}({\mathcal X})<\omega \Rightarrow {\mathcal X} \subseteq (-\infty,n].
(2)~A~known algorithm for every \mbox{k \in \N} decides whether or not k \in {\mathcal X}.
(3)~No known algorithm with no input returns the logical value of the statement {\rm card}({\mathcal X})=\omega.
(4)~There are many elements of~{\mathcal X} and it is conjectured, though so far unproven, that {\mathcal X} is infinite.
(5) {\mathcal X} is naturally defined. The infiniteness of {\mathcal X} is false or unproven.
{\mathcal X} has the simplest definition among known sets {\mathcal Y} \subseteq {\mathbb N} with the same set of known elements.
The set {\mathcal X}=\{n \in {\mathbb N}: the~interval~[-1,n]~contains~more~than 29.5+\frac{\textstyle 11!}{\textstyle 3n+1} \cdot \sin(n)~primes~of~the~form~k!+1\}
satisfies Conditions~(1)-(5) except the requirement that {\mathcal X} is naturally defined. 501893 \in {\mathcal X}. Condition~{\tt (1)} holds with n=501893. {\rm card}({\mathcal X} \cap [0,501893])=159827. {\mathcal X} \cap [501894,\infty)=\{n \in \N: the interval [-1,n] contains at least 30 primes of the form k!+1\}. We present a table that shows satisfiable conjunctions of the form \#{\rm (Condition}~{\tt 1}{\rm )} \wedge {\rm (Condition}~{\tt 2}{\rm )} \wedge \#{\rm (Condition}~{\tt 3}{\rm)} \wedge {\rm (Condition}~ {\tt 4}{\rm )}\wedge \#{\rm (Condition}~{\tt 5}{\rm )}, where \# denotes the negation \neg or the absence of any symbol.
No set {\mathcal X} \subseteq {\mathbb N} will satisfy Conditions~ (1)-(4) forever, if for every algorithm with no input,at some future day, a computer will be able to execute this algorithm in 1~second or less.




Additional Information


 Tyszka, Apoloniusz