Tuesday, September 12, 2017

Numerical experimentation and truth in mathematics

Is mathematics about proof or truth?

Sometimes mathematicians perform numerical experiments with computers. Goldbach’s Conjecture says that every even integer n greater than two is the sum of two primes. Numerical experiments have been performed that verified that this is true for every even integer from 4 to 4 × 1018.

Let G(n) be the statement that n is the sum of two primes, and let’s restrict ourselves to talking about even n greater than two. So, we have evidence that:

1. For an impressive sample of values of n, G(n) is true.

This gives one very good inductive evidence that:

1. For all n, G(n) is true.

And hence:

1. It is true that: for all n, G(n). I.e., Goldbach’s Conjecture is true.

Can we say a similar thing about provability? The numerical experiments do indeed yield a provability analogue of (1):

1. For an impressive sample of values of n, G(n) is provable.

For if G(n) is true, then G(n) is provable. The proof would proceed by exhibiting the two primes that add up to n, checking their primeness and proving that they add up to n, all of which can be done. We can now inductively conclude the analogue of (2):

1. For all n, G(n) is provable.

But here is something interesting. While we can swap the order of the “For all n” and the “is true” operator in (2) and obtain (3), it is logically invalid to swap the order of the “For all n” and the “is provable” operator (5) to obtain:

1. It is provable that: for all n, G(n). I.e., Goldbach’s Conjecture is provable.

It is quite possible to have a statement such that (a) for every individual n it is provable, but (b) it is not provable that it holds for every n. (Take a Goedel sentence g that basically says “I am not provable”. For each positive integer n, let H(n) be the statement that n isn’t the Goedel number of a proof of g. Then if g is in fact true, then for each n, H(n) is provably true, since whether n encodes a proof of g is a matter of simple formal verification, but it is not provable that for all n, H(n) is true, since then g would be provable.)

Now, it is the case that (5) is evidence for (6). For there is a decent chance that if Goldbach’s conjecture is true, then it is provable. But we really don’t have much of a handle on how big that “decent chance” is, so we lose a lot of probability when we go from the inductively verified (5) to (6).

In other words, if we take the numerical experiments to give us lots of confidence in something about Goldbach’s conjecture, then that something is truth, not provability.

Furthermore, even if we are willing to tolerate the loss of probability in going from (5) to (6), the most compelling probabilistic route from (5) to (6) seems to take a detour through truth: if G(n) is provable for each n, then Goldbach’s Conjecture is true, and if it’s true, it’s probably provable.

So the practice of numerical experimentation supports the idea that mathematics is after truth. This is reminiscent to me of some arguments for scientific realism.