instead of … ±. Finally, if “ and ∆ are sets of formulas, we™ll take

“ ∆ to mean that “ δ for every formula δ ∈ ∆.

Note. We have reused the axiom schema, the rule of inference, and

the de¬nition of deduction from propositional logic. It follows that any

44 7. DEDUCTIONS

deduction of propositional logic can be converted into a deduction of

¬rst-order logic simply by replacing the formulas of LP occurring in

the deduction by ¬rst-order formulas. Feel free to appeal to the deduc-

tions in the exercises and problems of Chapter 3. You should probably

review the Examples and Problems of Chapter 3 before going on, since

most of the rest of this Chapter concentrates on what is di¬erent about

deductions in ¬rst-order logic.

Example 7.1. We™ll show that {±} ∃x ± for any ¬rst-order for-

mula ± and any variable x.

1. (∀x ¬± ’ ¬±) ’ (± ’ ¬∀x ¬±) Problem 3.9.5

2. ∀x ¬± ’ ¬± A4

3. ± ’ ¬∀x ¬± 1,2 MP

4. ± Premiss

5. ¬∀x ¬± 3,4 MP

6. ∃x ± De¬nition of ∃

Strictly speaking, the last line is just for our convenience, like ∃ itself.

Problem 7.5. Show that:

1. ∀x • ’ ∀y •x , if y does not occur at all in •.

y

2. ± ∨ ¬±.

3. {c = d} ∀z Qazc ’ Qazd.

4. x = y ’ y = x.

5. {∃x ±} ± if x does not occur free in ±.

Many general facts about deductions can be recycled from propo-

sitional logic, including the Deduction Theorem.

Proposition 7.6. If •1 •2 . . . •n is a deduction of L, then •1 . . . •

is also a deduction of L for any such that 1 ¤ ¤ n.

δ ’ β, then “

Proposition 7.7. If “ δ and “ β.

Proposition 7.8. If “ ⊆ ∆ and “ ±, then ∆ ±.

Proposition 7.9. Then if “ ∆ and ∆ σ, then “ σ.

Theorem 7.10 (Deduction Theorem). If Σ is any set of formulas

and ± and β are any formulas, then Σ ± ’ β if and only if Σ∪{±}

β.

Just as in propositional logic, the Deduction Theorem is useful be-

cause it often lets us take shortcuts when trying to show that deductions

exist. There is also another result about ¬rst-order deductions which

often supplies useful shortcuts.

7. DEDUCTIONS 45

Theorem 7.11 (Generalization Theorem). Suppose x is a variable,

“ is a set of formulas in which x does not occur free, and • is a formula

such that “ •. Then “ ∀x •.

Theorem 7.12 (Generalization On Constants). Suppose that c is

a constant symbol, “ is a set of formulas in which c does not occur, and

• is a formula such that “ •. Then there is a variable x which does

not occur in • such that “ ∀x •c .1 Moreover, there is a deduction of

x

∀x •x from “ in which c does not occur.

c

Example 7.2. We™ll show that if • and ψ are any formulas, x is

any variable, and • ’ ψ, then ∀x • ’ ∀x ψ.

Since x does not occur free in any formula of …, it follows from

• ’ ψ by the Generalization Theorem that ∀x (• ’ ψ). But then

1. ∀x (• ’ ψ) above

2. ∀x (• ’ ψ) ’ (∀x • ’ ∀x ψ) A5

3. ∀x • ’ ∀x ψ 1,2 MP

is the tail end of a deduction of ∀x • ’ ∀x ψ from ….

Problem 7.13. Show that:

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

2. ∀x ± ’ ∃x ±.

3. ∃x γ ’ ∀x γ if x does not occur free in γ.

We conclude with a bit of terminology.

Definition 7.7. If Σ is a set of sentences, then the theory of Σ is

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

That is, the theory of Σ is just the collection of all sentences which

can be proved from Σ.

1c

•x is • with every occurence of the constant c replaced by x.

46 7. DEDUCTIONS

CHAPTER 8

Soundness and Completeness

As with propositional logic, ¬rst-order logic had better satisfy the

Soundness Theorem and it is desirable that it satisfy the Completeness

Theorem. These theorems do hold for ¬rst-order logic. The Soundness

Theorem is proved in a way similar to its counterpart for propositional

logic, but the Completeness Theorem will require a fair bit of additional

work.1 It is in this extra work that the distinction between formulas

and sentences becomes useful.

Let L be a ¬xed countable ¬rst-order language throughout this

chapter. All formulas will be assumed to be formulas of L unless stated

otherwise.

First, we rehash many of the de¬nitions and facts we proved for

