Chapter 41 Proofs and semantics
We have used two different turnstiles in this book. This:
means that there is some proof which ends with and whose only undischarged assumptions are among . This is a proof-theoretic notion. By contrast, this:
means that no valuation (or interpretation) makes all of true and false. This concerns assignments of truth and falsity to sentences. It is a semantic notion.
It cannot be emphasized enough that these are different notions. But we can emphasize it a bit more: They are different notions.
Once you have internalised this point, continue reading.
Although our semantic and proof-theoretic notions are different, there is a deep connection between them. To explain this connection,we will start by considering the relationship between validities and theorems.
To show that a sentence is a theorem, you need only produce a proof. Granted, 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 validity, though, requires reasoning about all possible interpretations. Given a choice between showing that a sentence is a theorem and showing that it is a validity, it would be easier to show that it is a theorem.
Contrawise, to show that a sentence is not a theorem is hard. We would need to reason about all (possible) proofs. That is very difficult. However, to show that a sentence is not a validity, you need only construct an interpretation in which the sentence is false. Granted, it may be hard to come up with the interpretation; but once you have done so, it is relatively straightforward to check what truth value it assigns to a sentence. Given a choice between showing that a sentence is not a theorem and showing that it is not a validity, it would be easier to show that it is not a validity.
Fortunately, a sentence is a theorem if and only if it is a validity. As a result, if we provide a proof of on no assumptions, and thus show that is a theorem, i.e., , we can legitimately infer that is a validity, i.e., . Similarly, if we construct an interpretation in which is false and thus show that it is not a validity, i.e., , it follows that is not a theorem, i.e., .
More generally, we have the following powerful result:
iff
This shows that, whilst provability and entailment are different notions, they are extensionally equivalent. As such:
-
‣
An argument is valid iff the conclusion can be proved from the premises.
-
‣
A sentence is a validity iff it is a theorem.
-
‣
Two sentences are equivalent iff they are provably equivalent.
-
‣
Sentences are jointly satisfiable iff they are jointly consistent.
For this reason, you can pick and choose when to think in terms of proofs and when to think in terms of valuations/interpretations, doing whichever is easier for a given task. The table on the next page summarizes which is (usually) easier.
It is intuitive that provability and semantic entailment should agree. But—let us repeat this—do not be fooled by the similarity of the symbols ‘’ and ‘’. These two symbols have very different meanings. The fact that provability and semantic entailment agree is not an easy result to come by.
In fact, demonstrating that provability and semantic entailment agree is, very decisively, the point at which introductory logic becomes intermediate logic.
Yes | No | |
Is a validity? | give a proof which shows | give an interpretation in which is false |
Is a contradiction? | give a proof which shows | give an interpretation in which is true |
Are and equivalent? | give two proofs, one for and one for | give an interpretation in which and have different truth values |
Are jointly satisfiable? | give an interpretation in which all of are true | prove a contradiction from assumptions |
Is valid? | give a proof with assumptions and concluding with | give an interpretation in which each of is true and is false |