Let us assume there is a number which is well-defined and computable, but it is hard to compute it. E.g., $x=\pi^{(\pi^{(\pi^\pi)})}$. It is not even known if the given number is an integer (which is actually true for the chosen $x$). And it is not known if the expression is equal to a prime number (a prime of $\mathbb{N}$).

My question is now: Can it be the case that it is undecidable (in ZFC) if the given expression for $x$ is equal to a prime number? Or is this for all (computable) expressions deciable?

If someone computes this expression to a given accuracy it might be de the case that it ends in something like "...2113.12131...". Then it obviously is not an integer (and therefore not a prime). But what if the expression ends (given any accuracy we choose during the experiments) with ".2113.000000..." or with "...2112.99999...". Then it might be really hard to prove that the expression is an integer (and then maybe a prime number) or not. Can it be that it is not even deciable? Even if the expression itself is computable?

Thank you

  • 1
    $\begingroup$ If the given expression is NOT an integer, this can always be proven because a given accuracy will show it. If it is however an integer (which is very unlikely for the given number), I am not sure. For an integer, ZFC can always decide whether it is prime. Considering the magnitude, it is quite unlikely that the given expression is a prime even if it is an integer. $\endgroup$ – Peter May 21 '18 at 20:16
  • $\begingroup$ From a practical point of view, there are expressions for which we will never know whether they are integers. And there also are integers from which we will never know whether they are prime or not. $\endgroup$ – Peter May 21 '18 at 20:20
  • $\begingroup$ The formulation "which is actually true ... " is somethat confusing. $\endgroup$ – Peter May 21 '18 at 20:23

First: If it's decidable whether it's an integer, it's decidable whether it's prime - just compute the number to a high enough precision to decide which integer it is, and check whether that's prime.

Second: It's not decidable whether a given expression encodes an integer. Let $x = \sum_{n = 1}^{\infty}p(n)2^{-n}$, where $p(n)$ is defined to be $1$ if $n$ is the Godel number of a proof in ZFC of $1 = 0$ and $0$ otherwise. Clearly, $x$ is $0$ if ZFC is consistent, and is some number strictly between $0$ and $1$ otherwise. Since ZFC can't prove whether ZFC is consistent (assuming, for the moment, that ZFC actually is consistent) ZFC cannot prove whether $x$ is an integer.

  • $\begingroup$ Thanks for the answer:)! I thought there might be something more advanced for "simpler" expressions where only "well-known" numbers like $\pi$ and operations like exponentiation are used. But I guess even for this case, there is nothing better known:)! Thanks $\endgroup$ – Kevin Meier May 21 '18 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.