Section 08: Proofs and models

As you might already suspect, there is a connection between theorems and tautologies.

There is a formal way of showing that a sentence is a theorem: Prove it. For each line, we can check to see if that line follows by the cited rule. It may be hard to produce a twenty line proof, but it is not so hard to check each line of the proof and confirm that it is legitimate— and if each line of the proof individually is legitimate, then the whole proof is legitimate. Showing that a sentence is a tautology, though, requires reasoning in English about all possible models. There is no formal way of checking to see if the reasoning is sound. Given a choice between showing that a sentence is a theorem and showing that it is a tautology, it would be easier to show that it is a theorem.

Contrawise, there is no formal way of showing that a sentence is not a theorem. We would need to reason in English about all possible proofs. Yet there is a formal method for showing that a sentence is not a tautology. We need only construct a model in which the sentence is false. Given a choice between showing that a sentence is not a theorem and showing that it is not a tautology, it would be easier to show that it is not a tautology.

Fortunately, a sentence is a theorem if and only if it is a tautology. If we provide a proof of ⊢ \(\mathcal{A}\) and thus show that it is a theorem, it follows that \(\mathcal{A}\) is a tautology; i.e., ⊨ \(\mathcal{A}\). Similarly, if we construct a model in which \(\mathcal{A}\) is false and thus show that it is not a tautology, it follows that \(\mathcal{A}\) is not a theorem.

In general, \(\mathcal{A}\) ⊢ \(\mathcal{B}\) if and only if \(\mathcal{A}\) ⊨ \(\mathcal{B}\). As such:

• An argument is valid if and only if the conclusion is derivable from the premises.
• Two sentences are logically equivalent if and only if they are provably equivalent.
• A set of sentences is consistent if and only if it is not provably inconsistent.

You can pick and choose when to think in terms of proofs and when to think in terms of models, doing whichever is easier for a given task. Table 6.1 summarizes when it is best to give proofs and when it is best to give models.

In this way, proofs and models give us a versatile toolkit for working with arguments. If we can translate an argument into QL, then we can measure its logical weight in a purely formal way. If it is deductively valid, we can give a formal proof; if it is invalid, we can provide a formal counterexample.

	YES	NO
Is \(\mathcal{A}\) a tautology?	prove ⊢ \(\mathcal{A}\)	give a model in which \(\mathcal{A}\) is false
Is \(\mathcal{A}\) a contradiction?	prove ⊢¬\(\mathcal{A}\)	give a model in which \(\mathcal{A}\) is true
Is \(\mathcal{A}\) contingent?	give a model in which \(\mathcal{A}\) is true and another in which \(\mathcal{A}\) is false	prove ⊢\(\mathcal{A}\) or ⊢¬\(\mathcal{A}\)
Are \(\mathcal{A}\) and \(\mathcal{B}\) equivalent?	prove \(\mathcal{A}\) ⊢ \(\mathcal{B}\) and \(\mathcal{B}\) ⊢ \(\mathcal{A}\)	give a model in which \(\mathcal{A}\) and \(\mathcal{B}\) have different truth values
Is the set \(\mathcal{A}\) consistent?	give a model in which all the sentences in \(\mathcal{A}\) are true	taking the sentences in \(\mathcal{A}\), prove \(\mathcal{B}\) and ¬\(\mathcal{B}\)
Is the argument ‘\(\mathcal{P}\), .˙. \(\mathcal{C}\)’ valid?	prove \(\mathcal{P}\) ⊢ \(\mathcal{C}\)	give a model in which \(\mathcal{P}\) is true and \(\mathcal{C}\) is false

Table 6.1: Sometimes it is easier to show something by providing proofs than it is by providing models. Sometimes it is the other way round. It depends on what you are trying to show.