47
$\begingroup$

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?

$\endgroup$
2
  • 15
    $\begingroup$ 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. $\endgroup$ Oct 2, 2011 at 21:54
  • $\begingroup$ it might also be useful to distinguish those two words (truth and provable) from the word "satisfies". $\endgroup$ Jan 18, 2018 at 4:12

8 Answers 8

49
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ In your third paragraph, "If it's true, there's no contradiction. ... So it's true,"... Why is it true? What do you mean by true? $\endgroup$
    – Student
    Oct 13, 2020 at 20:08
  • $\begingroup$ @Student I mean that John Smith will in fact never be able to prove that statement is true. Since that's what the statement says, it's true. By "true", I mean corresponds with reality. $\endgroup$ Oct 15, 2020 at 22:56
  • $\begingroup$ 1. Not every sentence is a statement. Why is that claim a statement, i.e. either true or false? 2. OK, suppose it's either true or false. If it is false, then $\neg$ (John Smith will never be able to prove this statement is true.), i.e. there's a chance that John Smith is able to prove this statement true. But that doesn't mean the statement is necessarily true. So there is no contradiction. $\endgroup$
    – Student
    Jul 4, 2022 at 12:17
  • $\begingroup$ If John Smith proves the statement is true, then the statement is false. Thus John Smith cannot prove the statement is true (because it is impossible to prove that a false statement is true). Since that's what the statement says, and we just proved that it's the case, the statement is true. $\endgroup$ Jul 4, 2022 at 21:37
  • $\begingroup$ This makes me think about another claim: "No one can prove that this statement is true". This seems like a paradox to me. If it is false, then someone can prove that it is true, so it must be true. But if it must be true, I have just proved that it is true, so it must be false. Funny how the claim goes from a true statement to a paradox depending on who you include in the set of those who cannot prove the statement to be true. $\endgroup$
    – Odsh
    Oct 7, 2022 at 10:11
33
$\begingroup$

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, constants 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.

$\endgroup$
2
  • 1
    $\begingroup$ in this context what does the word "satisfies" mean and what is its relation to the word truth and provable? $\endgroup$ Jan 18, 2018 at 4:12
  • $\begingroup$ How do you know that a statement about the natural numbers is true? I can't shake the impression that "truth", even in the mathematical sense, is an empirical or subjective concept. The only exception so far seems to be self-referencing statements that must be true otherwise they contradict themselves. $\endgroup$
    – Odsh
    Oct 7, 2022 at 10:28
19
$\begingroup$

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".

$\endgroup$
2
  • $\begingroup$ I appreciate you mentioned the implicit reliance on the standard model. Many discussions omit the fact that the notion "True" depends on a choice of such a mode. // Some further questions - (1) What is a model? Is it defined formally? Must it be written down in set-theoretic language? (2) Given a model $M$ of a formal system $X$, what does it mean for an reinterpretation of a $X$-statement in $M$ to be true? (3) "If an $X$-statement is provable, then it is true in all models $M$ of $X$" .. Why? This seems nonobvious to me.. (pointers to rigorous book without implicit assumption are helpful). $\endgroup$
    – Student
    Nov 29, 2022 at 15:50
  • 1
    $\begingroup$ @Student: I say what a model is: a model is an interpretation of the primitive notions that make the axioms true. You can create models in set theory, but you don't have to create them in set theory. An $X$-statement is true in a model $M$ if the assertion it makes holds in $M$. Provability preserves truth, so if all th axioms are true in $M$, then so is everything that can be proven from the axioms, hence any provable statement is necessarily true in all models, since the axioms are true in models. $\endgroup$ Nov 29, 2022 at 17:03
15
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Re: "Furthermore, [...] there is some statement which is true (in that specific model) but has no proof." - I can imagine proving this statement for the standard model of arithmetic. However, how would someone ever prove such a thing for all possible models? Note that models do not have to be expressed in set theoretic languages (e.g. category based interpretation). $\endgroup$
    – Student
    Nov 29, 2022 at 15:27
  • 1
    $\begingroup$ If your logic is sound, then proving that $T$ proves $\varphi$ will show that $\varphi$ holds in all possible models. If you're going to use some non-standard semantics, non-standard logic, or some other different approach, then that's on you to show that your logic is sound, as well. $\endgroup$
    – Asaf Karagila
    Nov 30, 2022 at 9:36
5
$\begingroup$

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.

$\endgroup$
3
  • 4
    $\begingroup$ But why would you call it true then? If the statement cannot be proven to be false or true it is impossible to know that there are no counter examples (because if you knew, as in had proven it, that would contradict that the statement can't be proven). So it makes as much sense to call the statement false as to call it true. (And I would say the most sensible thing in this situation is to use neither terms.) $\endgroup$
    – Kvothe
    Sep 26, 2019 at 17:51
  • $\begingroup$ @Kvothe Fermat's Last Theorem has always been true, but it's only been recently that we had a proof. You're correct to caution about calling it true until such time as it is warranted, but the fact remains that the statement was always true. $\endgroup$ Sep 30, 2019 at 19:32
  • 3
    $\begingroup$ Okay but I was more talking about the cases stated in the question where it has already been proven that the statement cannot be proven. In that case I don't see why you would call the statement true. Using the terminology "true" for statements that can be proven to be true (but perhaps have not been proven yet) makes some sense. But then you would never end up using this meaning of the word "true" because you only know it is true once it has been proven to be true. $\endgroup$
    – Kvothe
    Oct 1, 2019 at 8:18
3
$\begingroup$

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!

$\endgroup$
4
  • 4
    $\begingroup$ Then how do you know they are true? $\endgroup$ Oct 2, 2011 at 22:00
  • $\begingroup$ 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. $\endgroup$ Oct 2, 2011 at 22:02
  • 3
    $\begingroup$ $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. $\endgroup$
    – GEdgar
    Oct 2, 2011 at 22:12
  • 1
    $\begingroup$ @TROLLKILLER: I know this is an old post, but I would like to clarify one thing. We believe that PA has a model, meaning a collection of objects with operations on them satisfying the axioms of PA. In fact, we believe even more, that the collection consisting of only expressions of the form "1+1+...+1" forms a model where the arithmetic operations are defined as some algorithms on such expressions. In any reasonable meta-system we have an axiom stating the existence of this model, and we call it $\mathbb{N}$. When we say something is "true" we only mean "true about $\mathbb{N}$". $\endgroup$
    – user21820
    Aug 2, 2016 at 4:57
3
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

In the context of GIT, it means that there is a unary predicate $P(x)$, such that:

$P(0)$ has a proof, and $P(1)$ has a proof, and $P(2)$ has a proof, etc forever. In fact, the proofs are so simple that they are actually just "evaluate the statement".

But because of how $P$ is made based on the exact choice of logic, there is no proof of $\forall x . P(x)$.

So $P$ is true in the sense that, whatever number for $x$ you pick, $P(\text{that exact number})$ has a trivial simple proof. But $P$ is unprovable in the sense that, $\forall x . P(x)$ doesn't have a proof in the stipulated logic.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .