<<

. 5
( 11 .)



>>

(((¬∀v1 (¬ = v1 c7)) ’ P3 v5v8) ’ ∀v8(= v8 f5 c0 v1v5 ’ P2 v8))
2 3 1


in the language L1 , then the set of subformulas of •, S(•), ought to
include
• = v1c7 , P3 v5v8, = v8f5 c0 v1v5 , P2 v8 ,
2 3 1

• (¬ = v1c7 ), (= v8f5 c0 v1v5 ’ P2 v8),
3 1

• ∀v1 (¬ = v1 c7), ∀v8(= v8f5 c0 v1v5 ’ P2 v8),
3 1

• (¬∀v1 (¬ = v1 c7)),
• (¬∀v1 (¬ = v1 c7)) ’ P3 v5v8), and
2

• (((¬∀v1 (¬ = v1c7 )) ’ P3 v5 v8) ’ ∀v8(= v8f5 c0 v1v5 ’ P2 v8))
2 3 1

itself.
Second, we will need a concept that has no counterpart in proposi-
tional logic.
Definition 5.4. Suppose x is a variable of a ¬rst-order language
L. Then x occurs free in a formula • of L is de¬ned as follows:
1. If • is atomic, then x occurs free in • if and only if x occurs in
•.
2. If • is (¬±), then x occurs free in • if and only if x occurs free
in ±.
3. If • is (β ’ δ), then x occurs free in • if and only if x occurs
free in β or in δ.
4. If • is ∀vk ψ, then x occurs free in • if and only if x is di¬erent
from vk and x occurs free in ψ.
An occurrence of x in • which is not free is said to be bound . A formula
σ of L in which no variable occurs free is said to be a sentence.
Part 4 is the key: it asserts that an occurrence of a variable x
is bound instead of free if it is in the “scope” of an occurrence of
∀x. For example, v7 is free in ∀v5 = v5v7, but v5 is not. Di¬erent
occurences of a given variable in a formula may be free or bound,
depending on where they are; e.g. v6 occurs both free and bound in
∀v0 (= v0f3 v6 ’ (¬∀v6 P9 v6 )).
1 1
30 5. LANGUAGES

Problem 5.11. Give a precise de¬nition of the scope of a quanti-
¬er.
Note the distinction between sentences and ordinary formulas intro-
duced in the last part of De¬nition 5.4. As we shall see, sentences are
often more tractable and useful theoretically than ordinary formulas.
Problem 5.12. Which of the formulas you gave in solving Prob-
lem 5.8 are sentences?
Finally, we will eventually need to consider a relationship between
¬rst-order languages.
Definition 5.5. A ¬rst-order language L is an extension of a ¬rst-
order language L, sometimes written as L ⊆ L , if every non-logical
symbol of L is a non-logical symbol of the same kind of L .
For example, every ¬rst-order language is an extension of L= .
Problem 5.13. Which of the languages given in Example 5.2 are
extensions of other languages given in Example 5.2?
Proposition 5.14. Suppose L is a ¬rst-order language and L is
an extension of L. Then every formula • of L is a formula of L .
Common Conventions. As with propositional logic, we will often
use abbreviations and informal conventions to simplify the writing of
formulas in ¬rst-order languages. In particular, we will use the same
additional connectives we used in propositional logic, plus an additional
quanti¬er, ∃ (“there exists”):
• (± § β) is short for (¬(± ’ (¬β))).
• (± ∨ β) is short for ((¬±) ’ β).
• (± ” β) is short for ((± ’ β) § (β ’ ±)).
• ∃vk • is short for (¬∀vk (¬•)).
(∀ is often called the universal quanti¬er and ∃ is often called the
existential quanti¬er.)
Parentheses will often be omitted in formulas according to the same
conventions we used in propositional logic, with the modi¬cation that
∀ and ∃ take precedence over all the logical connectives:
• We will usually drop the outermost parentheses in a formula,
writing ± ’ β instead of (± ’ β) and ¬± instead of (¬±).
• We will let ∀ take precedence over ¬, and ¬ take precedence over
’ when parentheses are missing, and ¬t the informal abbrevia-
tions into this scheme by letting the order of precedence be ∀, ∃,
¬, §, ∨, ’, and ”.
5. LANGUAGES 31

• Finally, we will group repetitions of ’, ∨, §, or ” to the right
when parentheses are missing, so ± ’ β ’ γ is short for (± ’
(β ’ γ)).
For example, ∃vk ¬± ’ ∀vn β is short for ((¬∀vk (¬(¬±))) ’ ∀vnβ).
On the other hand, we will sometimes add parentheses and arrange
things in uno¬cial ways to make terms and formulas easier to read. In
particular we will often write
1. f(t1 , . . . , tk ) for ft1 . . . tk if f is a k-place function symbol and
t1 , . . . , tk are terms,
2. s —¦ t for —¦st if —¦ is a 2-place function symbol and s and t are
terms,
3. P (t1 , . . . , tk ) for P t1 . . . tk if P is a k-place relation symbol and
t1 , . . . , tk are terms,
4. s•t for •st if • is a 2-place relation symbol and s and t are terms,
and
5. s = t for = st if s and t are terms, and
6. enclose terms in parentheses to group them.
Thus, we could write the formula = +1 · 0v6 · 11 of LN T as 1 + (0 · v6) =
1 · 1.
As was observed in Example 5.1, it is customary in devising a formal
language to recycle the same symbols used informally for the given
objects. In situations where we want to talk about symbols without
committing ourselves to a particular one, such as when talking about
¬rst-order languages in general, we will often use “generic” choices:
• a, b, c, . . . for constant symbols;
• x, y, z, . . . for variable symbols;
• f, g, h, . . . for function symbols;
• P , Q, R, . . . for relation symbols; and
• r, s, t, . . . for generic terms.
These can be thought of as variables in the metalanguage4 ranging over
di¬erent kinds objects of ¬rst-order logic, much as we™re already using
lower-case Greek characters as variables which range over formulas. (In
fact, we have already used some of these conventions in this chapter
... )

