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.

We call a set of formulas $\Sigma$ of a language $L$ consistent if there is no $\varphi$ in $L$ such that $\Sigma \vdash \varphi$ and $\Sigma \vdash \lnot \varphi$.

Apparently, an equivalent formulation is the following:

A set $\Sigma$ of formulas of $L$ is consistent iff $\Sigma \not\vdash \varphi$ for some sentence $\varphi$ of $L$.

The $\implies$ direction is clear: if we can prove all sentences then we can prove both $\varphi$ and $\lnot \varphi$ so that $\Sigma$ is inconsistent.

But I don't immediately see how to prove $\Longleftarrow$. Can someone explain this to me? Thanks!

share|improve this question
    
Hm ... seems to depend on the conclusion rules you are using, but I'd say something along the lines $\Sigma \vdash \varphi, \neg \varphi$ gives $\Sigma \vdash \varphi \land\neg\varphi$ and by $\Sigma \vdash(\varphi \land \neg\varphi \to \psi)$ (logical axiom) we have by MP $\Sigma \vdash \psi$. –  martini Nov 19 '12 at 10:48

2 Answers 2

up vote 7 down vote accepted

Assume that $\Sigma$ is consistent then it cannot prove $\varphi\land\lnot\varphi$. Therefore there exists a sentence which it does not prove.

Assume that $\Sigma$ is inconsistent then it proves everything (using the principle of explosion). Therefore there is no sentence it does not prove.

share|improve this answer
    
Thank you! I like concise answers. –  Matt N. Nov 22 '12 at 15:22
    
@Matt: I know you do. :-) I like writing long answers, though. ;-) –  Asaf Karagila Nov 22 '12 at 15:23
    
I know you do. ${}$ –  Matt N. Nov 22 '12 at 15:25
    
Perhaps you could consider writing a set theoretic novel, set 42 B.C. -- 42 before Cantor? –  Matt N. Nov 22 '12 at 15:26
    
@Matt: Ha. I might take you on that. It will take me a "non-standard integer"-many days to write such novel, though. –  Asaf Karagila Nov 22 '12 at 15:28

The characterizations are not equivalent in general. Take the most trivial case: suppose $L$ is a negation-free language. Then vacuously, the set $\Sigma$ of all $L$-formulae is consistent in the first sense, but not in the second sense.

However, in a language with negation and in the presence of ex contradictione quodlibet (the rule that from $\varphi$ and $\neg\varphi$ you can derive any $\psi$), the two characterizations become co-extensional.

share|improve this answer
1  
I am fairly certain this is in the context of classical FOL. –  Asaf Karagila Nov 19 '12 at 11:05
1  
@AsafKaragila Sure thing, they come to the same in FOL. But it was important to Post, to whom we owe the second definition, that it applies more widely. So I thought it was worth emphasizing that, in a more general setting, the definitions peel apart. –  Peter Smith Nov 19 '12 at 11:17

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.