8.4 How to prove invalidity

Natural deduction provides a method to demonstrate that a reasoning is correct, but, how can you prove that a reasoning is non-correct? It can't be done with natural deduction.

We are in this situation: we have sequent $\Gamma\vdash A$, and we think that there exists a model (set of values) which make true $\Gamma$ -gamma- but not $A$. Well, then we just have to find it to prove that the sequent is invalid. This model is called countermodel, and we can find it in several ways. I think that the simplest one is intuitively: start trying different values which we regard as possible countermodel, until we find a good one.

For instance, $\neg P\Rightarrow\neg Q,\ \neg Q\vdash\neg P\vee Q$ is invalid ($\nvDash$), since when $P$ is true and $Q$ is false, the left part (antecedent) becomes true but the right part (consequent) is false, so $\neg P\vee Q$ is not a consequence of that from the left part.

Daniel Clemente Laboreo 2005-05-17