2
$\begingroup$

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!

  • 0
    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$.2012-11-19

2 Answers 2

7

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.

  • 0
    @Matt: Ha. I might take you on that. It will take me a "non-standard integer"-many days to write such novel, though.2012-11-22
3

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.

  • 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.2012-11-19