4
$\begingroup$

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 consistency I assume that no sentence $P$ and its negation $\neg P$ can be deduced.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Commented May 13, 2014 at 22:23
  • $\begingroup$ do you have a reference where soundness implies consistency? Consider the following system: $\{Axioms=\{ S,\neg S\}, InferenceRules=\{ NOT(\cdot) \} \}$. If I understand things correctly this system can derivate contradictions (i.e. its not consistent) but its sound, everything derivable is True (since we are assuming that the axioms are true by definition). Perhaps what makes this example wrong is that Truth can't be characterized mathematically but thats why I wanted a link to your supposed prove that soundness is implies consistency (i.e. soundness is stronger than consistency). $\endgroup$ Commented Feb 19, 2018 at 3:55

1 Answer 1

12
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Commented May 14, 2014 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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