3
$\begingroup$

Here is a question that popped into my head right as I fell asleep last night.

I was thinking about constructions of irrational numbers, like pi. I was wondering if there are two constructions (any constructions, the pair doesn't have to include pi itself) such that:

  1. We have good reason to believe they are different numbers.
  2. We have a demonstration that, if they are in fact different, then their difference must be small enough that there is no way we will ever find this difference. By this I mean, the number of calculations it would take to find the difference would take more computational resources than the energy of the Universe would allow.

Heads up, I'm an amateur computer science enthusiast, and am neither a mathematician nor a physicist, but this question involves a mix of all three, so some of the phrasing might be awkward, and the whole question could be conceptually confused. If you think it is, please let me know!

The inspiration for this question comes from reading about hash functions in software version control. It seems like one of the reasons that numbers are "useful" from a computational standpoint, is that they are easy to compare for equality. This probably has something to do with the ease with which they are placed in order. So the puzzle I was pondering was, if we know that numbers can be ordered by definition, do we also have numbers that we can't, in physical reality, put into an order?

Is this question reducible to some incompleteness argument? Has it been asked before? Apologies if this is too open-ended a question for Math Overflow. Any and all suggestions would be greatly appreciated.

$\endgroup$
7
  • $\begingroup$ What exactly do you mean by "find the difference"? $\endgroup$
    – user76284
    Apr 12, 2020 at 0:10
  • $\begingroup$ Since you can code proofs with numbers, you say that one number is, e.g. $\pi$ while the other is $\pi + \sum_i a_i/10^i$ where $a_i =1$ if the $i$ corresponds to a proof that $0=1$ (in ZFC say) and $a_i =0$ otherwise. Then you probably cannot prove (in ZFC) that these two numbers are distinct. $\endgroup$
    – ARG
    Apr 12, 2020 at 9:13
  • $\begingroup$ @user76284 you make a good point, that language is misleading/ambiguous. What I meant to say was, "we'd never find the first decimal at which point the two numbers were not equal". So, it would always look to anyone who was calculating the numbers as if they were equal up to that point. From your answer down below, I realized how the question I originally posed could also be interpreted as asking "will we ever find the exact value of their difference", which is an equally interesting question! I'll respond in more detail to your answer when I get a moment to follow up today. Thanks! $\endgroup$
    – Max Wall
    Apr 12, 2020 at 11:37
  • $\begingroup$ @ARG But do we have good reason to believe they are different numbers (i.e. that ZFC is inconsistent)? Also, to be precise, if ZFC is consistent it can’t prove they’re the same, but if it is inconsistent it can prove they’re distinct (since it can prove anything). $\endgroup$
    – user76284
    Apr 12, 2020 at 18:40
  • $\begingroup$ @MaxWall Does 0 and the reciprocal of googolplex satisfy your criteria? $\endgroup$
    – user76284
    Apr 12, 2020 at 23:36

2 Answers 2

10
$\begingroup$

I think standard examples are like this ... Enumerate the cases of Goldbach's conjecture. Let $a_n = 0$ if the $n$th case is true, and $a_n = 1$ if false. Consider the number $A = \sum_{k=1}^\infty a_k 2^{-k}$ with the binary expansion $(a_n)$. We may compute $A$ as accurately as we like. But $A=0$ is equivalent to Goldbach's conjecture.

Repeat this with many other undecidable propositions instead of Goldbach.

$\endgroup$
4
  • 2
    $\begingroup$ But this example can die if/when Goldbach's conjecture is ever settled. Maybe better to take $a_n=1$ if the $nth$ case of Goodstein's Theorem is true. Then we know first that $A=1$, and second that with the tools of ZFC, we will never be able to prove it. And we can be pretty confident that for we will never have the computational resources to distinguish $A$ from, $1-\epsilon$ where $\epsilon$ is, say, 1/10^10^10. $\endgroup$ Apr 11, 2020 at 16:51
  • 1
    $\begingroup$ Gerald's Goldbach example absolutely captures the intuition I was trying to express, but I have one small concern. While Goldbach is unproven, isn't the intuition that it's likely true? So wouldn't condition 1 of my question be unsatisfied? That we have no reason to think A is not zero? Maybe condition 1 is too vague (what is a good reason?)... I love the Goodstein idea too (new to me), and I think it captures more of the flavor of my second condition, but doesn't it suffer from the same problem? These are both great, by the way! Thanks! $\endgroup$
    – Max Wall
    Apr 11, 2020 at 17:57
  • 2
    $\begingroup$ @StevenLandsburg ZFC proves Goodstein's theorem - it's only undecidable in PA. Of course, using Gödel's theorem you can do a similar thing for ZFC or any other theory $\mathcal{T}$ to which Gödel's theorem applies, by encoding "n is not the Gödel number of a proof of 0=1 in $\mathcal{T}$". $\endgroup$ Apr 11, 2020 at 20:03
  • $\begingroup$ @RoberFurber: Gah. Yes, I meant to say PA. Thanks. $\endgroup$ Apr 12, 2020 at 2:59
4
$\begingroup$

I think your question needs some clarification (in particular, what you mean by "find the difference"). Let $x$ be Chaitin's constant for some prefix-free universal computable function.

  1. We have good reason to believe $x$ and 0 are different numbers (because they are, in fact, different numbers).

  2. Their difference $x - 0$ is uncomputable, so in a sense we will never "find the difference". (A real number is computable iff its Dedekind cut is at level $\Delta_1$ of the arithmetical hierarchy.)

Another example: Let $x$ be a super-omega. Then $x - 0$ is not even limit-computable (i.e., in $\Delta_2$).

Another example: Fix an enumeration of first-order formulas that define arithmetical sets. Consider the real number $x \in [0, 1]$ whose $n$th binary digit after the decimal point is 1 iff $n$ is not in the set defined by the $n$th formula. Then $x - 0$ is not even arithmetical. (See here.)


Alternatively, we could use a construction analogous to Rayo's number: Fix a theory T. Let $\varepsilon$ be a positive real number smaller than any positive real number that can be named by an expression in the language of T with at most googolplex symbols. Then, by definition, there does not exist a positive real number $\delta$ that can be named by an expression with at most googolplex symbols which lower-bounds $\varepsilon$:

$$ 0 < \delta < \varepsilon$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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