ONT Re: Model Theory
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 24
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
| 1. Introduction
|
| 1.3. Languages, Models, and Satisfaction (cont.)
|
| To formalize a language $L$, we need the
| following 'logical symbols' (see the
| corresponding development for $S$
| in Section 1.2):
|
| 1. Parentheses. '(' and ')'
|
| 2. Variables. v_0, v_1, ..., v_n, ...
|
| 3. Connectives. '&' (and), '~' (not)
|
| 4. Quantifier. '`A`' (for all)
|
| and one binary relation symbol '=' (identity).
|
| We assume, of course, that no symbol in $L$
| occurs in the above list. Certain strings
| of symbols from the above list and from $L$
| are called 'terms'. They are defined as
| follows:
|
| 1.3.1. [Definition of a 'term' of $L$].
|
| 1. A variable is a term.
|
| 2. A constant symbol is a term.
|
| 3. If F is an m-placed function symbol
| and t_1, ..., t_m are terms, then
|
| F(t_1 ... t_m) is a term.
|
| 4. A string of symbols is a term
| only if it can be shown to be
| a term by a finite number of
| applications of (1, 2, 3).
|
| The 'atomic formulas' of $L$ are strings of the form given below:
|
| 1.3.2. [Definition of an 'atomic formula' of $L$].
|
| 1. t_1 = t_2 is an atomic formula,
| where t_1 and t_2 are terms of $L$.
|
| 2. If P is an n-placed relation symbol
| and t_1, ..., t_n are terms, then
|
| P(t_1 ... t_n) is an atomic formula.
|
| Finally, the 'formulas' of $L$ are defined as follows:
|
| 1.3.3. [Definition of a 'formula' of $L$].
|
| 1. An atomic formula is a formula.
|
| 2. If p and q are formulas, then
|
| (p & q) and (~p) are formulas.
|
| 3. If v is a variable and p is a formula, then
|
| (`A`v)p is a formula.
|
| 4. A sequence of symbols is a formula
| only of it can be shown to be a
| formula by a finite number of
| applications of (1, 2, 3).
|
| Just as in the case of $S$, we may put definitions 1.3.1 and 1.3.3
| in a set-theoretical setting. Namely, the set of terms of $L$ is
| the least set T such that:
|
| T contains all constant symbols and all variables v_n, n = 0, 1, 2, ...,
| and, whenever F is an m-placed function symbol and t_1, ..., t_m are in T,
| then F(t_1 ... t_m) is in T.
|
| Similarly, the set of formulas of $L$ is the least set Q such that:
|
| Every atomic formula belongs to Q and, whenever p and q are in Q
| and v is a variable, then (p & q), (~p), (`A`v)p all belong to Q.
|
| Notice that we have tacitly used the letters 't' (with subscripts)
| to range over terms, 'v' to range over variables, and p, q to range
| over formulas. Again, we empahsize that 'properties of terms and
| formulas of $L$ can only be established by an induction based on
| definitions 1.3.1 and 1.3.3'.
|
| We can now introduce the abbreviations v, =>, <=> as in
| Section 1.2. Furthermore, we adopt all the conventions
| introduced earlier. The new symbol '`E`' (there exists)
| is introduced as an abbreviation defined as:
|
| (`E`v)p for ~(`A`v)~p.
|
| Some new conventions are the following:
|
| p_1 & p_2 & ... & p_n for (p_1 & (p_2 & ... & p_n))
|
| p_1 v p_2 v ... v p_n for (p_1 v (p_2 v ... v p_n))
|
| (`A`x_1 x_2 ... x_n)p for (`A`x_1)(`A`x_2) ... (`A`x_n)p
|
| (`E`x_1 x_2 ... x_n)p for (`E`x_1)(`E`x_2) ... (`E`x_n)p
|
| At this point we assume that the reader has enough experience in first-order
| predicate logic to continue the development on his [or her] own. In particular,
| we leave it to him [or her] to decide on the notions of 'subformulas', 'free' and
| 'bound' occurrences of a variable in a formula, and to give a proper definition
| (based on definitions 1.3.1, 1.3.3) of 'substitution' of a term for a variable
| in a formula.
|
| Chang & Keisler, 'Model Theory', pages 22-23.
|
| C.C. Chang and H.J. Keisler, 'Model Theory',
| North-Holland, Amsterdam, Netherlands, 1973.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