<<

. 6
( 11 .)



>>

essentially identical to the corresponding parts of De¬nition 2.1. The
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

<<

. 6
( 11 .)



>>