Statements and open problems on decidable sets \mbox{${\mathcal X} \subseteq \N$} that contain informal notions and refer to the current knowledge on ${\mathcal X}$
Apoloniusz Tyszka · Creative Mathematics and Informatics · 2023
For a set \mbox{${\mathcal X} \subseteq \N$} whose infiniteness is false or unproven, we define which elements of ${\mathcal X}$ are classified as known. No known set \mbox{${\mathcal X} \subseteq \N$} satisfies Conditions~{\tt (1)-(4)} and is widely known in number theory or naturally defined, where this term has only informal meaning. {\em {\tt (1)}~A~known algorithm with no input returns an integer $n$ satisfying \mbox{${\rm card}({\mathcal X}) \omega \Rightarrow$} \mbox{${\mathcal X} \subseteq (-\infty,n]$}. {\tt (2)}~A~known algorithm for every \mbox{$k \in \N$} decides whether or not \mbox{$k \in {\mathcal X}$}. {\tt (3)}~No known algorithm with no input returns the logical value of the statement \mbox{${\rm card}({\mathcal X})=\omega$}. {\tt (4)}~There are many elements of~${\mathcal X}$ and it is conjectured, though so far unproven, that ${\mathcal X}$ is infinite. {\tt (5)} ${\mathcal X}$ is naturally defined. The infiniteness of ${\mathcal X}$ is false or unproven. ${\mathcal X}$ has the simplest definition among known sets \mbox{${\mathcal Y} \subseteq \N$} with the same set of known elements.} The set \mbox{${\mathcal X}=\{n \in \N:$} \mbox{$the~interval~[-1,n]~contains~more~than$} \mbox{$29.5+\frac{\textstyle 11!}{\textstyle 3n+1} \cdot \sin(n)~primes~of~the~form~k!+1\}$} satisfies Conditions~{\tt (1)-(5)} except the requirement that ${\mathcal X}$ is naturally defined. \mbox{$501893 \in {\mathcal X}$}. Condition~{\tt (1)} holds with \mbox{$n=501893$}. \mbox{${\rm card}({\mathcal X} \cap [0,501893])=159827$}. \mbox{${\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 $ eg$ or the absence of any symbol. No set \mbox{${\mathcal X} \subseteq \N$} will satisfy Conditions~{\tt (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.