Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I understand that soundness implies consistency. Also, I understand that consistency alone does not imply soundness. But shouldn't consistency + completeness imply soundness? Scott Aaronson in his blog-post hints otherwise. What am I exactly missing?

Update: By completeness I assume that all sentences true under all interpretations are deducible. By soundness I assume that all deduced sentences are true under all interpretations. Finally, by completeness I assume that no sentence $P$ and its negation $\neg P$ can be deduced.

share|improve this question
1  
I suggest you define the concepts you use. What kind of proof systems are you interested at? What is soundness? What is consistency? What is completeness? These concepts have several related but different meanings in different contexts. –  Yuval Filmus May 13 at 22:23
add comment

1 Answer 1

up vote 7 down vote accepted

In the Scott Aaronson blog post you linked, (syntactic) consistency means that there is no sentence $P$ such that both $P$ and its negation can be deduced from the axioms of the theory. (Syntactic) completeness means that either $P$ or $\neg P$ are deducible from the axioms. And soundness means that if $P$ is deducible from the axioms then it is valid under all possible models/interpretations of the axioms.

Consistency + completeness does not imply soundness because you could have a set of axioms and a theorem $P$ where $P$ is deducible from the axioms, $\neg P$ is not deducible from the axioms but there is some model of the axioms under which $P$ is false and $\neg P$ is true.

Aaronson gives an example in his post:

If I believe that there’s a giant purple boogeyman on the moon, then presumably my belief is unsound, but it might be perfectly consistent with my various other beliefs about boogeymen.

"There's a giant purple boogeyman on the moon" is (perhaps) syntactically consistent with your axioms because you do not believe that "there isn't a giant purple boogeyman on the moon." Your axioms may be syntactically complete because they allow you to deduce at least one of the sentences "there's a giant purple boogeyman on the moon" or "there isn't a giant purple boogeyman on the moon." But in fact it is not true that "there's a giant purple boogeyman on the moon," so your deduction is unsound even though your axioms and deductive system are both consistent and complete.

The hardest concept in the above is probably soundness. Soundness relates the syntactic structure of your sentences and deduction rules to the interpretations (or models or semantics) of those sentences. A model of a language is a set, along with some relations and functions on the members of that set. For example, Gödel's language was the Peano axioms and the underlying model of the Peano axioms is the set of integers with (at least) an equality relation and a successor function. The Peano axioms are (I think) sound: if you can prove something with the Peano axioms then it is true of the natural numbers. But Gödel proved that the Peano axioms are not complete: there are sentences in the language of the Peano axioms that are in fact true of the natural numbers, but which are not derivable from the Peano axioms.

share|improve this answer
1  
The way I was taught logic, completeness means that all sentences valid under all intepretations are deducible. That being said, Godel's Incompleteness Theorem was about different kind of completeness, which involved standard and non-standard models. –  bellpeace May 14 at 1:07
add comment

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.