propositional logic in Chapter 4 for ¬rst-order logic.

Theorem 8.1 (Soundness Theorem). If ± is a sentence and ∆ is

a set of sentences such that ∆ ±, then ∆ |= ±.

Definition 8.1. A set of sentences “ is inconsistent if “ ¬(ψ ’

ψ) for some formula ψ, and is consistent if it is not inconsistent.

Recall that a set of sentences “ is satis¬able if M |= “ for some

structure M.

Proposition 8.2. If a set of sentences “ is satis¬able, then it is

consistent.

Proposition 8.3. Suppose ∆ is an inconsistent set of sentences.

Then ∆ ψ for any formula ψ.

Proposition 8.4. Suppose Σ is an inconsistent set of sentences.

Then there is a ¬nite subset ∆ of Σ such that ∆ is inconsistent.

Corollary 8.5. A set of sentences “ is consistent if and only if

every ¬nite subset of “ is consistent.

1

This is not too surprising because of the greater complexity of ¬rst-order logic.

Also, it turns out that ¬rst-order logic is about as powerful as a logic can get and

still have the Completeness Theorem hold.

47

48 8. SOUNDNESS AND COMPLETENESS

Definition 8.2. A set of sentences Σ is maximally consistent if Σ

is consistent but Σ ∪ {„ } is inconsistent whenever „ is a sentence such

that „ ∈ Σ.

/

One quick way of ¬nding examples of maximally consistent sets is

given by the following proposition.

Proposition 8.6. If M is a structure, then Th(M) is a maximally

consistent set of sentences.

Example 8.1. M = ({5}) is a structure for L= , so Th(M) is a

maximally consistent set of sentences. Since it turns out that Th(M) =

Th ({ ∀x ∀y x = y }), this also gives us an example of a set of sentences

Σ = { ∀x ∀y x = y } such that Th(Σ) is maximally consistent.

Proposition 8.7. If Σ is a maximally consistent set of sentences,

„ is a sentence, and Σ „ , then „ ∈ Σ.

Proposition 8.8. Suppose Σ is a maximally consistent set of sen-

tences and „ is a sentence. Then ¬„ ∈ Σ if and only if „ ∈ Σ.

/

Proposition 8.9. Suppose Σ is a maximally consistent set of sen-

tences and • and ψ are any sentences. Then • ’ ψ ∈ Σ if and only if

• ∈ Σ or ψ ∈ Σ.

/

Theorem 8.10. Suppose “ is a consistent set of sentences. Then

there is a maximally consistent set of sentences Σ with “ ⊆ Σ.

The counterparts of these notions and facts for propositional logic

su¬ced to prove the Completeness Theorem, but here we will need

some additional tools. The basic problem is that instead of de¬ning a

suitable truth assignment from a maximally consistent set of formulas,

we need to construct a suitable structure from a maximally consistent

set of sentences. Unfortunately, structures for ¬rst-order languages are

usually more complex than truth assignments for propositional logic.

The following de¬nition supplies the key new idea we will use to prove

the Completeness Theorem.

Definition 8.3. Suppose Σ is a set of sentences and C is a set of

(some of the) constant symbols of L. Then C is a set of witnesses for

Σ in L if for every formula • of L with at most one free variable x,

there is a constant symbol c ∈ C such that Σ ∃x • ’ •x. c

The idea is that every element of the universe which Σ proves must

exist is named, or “witnessed”, by a constant symbol in C. Note that

if Σ ¬∃x •, then Σ ∃x • ’ •x for any constant symbol c.

c

8. SOUNDNESS AND COMPLETENESS 49

Proposition 8.11. Suppose “ and Σ are sets of sentences of L,

“ ⊆ Σ, and C is a set of witnesses for “ in L. Then C is a set of

witnesses for Σ in L.

Example 8.2. Let LO be the ¬rst-order language with a single 2-

place relation symbol, <, and countably many constant symbols, cq for

each q ∈ Q. Let Σ include all the sentences

1. cp < cq , for every p, q ∈ Q such that p < q,

2. ∀x (¬x < x),

3. ∀x ∀y (x < y ∨ x = y ∨ y < x),

4. ∀x ∀y ∀z (x < y ’ (y < z ’ x < z)),

5. ∀x ∀y (x < y ’ ∃z (x < z § z < y)),

6. ∀x ∃y (x < y), and

7. ∀x ∃y (y < x).

In e¬ect, Σ asserts that < is a linear order on the universe (2“4) which

is dense (5) and has no endpoints (6“7), and which has a suborder

isomorphic to Q (1). Then C = { cq | q ∈ Q } is a set of witnesses for

