[ Pobierz całość w formacie PDF ]
Throughout this chapter, let L be an arbitrary fixed countable first-
order language. All formulas will be assumed to be formulas of L unless
stated otherwise.
Definition 6.1. A structure M for L consists of the following:
1. A non-empty set M, often written as |M|, called the universe of
M.
2. For each constant symbol c of L, an element cM of M.
3. For each k-place function symbol f of L, a function fM : Mk ’!
M, i.e. a k-place function on M.
4. For each k-place relation symbol P of L, a relation PM †" Mk,
i.e. a k-place relation on M.
That is, a structure supplies an underlying set of elements plus in-
terpretations for the various non-logical symbols of the language: con-
stant symbols are interpreted by particular elements of the underlying
set, function symbols by functions on this set, and relation symbols by
relations among elements of this set.
It is customary to use upper-case gothic characters such as M
and N for structures.
For example, consider Q =(Q,
relation on the rationals. This is a structure for LO, the language for
linear orders defined in Example 5.2; it supplies a 2-place relation to
33
34 6. STRUCTURES AND MODELS
interpret the language s 2-place relation symbol. Q is not the only
possible structure for LO: (R,
among infinitely many more. (Note that in these cases the relation
symbol
linear orders. One can ensure that a structure satisfy various condi-
tions beyond what Definition 6.1 guarantees by requiring appropriate
formulas to be true when interpreted in the structure.) On the other
hand, (R) is not a structure for LO because it lacks a binary relation
to interpret the symbol
for LO because it has two binary relations where LO has a symbol only
for one, plus constants and functions for which LO lacks symbols.
Problem 6.1. The first-order languages referred to below were all
defined in Example 5.2.
1. Is (") a structure for L=?
2. Determine whether Q = (Q,
LF, and LS.
3. Give three different structures for LF which are not fields.
To determine what it means for a given formula to be true in a
structure for the corresponding language, we will also need to specify
how to interpret the variables when they occur free. (Bound variables
have the associated quantifier to tell us what to do.)
Definition 6.2. Let V = { v0, v1, v2, . . .} be the set of all variable
symbols of L and suppose M is a structure for L. A function s : V ’!
|M| is said to be an assignment for M.
Note that these are not truth assignments like those for LP. An
assignment just interprets each variable in the language by an element
of the universe of the structure. Also, as long as the universe of the
structure has more than one element, any variable can be interpreted
in more than one way. Hence there are usually many different possible
assignments for a given structure.
Example 6.1. Consider the structure R = (R, 0, 1, +, ·) for LF.
Each of the following functions V ’! R is an assignment for R:
1. p(vn) =À for each n,
2. r(vn) =en for each n, and
3. s(vn) =n +1 for each n.
In fact, every function V ’! R is an assignment for R.
In order to use assignments to determine whether formulas are true
in a structure, we need to know how to use an assignment to interpret
each term of the language as an element of the universe.
6. STRUCTURES AND MODELS 35
Definition 6.3. Suppose M is a structure for L and s: V ’!|M|
is an assignment for M. Let T be the set of all terms of L. Then the
extended assignment s: T ’!|M| is defined inductively as follows:
1. For each variable x, s(x) =s(x).
2. For each constant symbol c, s(c) =cM.
3. For every k-place function symbol f and terms t1, . . . , tk,
s(ft1 . . . tk) =fM(s(t1), . . . ,s(tk)).
Example 6.2. Let R be the structure for LF given in Example
6.1, and let p, r, and s be the extended assignments corresponding to
the assignments p, r, and s defined in Example 6.1. Consider the term
+ · v6v0 +0v3 of LF. Then:
1. p(+ · v6v0 +0v3) =À2 + À,
2. r(+ · v6v0 +0v3) =e6 + e3, and
3. s(+ · v6v0 +0v3) = 11.
Here s why for the last one: since s(v6) = 7, s(v0) = 1, s(v3) = 4,
and s(0) = 0 (by part 2 of Definition 6.3), it follows from part 3 of
Definition 6.3 that s(+ · v6v0 +0v3) =(7 · 1) + (0 + 4) = 7 + 4 = 11.
Problem 6.2. N = (N, 0, S, +, ·, E) is a structure for LN. Let
s: V ’! N be the assignment defined by s(vk) = k +1. What are
s(E + v19v1 · 0v45) and s(SSS + E0v6v7)?
Proposition 6.3. s is unique, i.e. given an assignment s, no other
function T ’!|M| satisfies conditions 1 3 in Definition 6.3.
With Definitions 6.2 and 6.3 in hand, we can take our first cut at
defining what it means for a first-order formula to be true.
Definition 6.4. Suppose M is a structure for L, s is an assignment
for M, and Õ is a formula of L. Then M |= Õ[s] is defined as follows:
1. If Õ is t1 = t2 for some terms t1 and t2, then M |= Õ[s] if and
only if s(t1) =s(t2).
2. If Õ is Pt1 . . .tk for some k-place relation symbol P and terms
t1, . . . , tk, then M |= Õ[s] if and only if (s(t1), . . .,s(tk)) " PM,
i.e. PM is true of (s(t1), . . .,s(tk)).
[ Pobierz całość w formacie PDF ]