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.

I read an article which presented some system with axioms and inference rules (I don't know if that type of system have a term for in English).

The article stated that the system is "deductively complete".

I have read in Wikipedia a bit to recall what does it mean (its been a while since I studied logic).

In Wikipedia in states that $S$ is deductively complete system if for each formula $\varphi$ either $\varphi$ or $\neg\varphi$ is a theorem of $S$ .

Do I understand correctly that this system is not neccaseraly consistent ? for example you can add $$p\to\neg p$$ which is a contradiction and call the new system $S'$. If for a given $\varphi$ you had a proof for $\varphi$ or $\neg\varphi$ (that did not use the new axiom we added) then the same proof works in $S'$hence $S'$ is also deductively complete but is not consistent.

So if I understand correctly, a deductively complete system need not be sound.

Does it have to be complete ? the name of it suggest so, but I believe that the answer is no, for example if $S$ is a complete deductively complete system then either $\varphi$ or $\neg\varphi$ is a theorem of $S$ . I think there is maybe a way to construct a deductively complete system $S'$ in which if $\varphi$ is a theorem of $S$ then $\neg\varphi$ is a theorem of $S'$ and if $\neg\varphi$ is a theorem of $S$ then $\varphi$ is a theorem of $S'$. Then $S'$ is not complete (at least in the case where $S$ is consistent).

To sum up: Did I understand correctly that a deductively complete system need not be consistent, sound or complete ?

share|improve this question
    
Axioms and inference rules? Isn't that the definition of "logic"? :-) –  Asaf Karagila May 15 '13 at 9:33
    
Careful : $S$ is complete iff for every $\varphi$, $S$ as $\varphi$ or $\neg \varphi$ as a theorem. The or is inclusive. Your either $\varphi$ or $\neg \varphi$ makes me think you consider it exclusive. So yes, a theory can be complete but inconsistent. Actually every inconsistent theory is complete (as it shows everything). –  Pece May 15 '13 at 9:39
    
If every complete set of axioms were consistent, then Gödel's incompleteness theorem, which says that there is no complete, consistent axiomatization of Peano arithmetic, would be much less interesting. –  MJD May 15 '13 at 13:22
    
I think you need to say more. Some answers are about "complete theory" and not about "complete system of natural deduction". So, what is it that article? –  GEdgar May 15 '13 at 14:20

2 Answers 2

up vote 2 down vote accepted
  1. A deductively complete theory can be inconsistent. Indeed, as Pece remarks, a classical inconsistent theory entails every sentence $\varphi$ of the relevant language so (a fortiori) entails at least one of $\varphi$ and $\neg\varphi$ for each sentence $\varphi$. But your argument works too: if $T$ is deductively complete, consider $T'$ which you get by adding a contradiction as a new axiom. $T'$ proves everything which $T$ did, so is complete, but is inconsistent by construction.

  2. A deductively complete theory can be inconsistent, no inconsistent theory is sound, so a deductively complete theory need not be sound.

  3. But a deductively complete theory is, trivially, deductively complete. Of course, if we can show that $\varphi$ is a $T$ theorem iff $\neg\varphi$ is also a theorem, then we know that either $T$ is incomplete or is inconsistent. Turning that about, if $T$ is deductively complete, then either it is inconsistent or it isn't the case that there is some $\varphi$ such that $\varphi$ is a $T$ theorem iff $\neg\varphi$ is also a theorem.

  4. A deductively complete theory need not be sound on some given interpretation (if it has false axioms), so its set of theorems and the set of relevant truths are distinct. If completeness is understood in a semantic sense, as a matter of yielding a complete story about the relevant truths, then deductively completeness doesn't imply this kind of semantic completeness.

share|improve this answer

The Wikipedia article you linked to describes the different types of completeness fairly well, but there are some interesting connections between them. First, semantic completeness (everything true is provable) does not imply syntactic completeness (each sentence or its negation is provable), since there are sentences which are contingent (e.g., $A \lor B$), and the propositional calculus (a semantically complete calculus) won't be able to prove either of $A \lor B$ or $\lnot(A \lor B)$.

To the first question, a deductively complete system need not be consistent. The trivial counterexample is that an inconsistent system proves everything, and thus proves $\phi$ or $\lnot\phi$ for every $\phi$ (in fact, it proves both!).

To the second question, a deductively complete system need not be (semantically) complete. We could construct, for instance, an esoteric calculus with bizarre proof rules that guarantee that for every formula $\phi$, either $\phi$ or $\lnot\phi$ is a theorem. For instance, given the propositional language with variables $A$, $B$, $C$, $\dots$, the connectives $\lnot$, $\land$, $\lor$, and $\to$, where well-formed formulae are defined as usual, take as your system just the following two axiom schemata:

  1. $\phi$ where $\phi$ is a wff in which $\land$ appears an odd number of times
  2. $\lnot\phi$ where $\phi$ is a wff in which $\land$ does not appear an odd number of times

Since every formula $\phi$ either has an odd number of $\land$s, in which case $\phi$ is a theorem, or it doesn't, in which case $\lnot\phi$ is a theorem, the system is deductively complete. Theorems of this system include \begin{gather*} \lnot A \qquad A \land B \qquad \lnot(A \land (B \land C)) \end{gather*} It's pretty obviously not semantically complete (there are true sentences that it does not prove) and even unsound (there are non-true sentences that it does prove), but it's syntactically consistent (it never proves $\phi$ and $\lnot\phi$).

To sum up, a deductively complete system need not be (syntactically) consistent (never prove $\phi$ and $\lnot\phi$), sound ($\vdash \phi$ implies $\models \phi$), or (semantically) complete ($\models \phi$ implies $\vdash\phi$).


It would be an interesting exercise to determine which combinations of those can be had in a proof system, though. In the examples above saw deductively complete systems that were:

  • inconsistent, unsound, and (semantically) complete;
  • consistent, unsound, and (semantically) incomplete;

Without specifying a particular interpretation for the propositional variables, we cannot have a sound deductively complete system, because the deductively complete system has to make some judgment about the contingent sentences. Any inconsistent system will automatically be (semantically) complete, so the only possible case that we haven't seen is one which is:

  • consistent, unsound, and (semantically) complete.

Such a system could be had if a propositional variable assignment were part of the proof system. For instance, take the standard propositional calculus as a starting point. Then suppose some particular interpretation $\cal I$ of propositional variables (as an easy one, let every propositional variable be true). The standard propositional calculus is consistent and semantically complete, so we have those. To get the unsoundness, let us also add the axiom schema inference rule:

  • $\phi$, if $\cal I \models \phi$.

This will have the effect of making every otherwise contingent sentence (or its negation) a theorem. Since the propositional calculus is semantically complete, the only $\phi$ such that neither $\phi$ nor $\lnot\phi$ is a theorem are contingent sentences, but now those have been fixed as well, so the resulting system is consistent, unsound (since, e.g., $\vdash A \land B$ and $\not\models A \land B$), and semantically complete.

share|improve this answer

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.