ONT Re: Model Theory
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 11
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
| 1. Introduction
|
| 1.2. Model Theory for Sentential Logic (cont.)
|
| Let us now introduce the notion of
| a formal deduction in our logic $S$.
|
| The 'Rule of Detachment' (or 'Modus Ponens') states:
|
| From q and q => p, infer p.
|
| We say that p is 'inferred' from q and r
| by detachment iff r is the sentence q => p.
|
| Now consider a finite or infinite set !S! of $S$.
|
| A sentence p is 'deducible' from !S!, in symbols, !S! |- p,
| iff there is a finite sequence q_0, q_1, ..., q_n of sentences
| such that p = q_n, and each sentence q_m is either a tautology,
| belongs to !S!, or is inferred from two earlier sentences of
| the sequence by detachment. The sequence q_0, q_1, ..., q_n
| is called a 'deduction' of p from !S!. Notice that p is
| deducible from the empty set of sentences if and only if
| p is a tautology.
|
| We shall say that !S! is 'inconsistent'
| iff we have !S! |- p for all sentences p.
| Otherwise, we say that !S! is 'consistent'.
|
| Finally, we say that !S! is 'maximal consistent'
| iff !S! is consistent, but the only consistent
| set of sentences which includes !S! is !S!
| itself. The proposition below contains
| facts which can be found in most
| elementary logic texts.
|
| 1.2.8. Proposition.
|
| 1. If !S! is consistent
| and !C! is the set of all
| sentences deducible from !S!,
| then !C! is consistent.
|
| 2. If !S! is maximal consistent
| and !S! |- p, then p is in !S!.
|
| 3. !S! is inconsistent if and only if
| !S! |- S & ~S (for any S in $S$).
|
| 4. Deduction Theorem.
|
| If !S! |_| {q} |- p, then !S! |- q => p.
|
| Chang & Keisler, 'Model Theory', pages 9-10.
|
| C.C. Chang and H.J. Keisler, 'Model Theory',
| North-Holland, Amsterdam, Netherlands, 1973.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