ONT Re: Model Theory
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 10
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
| 1. Introduction
|
| 1.2. Model Theory for Sentential Logic (cont.)
|
| We now prove the first of a series of theorems
| which state that a certain syntactical condition
| is equivalent to a semantical condition.
|
| 1.2.7. Theorem. (Completeness Theorem).
|
| |- p if and only if |= p.
|
| In words, a sentence is a tautology
| if and only if it is valid.
|
| Proof. Let p be a sentence and let all the sentence symbols in p
| be among S_0, ..., S_n. Consider an arbitrary model A.
| For m = 0, 1, ..., n, put a_m = t if S_m is in A,
| and a_m = f if S_m is not in A. This gives us
| an assignment a_0, a_1, ..., a_n. We claim:
|
| 1. A |= p if and only if the value of p for
| the assignment a_0, a_1, ..., a_n is t.
|
| This can be readily proved by induction. It is immediate
| if p is a sentence symbol S_m. Assuming that (1) holds
| for p = q and for p = r, we see at once that (1) holds
| for p = ~q and p = q & r.
|
| Now let S_0, ..., S_n be all the sentence symbols occurring in p.
| If p is a tautology, then by (1), p is valid. Since every assignment
| a_0, a_1, ..., a_n can be obtained from some model A, it follows from (1)
| that, if p is valid, then p is a tautology. -|
|
| Our decision procedure for |- p now can be used to decide whether p is valid.
| Several times we shall have an occasion to use the fact that a particular
| sentence is a tautology, or is valid. We shall never take the trouble
| actually to give the proof that a sentence of $S$ is valid, because
| the proof is always the same -- we simply look at the truth table.
|
| Chang & Keisler, 'Model Theory', pages 8-9.
|
| C.C. Chang and H.J. Keisler, 'Model Theory',
| North-Holland, Amsterdam, Netherlands, 1973.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