key clause is 5, which says that ∀ should be interpreted as “for all

elements of the universe”.

Example 6.3. Let R be the structure for LF and s the assignment

for R given in Example 6.1, and consider the formula ∀v1 (= v3 ·0v1 ’=

v30) of LF . We can verify that R |= ∀v1 (= v3 · 0v1 ’= v30) [s] as

follows:

R |= ∀v1 (= v3 · 0v1 ’= v3 0) [s]

⇐’ for all a ∈ |R|, R |= (= v3 · 0v1 ’= v3 0) [s(v1|a)]

⇐’ for all a ∈ |R|, if R |== v3 · 0v1 [s(v1|a)],

then R |== v3 0 [s(v1|a)]

⇐’ for all a ∈ |R|, if s(v1|a)(v3) = s(v1 |a)(·0v1),

then s(v1|a)(v3) = s(v1|a)(0)

⇐’ for all a ∈ |R|, if s(v3) = s(v1|a)(0) · s(v1|a)(v1), then s(v3) = 0

⇐’ for all a ∈ |R|, if s(v3) = 0 · a, then s(v3 ) = 0

⇐’ for all a ∈ |R|, if 4 = 0 · a, then 4 = 0

⇐’ for all a ∈ |R|, if 4 = 0, then 4 = 0

. . . which last is true whether or not 4 = 0 is true or false.

Problem 6.4. Let N be the structure for LN in Problem 6.2. Let

p : V ’ N be de¬ned by p(v2k ) = k and p(v2k+1 ) = k. Verify that

1. N |= ∀w (¬Sw = 0) [p] and

2. N ∀x∃y x + y = 0 [p].

Proposition 6.5. Suppose M is a structure for L, s is an assign-

ment for M, x is a variable, and • is a formula of a ¬rst-order language

L. Then M |= ∃x •[s] if and only if M |= •[s(x|m)] for some m ∈ |M|.

Working with particular assignments is di¬cult but, while some-

times unavoidable, not always necessary.

6. STRUCTURES AND MODELS 37

Definition 6.5. Suppose M is a structure for L, and • a formula

of L. Then M |= • if and only if M |= •[s] for every assignment

s : V ’ |M| for M. M is a model of • or that • is true in M if

M |= •. We will often write M ψ if it is not the case that M |= ψ.

Similarly, if “ is a set of formulas, we will write M |= “ if M |= γ

for every formula γ ∈ “, and say that M is a model of “ or that M

satis¬es “. A formula or set of formulas is satis¬able if there is some

structure M which satis¬es it. We will often write M “ if it is not

the case that M |= “.

Note. M • does not mean that for every assignment s : V ’

|M|, it is not the case that M |= •[s]. It only means that that there is

some assignment r : V ’ |M| for which M |= •[r] is not true.

Problem 6.6. Q = (Q, <) is a structure for LO . For each of the

following formulas • of LO , determine whether or not Q |= •.

1. ∀v0 ∃v2 v0 < v2

2. ∃v1 ∀v3 (v1 < v3 ’ v1 = v3 )

3. ∀v4 ∀v5 ∀v6(v4 < v5 ’ (v5 < v6 ’ v4 < v6))

The following facts are counterparts of sorts for Proposition 2.2.

Their point is that what a given assignment does with a given term or

formula depends only on the assignment™s values on the (free) variables

of the term or formula.

Lemma 6.7. Suppose M is a structure for L, t is a term of L, and

r and s are assignments for M such that r(x) = s(x) for every variable

x which occurs in t. Then r(t) = s(t).

Proposition 6.8. Suppose M is a structure for L, • is a formula

of L, and r and s are assignments for M such that r(x) = s(x) for

every variable x which occurs free in •. Then M |= •[r] if and only if

M |= •[s].

Corollary 6.9. Suppose M is a structure for L and σ is a sen-

tence of L. Then M |= σ if and only if there is some assignment

s : V ’ |M| for M such that M |= σ[s].

Thus sentences are true or false in a structure independently of any

particular assignment. This does not necessarily make life easier when

trying to verify whether a sentence is true in a structure “ try doing

Problem 6.6 again with the above results in hand “ but it does let us

simplify things on occasion when proving things about sentences rather

than formulas.

We recycle a sense in which we used |= in propositional logic.

38 6. STRUCTURES AND MODELS

Definition 6.6. Suppose “ is a set of formulas of L and ψ is a

formula of L. Then “ implies ψ, written as “ |= ψ, if M |= ψ whenever

M |= “ for every structure M for L.

Similarly, if “ and ∆ are sets of formulas of L, then “ implies ∆,

written as “ |= ∆, if M |= ∆ whenever M |= “ for every structure M

for L.

We will usually write |= . . . for … |= . . . .

Proposition 6.10. Suppose ± and β are formulas of some ¬rst-

order language. Then { (± ’ β), ± } |= β.

