ONT Re: Model Theory
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 9
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
| 1. Introduction
|
| 1.2. Model Theory for Sentential Logic (cont.)
|
| An especially important kind of sentence is a 'valid sentence'.
| A sentence p is called 'valid', in symbols, |= p, iff p holds in
| all models for $S$, that is, iff A |= p for all A. Some notions
| closely related to validity are mentioned in the exercises.
|
| At first glance, it seems that we have to examine uncountably many
| different infinite models A in order to find out whether a sentence p
| is valid. This is because validity is a semantical notion, defined in
| terms of models. However, as the reader surely knows, there is a simple
| and uniform test by which we can find out in only finitely many steps
| whether or not a given sentence p is valid.
|
| This decision procedure for validity is based on a syntactical notion,
| the notion of a tautology. Let p be a sentence such that all the sentence
| symbols which occur in p are among the n + 1 symbols S_0, S_1, ..., S_n.
| Let a_0, a_1, ..., a_n be a sequence made up of the two letters 't', 'f'.
| We shall call such a sequence an 'assignment'.
|
| 1.2.4. The 'value' of a sentence p for the assignment a_0, ..., a_n
| is defined recursively as follows:
|
| 1. If p is the sentence symbol S_m, m =< n, then the value of p is a_m.
|
| 2. If p is ~q, then the value of p is the opposite of the value of q.
|
| 3. If p is q & r, then the value of p is t if the values of q and r
| are both t, and otherwise the value of p is f.
|
| Note how similar Definitions 1.2.3 and 1.2.4 are. The only
| essential difference is that 1.2.3 involves an infinite model A,
| while 1.2.4 involves only a finite assignment a_0, ..., a_n.
|
| 1.2.5. Let p be a sentence and let S_0, ..., S_n
| be all the sentence symbols occurring in p.
| The sentence p is said to be a 'tautology',
| in symbols, |- p, iff p has the value t
| for every assignment a_0, ..., a_n.
|
| We shall use both of the symbols |= and |- in many
| ways throughout this book. To keep things straight,
| remember this:
|
| |= is used for semantical ideas,
|
| |- is used for syntactical ideas.
|
| The value of a sentence p for an assignment a_0, ..., a_n may be very easily
| computed. We first find the values of the sentence symbols occurring in p
| and then work our way through the smaller sentences used in building up
| the sentence p. A table showing the value of p for each possible
| assignment a_0, ..., a_n is called a 'truth table' of p. We shall
| assume that truth tables are already quite familiar to the reader,
| and that he [or she] knows how to construct a truth table of a
| sentence. Truth tables provide a simple and purely mechanical
| procedure to determine whether a sentence p is a tautology --
| simply write down the truth table for p and check to see
| whether p has the value t for every assignment.
|
| 1.2.6. Proposition. Suppose that all the sentence symbols occurring in p
| are among S_0, S_1, ..., S_n. Then the value of p for an assignment
| a_0, a_1, ..., a_n, ..., a_(n+m) is the same as the value of p for
| the assignment a_0, a_1, ..., a_n.
|
| Chang & Keisler, 'Model Theory', pages 7-8.
|
| C.C. Chang and H.J. Keisler, 'Model Theory',
| North-Holland, Amsterdam, Netherlands, 1973.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