Kurpaska, Sławomir and Tyszka, Apoloniusz
(2020)
Open problems that concern computable sets X \subseteq N and cannot be formalized in ZFC as they refer to current knowledge about X.
[Preprint]
Abstract
Conditions (1)(8) below concern sets X \subseteq N. (1) There are a large number of elements of X and it is conjectured that X is infinite. (2) No known algorithm decides the finiteness of X. (3) There is a known algorithm that for every n \in N decides whether or not n \in X. (4) There is an explicitly known integer n such that card(X)< \omega ==> X \subseteq (\infty,n]. (5) X is widely known in number theory. (6) There is no known equality X=X_1 \cup X_2, where X_1 and X_2 are defined simpler than X. (7) No known set Y is defined simpler than X and satisfies (Y \subseteq X) \wedge (card(X\Y)< \omega). (8) No known set Y is defined simpler than X and satisfies card((X\Y) \cup (Y\X))<\omega. We do not know any set X \subseteq N that satisfies conditions (1)(4) and (5). The same is true, if condition (5) is replaced by condition (6) or (7) or (8). For every explicitly known integer n, some simply defined set X \subseteq N includes the set (\infty,n] \cap N and satisfies conditions (1)(4). Let P_{n^2+1} denote the set of primes of the form n^2+1. The set X=P_{n^2+1} satisfies conditions (1)(3) and (5)(8). The set X={k \in N: the number of digits of k belongs to P_{n^2+1}} contains 10^{10^{450}} consecutive integers and satisfies conditions (1)(3) and (6)(8). Some hypothetical statement implies that these sets X satisfy condition (4).
Available Versions of this Item

Open problems that concern computable sets X \subseteq N and cannot be formalized in ZFC as they refer to current knowledge about X. (deposited 21 Apr 2020 15:31)
[Currently Displayed]
Monthly Views for the past 3 years
Monthly Downloads for the past 3 years
Plum Analytics
Actions (login required)

View Item 