creative_2023_32_2_247_253_001

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

creative_2023_32_2_247_253

For a set {\mathcal X} \subseteq \N whose infiniteness is false or unproven, we define which elements of {\mathcal X} are classified as known. No known set {\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.
{\tt (1)}~A~known algorithm with no input returns an integer n satisfying
{\rm card}({\mathcal X})<\omega \Rightarrow {\mathcal X} \subseteq (-\infty,n].
{\tt (2)}~A~known algorithm for every \mbox{k \in \N} decides whether or not k \in {\mathcal X}.
{\tt (3)}~No known algorithm with no input returns the logical value of the statement {\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 {\mathcal Y} \subseteq \N with the same set of known elements.
The set {\mathcal X}=\{n \in \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~{\tt (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 \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.

 

 

 

Additional Information

Author(s)

 Tyszka, Apoloniusz