Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 13 down vote accepted

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)$.

share|improve this answer
    
Thanks. That's what I thought. Now a follow up question. Can we construct a model in which the Godel sentence is false? –  Timothy Wagner Dec 9 '10 at 16:20
7  
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. –  Carl Mummert Dec 9 '10 at 16:28
    
Thanks. I have not read Henkin's proof, but it sounds like what I need. –  Timothy Wagner Dec 9 '10 at 16:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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