Proposition 6.11. Suppose Σ is a set of formulas and ψ and ρ

are formulas of some ¬rst-order language. Then Σ ∪ {ψ} |= ρ if and

only if Σ |= (ψ ’ ρ).

Definition 6.7. A formula ψ of L is a tautology if it is true in

every structure, i.e. if |= ψ. ψ is a contradiction if ¬ψ is a tautology,

i.e. if |= ¬ψ.

For some trivial examples, let • be a formula of L and M a structure

for L. Then M |= {•} if and only if M |= •, so it must be the case

that {•} |= •. It is also easy to check that • ’ • is a tautology and

¬(• ’ •) is a contradiction.

Problem 6.12. Show that ∀y y = y is a tautology and that ∃y ¬y =

y is a contradiction.

Problem 6.13. Suppose • is a contradiction. Show that M |= •[s]

is false for every structure M and assignment s : V ’ |M| for M.

Problem 6.14. Show that a set of formulas Σ is satis¬able if and

only if there is no contradiction χ such that Σ |= χ.

The following fact is a counterpart of Proposition 2.4.

Proposition 6.15. Suppose M is a structure for L and ± and β

are sentences of L. Then:

1. M |= ¬± if and only if M ±.

2. M |= ± ’ β if and only if M |= β whenever M |= ±.

3. M |= ± ∨ β if and only if M |= ± or M |= β.

4. M |= ± § β if and only if M |= ± and M |= β.

5. M |= ± ” β if and only if M |= ± exactly when M |= β.

6. M |= ∀x ± if and only if M |= ±.

7. M |= ∃x ± if and only if there is some m ∈ |M| so that M |=

± [s(x|m)] for every assignment s for M.

Problem 6.16. How much of Proposition 6.15 must remain true

if ± and β are not sentences?

6. STRUCTURES AND MODELS 39

Recall that by Proposition 5.14 a formula of a ¬rst-order language

is also a formula of any extension of the language. The following rela-

tionship between extension languages and satis¬ability will be needed

later on.

Proposition 6.17. Suppose L is a ¬rst-order language, L is an

extension of L, and “ is a set of formulas of L. Then “ is satis¬able

in a structure for L if and only if “ is satis¬able in a structure for L .

One last bit of terminology . . .

Definition 6.8. If M is a structure for L, then the theory of M

is just the set of all sentences of L true in M, i.e.

Th(M) = { „ | „ is a sentence and M |= „ }.

If ∆ is a set of sentences and S is a collection of structures, then ∆ is

a set of (non-logical) axioms for S if for every structure M, M ∈ S if

and only if M |= ∆.

Example 6.4. Consider the sentence ∃x ∃y ((¬x = y) § ∀z (z =

x ∨ z = y)) of L= . Every structure of L= satisfying this sentence must

have exactly two elements in its universe, so { ∃x ∃y ((¬x = y)§∀z (z =

x ∨ z = y)) } is a set of non-logical axioms for the collection of sets of

cardinality 2:

{ M | M is a structure for L= with exactly 2 elements } .

Problem 6.18. In each case, ¬nd a suitable language and a set of

axioms in it for the given collection of structures.

1. Sets of size 3.

2. Bipartite graphs.

3. Commutative groups.

4. Fields of characteristic 5.

40 6. STRUCTURES AND MODELS

CHAPTER 7

Deductions

Deductions in ¬rst-order logic are not unlike deductions in propo-

sitional logic. Of course, some changes are necessary to handle the

various additional features of propositional logic, especially quanti¬ers.

In particular, one of the new axioms requires a tricky preliminary def-

inition. Roughly, the problem is that we need to know when we can

replace occurrences of a variable in a formula by a term without letting

any variable in the term get captured by a quanti¬er.

Throughout this chapter, let L be a ¬xed arbitrary ¬rst-order lan-

guage. Unless stated otherwise, all formulas will be assumed to be

formulas of L.

Definition 7.1. Suppose x is a variable, t is a term, and • is a

formula. Then t is substitutable for x in • is de¬ned as follows:

1. If • is atomic, then t is substitutable for x in •.

2. If • is (¬ψ), then t is substitutable for x in • if and only if t is

substitutable for x in ψ.

3. If • is (± ’ β), then t is substitutable for x in • if and only if t

is substitutable for x in ± and t is substitutable for x in β.

4. If • is ∀y δ, then t is substitutable for x in • if and only if either

(a) x does not occur free in •, or

(b) if y does not occur in t and t is substitutable for x in δ.

For example, x is always substitutable for itself in any formula

• and •x is just • (see Problem 7.1). On the other hand, y is not

x

substitutable for x in ∀y x = y because if x were to be replaced by y,

the new instance of y would be “captured” by the quanti¬er ∀y. This

makes a di¬erence to the truth of the formula. The truth of ∀y x = y

