6
$\begingroup$

First-order logic is complete & sound. The notion of truth used here is model-theoretic.

Informally Godels incompleteness theorem says that for a sufficiently strong formal language there are truths that cannot be proved. How is truth encoded in the language? Is this actually correct, should it be that there are statements which cannot be either proved or disproved - that is they are undecidable. Does this mean that they actually have no truth status?

$\endgroup$
  • 1
    $\begingroup$ I would say by observing certain properties within the system. The book Godel, Escher, Bach explains this quite well in the second chapter. These are the properties called axioms. $\endgroup$ – Don Larynx Aug 23 '13 at 23:00
8
$\begingroup$

"True" here means "true in the standard model." For example, the standard model of PA is the "actual" natural numbers. I agree that this is confusing. A more model-agnostic way to state the incompleteness theorem is that there are statements that are true in some models but false in others (hence that are neither provable nor disprovable).

$\endgroup$
  • $\begingroup$ Using two notions of completeness has kept me confused for some time. It might be better if the common name for the incompleteness theorem was the undecideability theorem which seems eminently sensible to me given that the name of Godels paper is 'on formally undecidable propositions of the Principia Mathematica'. $\endgroup$ – Mozibur Ullah Aug 23 '13 at 23:45
  • $\begingroup$ ‘Decidability’ is equally ambiguous. $\endgroup$ – Zhen Lin Aug 24 '13 at 0:03
5
$\begingroup$

The incompleteness theorems (for a fixed theory) have as an assumption that the theory is consistent. This assumption can be phrased as a statement $C$ in the language of Peano arithmetic. Meanwhile, the first incompleteness theorem produces a Gödel sentence $G$ in the language of Peano arithmetic that is independent of the theory.

The Gödel sentence $G$ is true in exactly the same sense that the consistency assumption $C$ is true.

In other words, as soon as you work out a sense in which you think that $C$ is true, $G$ will also be true in that sense. There are many different "senses" that can be used here:

  • Semantically: $C$ is true in the standard model, and $G$ is also true in that model.

  • Disquotationally: $C$ is true, disquotationally, as a statement about natural numbers, and so is $G$.

  • Formally: If $C$ is provable in some reasonable metatheory, $G$ will also be provable in that metatheory. Here any metatheory at least as strong as PA is "reasonable". In fact PA can be replaced with a weaker metatheory such as PRA (primitive recursive arithmetic) or any other metatheory strong enough to prove the first incompleteness theorem.

$\endgroup$
-1
$\begingroup$

In this thread I was wondering about what I believe are similar issues of truth in 'the standard model' and provability.

I will use the language of Gensler's little book Godel's Theorem Simplified.

For what Gensler calls System C, he gives an outline for how to construct a wff in system C. The system C the symbols are /, (, ), - , n (for a variable), nn (another variable),...etc.).

The reference numbers for system C formulas (like Godel numbers) are defined too.

For example the ref # for / is 1, the reference # for the variable n is 8, etc.

Then Gensler gives instructions for how to create a formula called F which states

(F) "There is no system C proof for the son of the system C formula with reference # n ".

Here n is a variable. So the system C formula with reference # n exists, call that system C formula XX, and F is the statement that the system C son of XX, SonXX, is not a theorem in system C).

F is a string of symbols of system C.The son of F is obtained by taking the reference number (an actual whole number like 112278 etc) for F, writing that whole number as the system C string //.../ (with reference # of F many /'s appearing) and replacing each occurrence the variable n in (F) with that many ///.../.

The result is a new system C formula, the son of F, called G.

The 'standard model' interpretation of G is then

(G) "There is no system C proof for the son of the system C formula with reference # equal to the reference # of F."

In other words, there is no system C proof of G itself.

Then Gensler and other sources indicate this standard interpretation of G is true, so it is a true 'ordinary arithmetic' statement, for which the corresponding system C formula has no proof.

It seems to me that what you can really say is this:

If you assume that the standard interpretation of G is a true statement in the ordinary standard model, then the corresponding system C formula is an unprovable system C formula. So you have a 'true' ordinary arith statement which cannot be proved in system C, BECAUSE you have ASSUMED that the standard model version of G is true.

If you assume that the standard interpretation of G is a false statement in the ordinary standard model, then the corresponding system C formula is an provable system C formula.So you have a 'false' ordinary arith statement which can be proved in system C, BECAUSE you have ASSUMED that the standard model version of G is false.

But how do you know that one of the two statements " G is a true statement in the ordinary standard model" or " G is a false statement in the ordinary standard model" must be valid?

Isn't the best you can say that IF you could determine that G were a true statement in the ordinary standard model" or " G is a false statement in the ordinary standard model" THEN you can draw conclusions about non provability or provability of G as a system C formula?

$\endgroup$
  • 1
    $\begingroup$ This seems more like a separate question than an answer to this one. $\endgroup$ – Noah Schweber Jan 22 at 21:33
  • $\begingroup$ You are right! I have posted this as a question. Thanks! $\endgroup$ – grell6954 Jan 23 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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