# True vs. Provable

Gödel's first incompleteness theorem states that "...For any such system, there will always be statements about the natural numbers that are true, but that are unprovable within the system".

What does it mean that a statement is true if it's not provable?

What is the difference between true and provable?

-
That is not a very good paraphrase of the 2nd Incompleteness Theorem. In fact, that's not even the 2nd Incompleteness Theorem (The 2nd incompleteness theorem is about the provability of the consistency of the system). Rather, it seems a poor paraphrase of the First incompleteness theorem. When the 1st Theorem talks about "arithmetical statements that are true but unprovable", "true" means "true in the standard model". Truth is a notion that depends on interpretation (i.e., on model); "provability" is a notion that depends on the formal system. –  Arturo Magidin Oct 2 '11 at 21:54

Provable means that there is a formal proof using the axioms that you want to use. The set of axioms (in this case axioms for arithmetic, i.e., natural numbers) is the "system" that your quote mentions. True statements are those that hold for the natural numbers (in this particular situation).

The point of the incompleteness theorems is that for every reasonable system of axioms for the natural numbers there will always be true statements that are unprovable. You can of course cheat and say that your axioms are simply all true statements about the natural numbers, but this is not a reasonable system since there is no algorithm that decides whether or not a given statement is one of your axioms or not.

As a side note, your quote is essentially the first incompleteness theorem, in the form in which it easily follows from the second.

In general (not speaking about natural numbers only) given a structure, i.e., a set together with relations on the set, constant in the set, and operations on the set, there is a natural way to define when a (first order) sentence using the corresponding symbols for your relations, constants, and operations holds in the structure. ($\forall x\exists y(x\cdot y=e)$ is a sentence using symbols corresponding to constants and operations that you find in a group, and the sentence says that every element has an inverse.)

So this defines what is true in a structure. In order to prove a statement (sentence), you need a set of axioms (like the axioms of group theory) and a notion of formal proof from these axioms. I won't eleborate here, but the important connection between true statements and provable statements is the completeness theorem:

A sentence is provable from a set of axioms iff every structure that satisfies the axioms also satisfies the sentence.

This theorem tells you what the deal with the incompleteness theorems is: We consider true statements about the natural numbers, but a statement is provable from a set of axioms only if it holds for all structures satisying the axioms. And there will be structures that are not isomorphic to the natural numbers.

-

Consider this claim: John Smith will never be able to prove this statement is true.

If the statement is false, then John Smith will be able to prove it's true. But clearly that can't be, since it's impossible to prove that a false statement is true. (Assuming John Smith is sensible.)

If it's true, there's no contradiction. It just means John Smith won't be able to prove it's true. So it's true, and John Smith won't be able to prove it's true. This is a limit on what John Smith can do. (So if John Smith is sensible, there are truths he cannot prove.)

What Goedel showed is that for any sensible formal axiom system, there will be formal versions of "this axiom system cannot prove this claim is true". It will be a statement expressible in that formal system but, obviously, not provable within that axiom system.

-

Note that you are not paraphrasing the 2nd Incompleteness Theorem (which says that an axiomatic system that satisfies certain technical conditions cannot prove its own consistency unless it is inconsistent), but rather the First Incompleteness Theorem.

Remember that a "model" of an axiomatic system means a particular interpretation of the primitive notions that makes that makes the axioms true in that interpretation.

"True" and "False" in this context refer to models. "True" should really be "true in the model $M$"; that is, there is a particular interpretation of the axioms which makes the statement true. When we talk about arithmetic statements being "true", we mean "true in the standard model" (the "standard model" being a particular interpretation of the primitive notions of arithmetic). See for example Wikipedia's page on non-standard models of airthmetic.

"Provable" means that there is a formal derivation of the statement from the axioms. If a statement is provable, then it is true in all models; conversely, Gödel's Completeness Theorem shows that if a (first order) statement is true in all models, then it is provable.

In particular, a statement is "formally undecidable" in an axiomatic system if there are some models in which it is true, and some models in which it is false. When you have a "prefered model" (as we do with arithmetic), we often talk simply about "true" instead of "true in a particular model".

-

The dinosaurs were killed by a gigantic brain, rather than an asteroid. (cf. Futurama, The Why of Fry)

While seemingly false, you cannot prove this statement is true or false. You can only find evidence to support its refutation.

In real life we tend to label things as true or false regardless to their provability. Mathematics, however, offers us the distinction between the existence of a proof and the truth value of a statement.

That is, we define what is a structure in some language, and what sort of assertions are true in that structure.

We can take a set of sentences from which we cannot derive contradiction (these sets are called theories, for example, axioms of a group), and we can consider structures of the appropriate language in which this set of sentences is true (we say that this is a model of the theory).

The incompleteness theorem says that given such theory which is "nice enough" and can be used to develop some of the theory true in the natural numbers, then in a model of this theory there will be assertions which are true but cannot be proved.

Of course, we can prove such assertion using different theories, or we can provide counterexamples with different theories. We can perhaps prove more (or less) if we even replace the way we deduce things, or the sentences we allow (we can allow second-order logic, or infinite quantification, for example).

However within the confines of first-order logic, and the given theory there are sentences which we can prove are unprovable from this given theory, but can be true in some model. Furthermore, in every model there is some statement which is true (in that specific model) but has no proof.

-

Suppose I made some kind of statement like "For all natural numbers $n$, $P(n)$ holds."

For my claim to be true, it must be that there is no counterexample. That is, there is no integer $n_0$ such that $P(n_0)$ fails. Even if this is the case, I may not be able to prove that it is so. So, my statement could be true, but unprovable.

-

Provability depends on what you can do to prove things, that is, on the deduction rules available within the system.

Consider the first order theory of the natural numbers with no deduction rules. There are lots of true statements in it, but most of them are not provable!

-
Then how do you know they are true? –  user1708 Oct 2 '11 at 22:00
Pick any statement from, say, Peano arithmetic which is not one of its axioms, and consider it in the theory which has the same axioms but no deduction rules. –  Mariano Suárez-Alvarez Oct 2 '11 at 22:02
$17$ is a prime number. That is true. But if there are no deduction rules, then of course you cannot prove it. "No deduction rules" is a stupid system, granted. But, in fact, Gödel showed that all systems attempting to describe the natural numbers are a little stupid in this regard. –  GEdgar Oct 2 '11 at 22:12

Let John Smith be a normal person, just as smart as you and me. Consider the sentence:

'John Smith will never be able to prove this statement is true.'

It seems easy to prove the sentence true: if JS can prove it, it is false; since nothing false can be proven, JS cannot prove it; hence, it is true.

The problem is that JS, being as smart as any of us, can understand the 'proof' above and then 'prove' the sentence. What has gone wrong?

Most probably, the sentence above is not a real statement but a sentence unable to make a statement or express a proposition; a paradoxical sentence like the Liar, unable to be true or false.

This never happens with formal systems. If S is a correct formal system, it will not prove:

'S doesn't prove this sentence'

beause if S proved it, it would be false and S incorrect, contrary to the assumed.

Therefore, the sentence will be true but unprovable if S is correct.

The difference between JS and S is that, S being a formal system, whether S proves or doesn't a particular sentence is a determinate state of affairs, with respect to which only truth or falsity is possible, but not paradox.

Note that this suggests a difference between provability by JS (or you or me) and provability in some correct formal system.

-