depends on the structure in which it is interpreted ” it™s true if the

universe has only one element and false otherwise ” but ∀y y = y is

a tautology by Problem 6.12 so it is true in any structure whatsoever.

This sort of di¬culty makes it necessary to be careful when substituting

for variables.

41

42 7. DEDUCTIONS

Definition 7.2. Suppose x is a variable, t is a term, and • is

a formula. If t is substitutable for x in •, then •x (i.e. • with t

t

substituted for x) is de¬ned as follows:

1. If • is atomic, then •x is the formula obtained by replacing each

t

occurrence of x in • by t.

2. If • is (¬ψ), then •x is the formula (¬ψt ).

x

t

3. If • is (± ’ β), then •x is the formula (±x ’ βtx).

t t

4. If • is ∀y δ, then •t is the formula

x

(a) ∀y δ if x is y, and

(b) ∀y δt if x isn™t y.

x

1. Is x substitutable for z in ψ if ψ is z = x ’

Problem 7.1.

∀z z = x? If so, what is ψx ?

z

2. Show that if t is any term and σ is a sentence, then t is substi-

x

tutable in σ for any variable x. What is σt ?

3. Show that if t is a term in which no variable occurs that occurs

in the formula •, then t is substitutable in • for any variable x.

4. Show that x is substitutable for x in • for any variable x and

any formula •, and that •x is just •.

x

Along with the notion of substitutability, we need an additional

notion in order to de¬ne the logical axioms of L.

Definition 7.3. If • is any formula and x1, . . . , xn are any vari-

ables, then ∀x1 . . . ∀xn • is said to be a generalization of •.

For example, ∀y ∀x (x = y ’ fx = fy) and ∀z (x = y ’ fx = f y)

are (di¬erent) generalizations of x = y ’ fx = f y, but ∀x ∃y (x =

y ’ fx = fy) is not. Note that the variables being quanti¬ed don™t

have to occur in the formula being generalized.

Lemma 7.2. Any generalization of a tautology is a tautology.

Definition 7.4. Every ¬rst-order language L has eight logical ax-

iom schema:

A1: (± ’ (β ’ ±))

A2: ((± ’ (β ’ γ)) ’ ((± ’ β) ’ (± ’ γ)))

A3: (((¬β) ’ (¬±)) ’ (((¬β) ’ ±) ’ β))

A4: (∀x ± ’ ±x ), if t is substitutable for x in ±.

t

A5: (∀x (± ’ β) ’ (∀x ± ’ ∀x β))

A6: (± ’ ∀x ±), if x does not occur free in ±.

A7: x = x

A8: (x = y ’ (± ’ β)), if ± is atomic and β is obtained from ±

by replacing some occurrences (possibly all or none) of x in ± by

y.

7. DEDUCTIONS 43

Plugging in any particular formulas of L for ±, β, and γ, and any

particular variables for x and y, in any of A1“A8 gives a logical axiom

of L. In addition, any generalization of a logical axiom of L is also a

logical axiom of L.

The reason for calling the instances of A1“A8 the logical axioms,

instead of just axioms, is to avoid con¬‚ict with De¬nition 6.8.

Problem 7.3. Determine whether or not each of the following for-

mulas is a logical axiom.

1. ∀x ∀z (x = y ’ (x = c ’ x = y))

2. x = y ’ (y = z ’ z = x)

3. ∀z (x = y ’ (x = c ’ y = c))

4. ∀w ∃x (P wx ’ P ww) ’ ∃x (P xx ’ P xx)

5. ∀x (∀x c = fxc ’ ∀x ∀x c = fxc)

6. (∃x P x ’ ∃y ∀z Rzfy) ’ ((∃x P x ’ ∀y ¬∀z Rzfy) ’ ∀x ¬P x)

Proposition 7.4. Every logical axiom is a tautology.

Note that we have recycled our axiom schemas A1”A3 from propo-

sitional logic. We will also recycle MP as the sole rule of inference for

¬rst-order logic.

Definition 7.5 (Modus Ponens). Given the formulas • and (• ’

ψ), one may infer ψ.

As in propositional logic, we will usually refer to Modus Ponens by

its initials, MP. That MP preserves truth in the sense of Chapter 6

follows from Problem 6.10. Using the logical axioms and MP, we can

execute deductions in ¬rst-order logic just as we did in propositional

logic.

Definition 7.6. Let ∆ be a set of formulas of the ¬rst-order lan-

guage L. A deduction or proof from ∆ in L is a ¬nite sequence

•1•2 . . . •n of formulas of L such that for each k ¤ n,

1. •k is a logical axiom, or

2. •k ∈ ∆, or

3. there are i, j < k such that •k follows from •i and •j by MP.

A formula of ∆ appearing in the deduction is usually referred to as a

premiss of the deduction. ∆ proves a formula ±, written as ∆ ±, if