20
$\begingroup$

This might be an elementary question, but I am just beginning to learn logic theory.

From wikipedia article on Gödel's incompleteness theorems

Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true, but not provable in the theory (Kleene 1967, p. 250). The true but unprovable statement referred to by the theorem is often referred to as “the Gödel sentence” for the theory.

My question: Is a Gödel statement logically valid?.

Edit: As Carl answers below, if the Gödel statement is valid, then by completeness theorem, it is provable, which leads to a contradiction. So there exists a model in which the statement is false. Can we construct such a model?

$\endgroup$

1 Answer 1

Reset to default
22
$\begingroup$

No, a Gödel sentence is not logically valid. Because the Gödel sentence for a theory $T$ is unprovable from $T$, it follows from the completeness theorem for first-order logic that there is a model of $T$ in which the Gödel sentence is false.

When the text you quoted says "true" you should read that as "true in the standard model of arithmetic". Logical validity would correspond to truth in all models. An example of a logically valid sentence is $(\forall x) (x=x)$.

$\endgroup$
3
  • $\begingroup$ Thanks. That's what I thought. Now a follow up question. Can we construct a model in which the Godel sentence is false? $\endgroup$
    – Timothy Wagner
    Commented Dec 9, 2010 at 16:20
  • 13
    $\begingroup$ That depends greatly on what you mean by "construct". The Henkin proof of the completeness theorem shows how to construct, in a sense, a model in which $T$ is true and the Gödel sentence for $T$ is false. This construction can be done completely explicitly in set theory. On the other hand, Tennenbaum's theorem shows that there is no computable nonstandard model of Peano Arithmetic, so the construction cannot be explicit enough in general to yield a computable model. $\endgroup$
    – Carl Mummert
    Commented Dec 9, 2010 at 16:28
  • $\begingroup$ Thanks. I have not read Henkin's proof, but it sounds like what I need. $\endgroup$
    – Timothy Wagner
    Commented Dec 9, 2010 at 16:43

You must log in to answer this question.

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