Is it possible for a statement about natural numbers not to be provable, but can be proved for any concrete natural number?

144 Views Asked by At

I am pretty sure there are statements about natural numbers that cannot be proven. But is there a statement that can be proven for any concrete natural number and cant be proven in general.

For example, Goldbach conjecture says that every even number greater than 2 can be written as sum of two prime numbers. As far as i know we dont know if Goldbach conjecture is provable. But if we take concrete number lets say 2425582 than we can check if it can be written as sum of two primes in finitely many steps.

Another example that comes to mind is not about natural numbers, but its also interesting. That is continuum hypothesis. It is proven that it can not be proven in ZF, but here I dont see a way for a concrete set $S$ how we could determine if its cardinality is strictly greater than $\aleph_0$ and strictly smaller than $c$.

1

There are 1 best solutions below

2
On BEST ANSWER

Goldbach's conjecture and $\text{Con}(ZFC)$ are both examples of what I believe are called $\Pi_1^0$ statements, meaning they are arithmetic statements of the form $\forall n : P(n)$ where $P(n)$ is a statement about a natural number $n$ that can be verified by a finite computation. In the Goldbach conjecture case $P(n)$ says that e.g. $2n + 2$ can be written as the sum of two primes, and in the $\text{Con}(ZFC)$ case $P(n)$ says that $n$ is not the Gödel number of a proof of a contradiction in ZFC.

A general fact about $\Pi_1^0$ statements is that they are either provably true, true but unprovable, or provably false (so they cannot be false but unprovable). The reason is that if they are false then there is a specific natural number $n$ which provides a counterexample to them, and then writing this natural number down and verifying that $P(n)$ is not true constitutes a disproof.

However, it is possible for $\Pi_1^0$ statements, such as Goldbach's conjecture and $\text{Con}(ZFC)$, to be true but unprovable. To get a sense for how this could possibly be the case, recall that by the completeness theorem, to say that an arithmetic statement is unprovable (in first-order Peano arithmetic) is exactly to say that there exists a model of PA in which it's true and a model of PA in which it's false. So, a true but unprovable statement is a statement which is true in the "standard model" of PA, the "actual natural numbers," but false in some nonstandard model of arithmetic. For a $\Pi_1^0$ statement $\forall n : P(n)$ this means exactly that $P(n)$ is true of every standard or "actual" natural number, but that it has some "nonstandard counterexample."

In the case of $\text{Con}(ZFC)$, for example, this means there is some nonstandard model of arithmetic containing a "nonstandard proof" (more precisely, a nonstandard number which is rigged up to have the property that PA thinks it's the Gödel number of a proof) of an inconsistency in ZFC. Such models must exist if you believe that ZFC is consistent, by the incompleteness theorems.