ńņš. 5 |

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 |