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.

What does it mean when we say that a set of formulas , Sigma , is Consistent , or Inconsistent ?

Is Consistency is a semantic or a syntactic quality ?

From what I've read,Consistency means that we cannot prove a formula and its opposite meaning , is this correct ?

Regards,Ron

EDIT:

One more important question regarding completeness : if we cannot prove something , does it mean that it must be wrong ?

Once again , much thanks Ron

share|improve this question
2  
No it does not. Just means that there are models where it is true and others where it fails. –  azarel Feb 6 '12 at 7:21
add comment

4 Answers

up vote 2 down vote accepted

Let $\Sigma$ be a set of sentences (axioms). If (in first-order logic) there is no proof of $\varphi$, then there is a model of $\Sigma$ in which $\varphi$ is false.

Thus, for example, if $\Sigma$ is one of the usual first-order sets of axioms of Group Theory, and $\varphi$ is not provable from $\Sigma$, then there is a group $G$ in which $\varphi$ is false.

The situation is the same if we let $\Sigma$ be the usual first-order version of the Peano axioms for Number Theory. If $\varphi$ is not provable from $\Sigma$, then there is a model of $\Sigma$ in which $\varphi$ is false. That model, however, need not be the intended model (the natural numbers).

share|improve this answer
add comment

"Is Consistency is a semantic or a syntactic quality ?"

In first-order logic, as the other answers indicate, the completeness theorem shows that syntactic and semantic consistency are equivalent.

In other logics, the two types of consistency are distinct, and you have to specify the type of consistency you mean. In particular, to give a very specific example, there is no complete effective, sound deductive system for second-order logic, and given any particular effective, sound deduction system for it there are effective theories that are syntactically consistent but semantically inconsistent.

Things can get even more odd as we go farther from classical logic. Classically, it is equivalent to say that a theory proves $\phi \land \lnot \phi$ for some $\phi$, and to say that the theory proves every sentence $\phi$. But in other logics these may not be equivalent, so they may represent distinct types of syntactic inconsistency. Paraconsistent logics, in particular, allow for some contradictory statements to be proved without allowing every statement to be proved.

share|improve this answer
add comment

Note that by the completeness theorem: $\Sigma$ is consistent (in your sense) if and only if $\Sigma$ has a model.

share|improve this answer
1  
You are assuming that it is a first order theory. –  Asaf Karagila Feb 6 '12 at 7:56
add comment

Consistency (in, say, first-order logic) means that we cannot prove $\perp$ (falsehood) from the statements in $\Sigma$; this is a syntactic notion. However, by the completeness theorem, it equivalently means that a model exists in which all of the statements in $\Sigma$ are true; this is a semantic notion. The power of the completeness theorem is precisely that it allows us to switch between working syntactically and working semantically.

share|improve this answer
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.