<<

. 7
( 11 .)



>>

± is the last formula of a deduction from ∆. We™ll usually write ±
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

<<

. 7
( 11 .)



>>