Σ in LO .

In the example above, one can “reverse-engineer” a model for the set

of sentences in question from the set of witnesses simply by letting the

universe of the structure be the set of witnesses. One can also de¬ne the

necessary relation interpreting < in a pretty obvious way from Σ.2 This

example is obviously contrived: there are no constant symbols around

which are not witnesses, Σ proves that distinct constant symbols aren™t

equal to to each other, there is little by way of non-logical symbols

needing interpretation, and Σ explicitly includes everything we need to

know about <.

In general, trying to build a model for a set of sentences Σ in this

way runs into a number of problems. First, how do we know whether

Σ has a set of witnesses at all? Many ¬rst-order languages have few or

no constant symbols, after all. Second, if Σ has a set of witnesses C,

it™s unlikely that we™ll be able to get away with just letting the universe

of the model be C. What if Σ c = d for some distinct witnesses c

and d? Third, how do we handle interpreting constant symbols which

are not in C? Fourth, what if Σ doesn™t prove enough about whatever

relation and function symbols exist to let us de¬ne interpretations of

them in the structure under construction? (Imagine, if you like, that

someone hands you a copy of Joyce™s Ulysses and asks you to produce a

complete road map of Dublin on the basis of the book. Even if it has no

Note, however, that an isomorphic copy of Q is not the only structure for LO

2

satisfying Σ. For example, R = (R, <, q +π : q ∈ Q) will also satisfy Σ if we intepret

cq by q + π.

50 8. SOUNDNESS AND COMPLETENESS

geographic contradictions, you are unlikely to ¬nd all the information

in the novel needed to do the job.) Finally, even if Σ does prove all we

need to de¬ne functions and relations on the universe to interpret the

function and relation symbols, just how do we do it? Getting around

all these di¬culties requires a fair bit of work. One can get around

many by sticking to maximally consistent sets of sentences in suitable

languages.

Lemma 8.12. Suppose Σ is a set of sentences, • is any formula,

and x is any variable. Then Σ • if and only if Σ ∀x •.

Theorem 8.13. Suppose “ is a consistent set of sentences of L.

Let C be an in¬nite countable set of constant symbols which are not

symbols of L, and let L = L∪C be the language obtained by adding the

constant symbols in C to the symbols of L. Then there is a maximally

consistent set Σ of sentences of L such that “ ⊆ Σ and C is a set of

witnesses for Σ.

This theorem allows one to use a certain measure of brute force:

No set of witnesses? Just add one! The set of sentences doesn™t decide

enough? Decide everything one way or the other!

Theorem 8.14. Suppose Σ is a maximally consistent set of sen-

tences and C is a set of witnesses for Σ. Then there is a structure M

such that M |= Σ.

The important part here is to de¬ne M ” proving that M |= Σ

is tedious but fairly straightforward if you have the right de¬nition.

Proposition 6.17 now lets us deduce the fact we really need.

Corollary 8.15. Suppose “ is a consistent set of sentences of a

¬rst-order language L. Then there is a structure M for L satisfying “.

With the above facts in hand, we can rejoin our proof of Soundness

and Completeness, already in progress:

Theorem 8.16. A set of sentences Σ in L is consistent if and only

if it is satis¬able.

The rest works just like it did for propositional logic.

Theorem 8.17 (Completeness Theorem). If ± is a sentence and

∆ is a set of sentences such that ∆ |= ±, then ∆ ±.

It follows that in a ¬rst-order logic, as in propositional logic, a

sentence is implied by some set of premisses if and only if it has a proof

from those premisses.

Theorem 8.18 (Compactness Theorem). A set of sentences ∆ is

satis¬able if and only if every ¬nite subset of ∆ is satis¬able.

CHAPTER 9

Applications of Compactness

After wading through the preceding chapters, it should be obvious

that ¬rst-order logic is, in principle, adequate for the job it was origi-

nally developed for: the essentially philosophical exercise of formalizing

most of mathematics. As something of a bonus, ¬rst-order logic can

supply useful tools for doing “real” mathematics. The Compactness

Theorem is the simplest of these tools and glimpses of two ways of

using it are provided below.

From the ¬nite to the in¬nite. Perhaps the simplest use of the

Compactness Theorem is to show that if there exist arbitrarily large

¬nite objects of some type, then there must also be an in¬nite object

of this type.

Example 9.1. We will use the Compactness Theorem to show that

there is an in¬nite commutative group in which every element is of order

2, i.e. such that g · g = e for every element g.

Let LG be the ¬rst-order language with just two non-logical sym-

bols:

• Constant symbol: e