Unique Readability. The slightly paranoid might ask whether
De¬nitions 5.1, 5.2 and 5.3 actually ensure that the terms and formulas
4
The metalanguage is the language, mathematical English in this case, in which
we talk about a language. The theorems we prove about formal logic are, strictly
speaking, metatheorems, as opposed to the theorems proved within a formal logical
system. For more of this kind of stu¬, read some philosophy . . .
32 5. LANGUAGES

of a ¬rst-order language L are unambiguous, i.e. cannot be read in
more than one way. As with LP , to actually prove this one must
assume that all the symbols of L are distinct and that no symbol is a
subsequence of any other symbol. It then follows that:
Theorem 5.15. Any term of a ¬rst-order language L satis¬es ex-
actly one of conditions 1“3 in De¬nition 5.2.
Theorem 5.16 (Unique Readability Theorem). Any formula of a
¬rst-order language satis¬es exactly one of conditions 1“5 in De¬nition
5.3.
CHAPTER 6


Structures and Models

De¬ning truth and implication in ¬rst-order logic is a lot harder
than it was in propositional logic. First-order languages are intended
to deal with mathematical objects like groups or linear orders, so it
makes little sense to speak of the truth of a formula without specifying
a context. For example, one can write down a formula expressing the
commutative law in a language for group theory, ∀x ∀y x · y = y · x,
but whether it is true or not depends on which group we™re dealing
with. It follows that we need to make precise which mathematical
objects or structures a given ¬rst-order language can be used to discuss
and how, given a suitable structure, formulas in the language are to
be interpreted. Such a structure for a given language should supply
most of the ingredients needed to interpret formulas of the language.
Throughout this chapter, let L be an arbitrary ¬xed countable ¬rst-
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 f M : M k ’
M, i.e. a k-place function on M.
4. For each k-place relation symbol P of L, a relation P M ⊆ M k ,
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, <), where < is the usual “less than”
relation on the rationals. This is a structure for LO , the language for
linear orders de¬ned 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, <), ({0}, …), and (N, N2) are three others
among in¬nitely many more. (Note that in these cases the relation
symbol < is interpreted by relations on the universe which are not
linear orders. One can ensure that a structure satisfy various condi-
tions beyond what De¬nition 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 < by, while (N, 0, 1, +, ·, |, <) is not a structure
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 ¬rst-order languages referred to below were all
de¬ned in Example 5.2.
1. Is (…) a structure for L= ?
2. Determine whether Q = (Q, <) is a structure for each of L= ,
LF , and LS .
3. Give three di¬erent structures for LF which are not ¬elds.
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 quanti¬er 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 di¬erent 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 de¬ned 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 ) = f M (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 de¬ned in Example 6.1. Consider the term
+ · v6v0 + 0v3 of LF . Then:
1. p(+ · v6 v0 + 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 De¬nition 6.3), it follows from part 3 of
De¬nition 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 de¬ned by s(vk ) = k + 1. What are
s(E + v19v1 · 0v45 ) and s(SSS + E0v6 v7)?
Proposition 6.3. s is unique, i.e. given an assignment s, no other
function T ’ |M| satis¬es conditions 1“3 in De¬nition 6.3.
With De¬nitions 6.2 and 6.3 in hand, we can take our ¬rst cut at
de¬ning what it means for a ¬rst-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 de¬ned 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 P t1 . . . tk for some k-place relation symbol P and terms
t1 , . . . , tk , then M |= •[s] if and only if (s(t1 ), . . . , s(tk )) ∈ P M ,
i.e. P M is true of (s(t1 ), . . . , s(tk )).
3. If • is (¬ψ) for some formula ψ, then M |= •[s] if and only if it
is not the case that M |= ψ[s].
4. If • is (± ’ β), then M |= •[s] if and only if M |= β[s] whenever
M |= ±[s], i.e. unless M |= ±[s] but not M |= β[s].
5. If • is ∀x δ for some variable x, then M |= •[s] if and only if for
all m ∈ |M|, M |= δ[s(x|m)], where s(x|m) is the assignment
36 6. STRUCTURES AND MODELS

given by
s(vk ) if vk is di¬erent from x
s(x|m)(vk ) =
m if vk is x.
If M |= •[s], we shall say that M satis¬es • on assignment s or that
• is true in M on assignment s. We will often write M •[s] if it is
not the case that M |= •[s]. Also, if “ is a set of formulas of L, we
shall take M |= “[s] to mean that M |= γ[s] for every formula γ in “
and say that M satis¬es “ on assignment s. Similarly, we shall take
M “[s] to mean that M γ[s] for some formula γ in “.
Clauses 1 and 2 are pretty straightforward and clauses 3 and 4 are

<<

. 5
( 11 .)



>>