ONT Re: Model Theory
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 19
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
| 1. Introduction
|
| 1.3. Languages, Models, and Satisfaction
|
| We begin here the development of first-order languages in a way parallel
| to the treatment of sentential logic in Section 1.2. First, we shall
| define the notions of a first-order predicate language $L$ and of a
| model for $L$. We introduce some basic relations between models --
| reductions and expansions, isomorphisms, submodels and extensions.
| We shall then develop the syntax of the language $L$, defining the
| sets of terms, formulas, and sentences, and presenting the axioms and
| rules of inference. Finally, we give the key definition of a sentence
| being true in a model for the language $L$. The precise formulation of
| this definition is much more of a challenge in first-order logic than
| it was for sentential logic. At the end of this section, we state
| the completeness and compactness theorems (Theorems 1.3.20, 21, 22),
| but the proofs of these theorems are deferred until the next chapter.
|
| We first establish a uniform notation and set of conventions
| for such languages and their models. A 'language' $L$ is a
| collection of symbols. These symbols are separated into
| three groups, 'relation symbols', 'function symbols',
| and '(individual) constant symbols'. The relation
| and function symbols of $L$ will be denoted by
| capital Latin letters P, F, with subscripts.
| Lower case Latin letters c, with subscripts,
| range over the constant symbols of $L$.
| If $L$ is a finite set, we may display
| the symbols of $L$ as follows:
|
| $L$ = {P_0, ..., P_n, F_0, ..., F_m, c_0, ..., c_k}.
|
| Each relation symbol P of $L$ is assumed to be an n-placed relation for
| some n >= 1, depending on P. Similarly, each function symbol F of $L$ is
| an m-placed function symbol, where m >= 1 and m depends on F. Notice that
| we do not allow 0-placed relation or function symbols. When dealing with
| several languages at the same time, we use the letters $L$, $L$’, $L$”,
| etc. If the symbols of the language are quite standard, as for example,
| '+' for addition, '=<' for an order relation, etc., we shall simply write:
|
| $L$ = {=<},
|
| $L$ = {=<, +, ·, 0},
|
| $L$ = {+, ·, -, 0, 1},
|
| etc.,
|
| for such languages. The number of places of the various
| kinds of symbols is understood to follow the standard usage.
| The 'power', or 'cardinal' of the language $L$, denoted
| by ||$L$||, is defined as:
|
| ||$L$|| = !w! [omega] |_| |$L$|.
|
| We say that a language $L$ is countable or uncountable
| depending on whether ||$L$|| is countable or uncountable.
|
| We occasionally pass from a given language $L$ to another language $L$’ which
| has all the symbols of $L$ plus some additional symbols. In such cases we use
| the notation $L$ c $L$’ and say that the language $L$’ is an 'expansion' of $L$,
| and that $L$ is a 'reduction' of $L$’. In the special case where all the symbols
| in $L$’ but not in $L$ are constant symbols, $L$’ is said to be a 'simple expansion'
| of $L$. Since $L$ and $L$’ are just sets of symbols, the expansion $L$’ may be
| written $L$’ = $L$ |_| X, where X is the set of new symbols.
|
| Chang & Keisler, 'Model Theory', pages 18-19.
|
| C.C. Chang and H.J. Keisler, 'Model Theory',
| North-Holland, Amsterdam, Netherlands, 1973.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