Basic Logic, Lecture 7
Luca Incurvati
[email protected]
Luca Incurvati ([email protected]) Basic Logic 7 1 / 34
Outline
1 Compactness and Löwenheim-Skolem
2 Expressive power
3 Expressive power of FOL and FOL with identity
4 Proving strong completeness: first-order logic with identity
5 Löwenheim-Skolem again
Luca Incurvati ([email protected]) Basic Logic 7 2 / 34
Compactness and Löwenheim-Skolem
Compactness
We have proved strong soundness and strong completeness for
first-order logic.
This means that first-order logic is strongly axiomatisable.
This has two important corollaries:
Corollary 1 (Compactness of first-order logic)
First-order logic is compact.
Proof.
In the first lecture we showed that if a logic is strongly axiomatisable, it is
compact.
Luca Incurvati ([email protected]) Basic Logic 7 3 / 34
Compactness and Löwenheim-Skolem
Löwenheim-Skolem
Corollary 2 (Löwenheim-Skolem Theorem)
Let Φ be a set of sentences of first-order logic. If Φ has a model, then it
has a denumerably infinite model (i.e. a model whose domain is
denumerably infinite).
Proof.
Luca Incurvati ([email protected]) Basic Logic 7 4 / 34
Compactness and Löwenheim-Skolem
Löwenheim-Skolem
Corollary 2 (Löwenheim-Skolem Theorem)
Let Φ be a set of sentences of first-order logic. If Φ has a model, then it
has a denumerably infinite model (i.e. a model whose domain is
denumerably infinite).
Proof.
Take an arbitrary set Φ of sentences of first-order logic and suppose that it
has a model. By strong soundness, Φ is consistent. Now in the course of
proving strong completeness, we showed how to extend any consistent set
Φ of sentences of first-order logic to a special set Φ? and how to build a
model for Φ? . This model consists of denumerably infinitely many
constants and is also a model of Φ. Thus, Φ has a denumerably infinite
model.
Luca Incurvati ([email protected]) Basic Logic 7 4 / 34
Expressive power
1 Compactness and Löwenheim-Skolem
2 Expressive power
3 Expressive power of FOL and FOL with identity
4 Proving strong completeness: first-order logic with identity
5 Löwenheim-Skolem again
Luca Incurvati ([email protected]) Basic Logic 7 5 / 34
Expressive power
Definability
Let us consider two ways to measure the expressive power of a logic.
Definition (Definability by a sentence)
A property P is definable by a sentence σ of a given logic iff for every
interpretation I, I has the property P iff σ is true in I.
That is, a property P is definable by a sentence σ just in case the
interpretations with property P are all and only those interpretations
that are models of σ.
Luca Incurvati ([email protected]) Basic Logic 7 6 / 34
Expressive power
Definability
Definition (Definability by a set of sentences)
A property P is definable by a set of sentences σ of a given logic iff for
every interpretation I, I has the property P iff each member of σ is true
in I.
That is, a property P is definable by a sentence σ just in case the
interpretations with property P are all and only those interpretations
that are models of σ.
Luca Incurvati ([email protected]) Basic Logic 7 7 / 34
Expressive power
Expressive power of logics
If P is definable by a sentence, it is definable by a set of sentences
(just take the set whose only member is the sentence in question).
If P is definable by a finite set of sentences, it is definable by a
sentence (just take the conjunction of the members of the set).
Luca Incurvati ([email protected]) Basic Logic 7 8 / 34
Expressive power
Expressive power of logics
If P is definable by a sentence, it is definable by a set of sentences
(just take the set whose only member is the sentence in question).
If P is definable by a finite set of sentences, it is definable by a
sentence (just take the conjunction of the members of the set).
If P is definable by a set of sentences, however, it need not be
definable by a sentence (because it may be definable only by an
infinite set of sentences, in which case we cannot take the conjunction
of the members of the set).
We can assess and compare the expressive power of logics by
considering the range of properties of interpretations which are
definable within them and in which of the two ways.
Luca Incurvati ([email protected]) Basic Logic 7 8 / 34
Expressive power of FOL and FOL with identity
1 Compactness and Löwenheim-Skolem
2 Expressive power
3 Expressive power of FOL and FOL with identity
4 Proving strong completeness: first-order logic with identity
5 Löwenheim-Skolem again
Luca Incurvati ([email protected]) Basic Logic 7 9 / 34
Expressive power of FOL and FOL with identity
On the expressive power of first-order logic
Corollary 2 above tells us that none of the following properties is
first-order definable in either of the two senses of definability:
(i) The property of having a domain with exactly one member, the
property of having a domain with exactly two members, and so on for
any particular finite size.
(ii) The property of having a finite domain.
(iii) The property of having a nondenumerably infinite domain.
Luca Incurvati ([email protected]) Basic Logic 7 10 / 34
Expressive power of FOL and FOL with identity
On the expressive power of first-order logic with identity
The compactness of first-order logic is a corollary of its strong
axiomatisability.
But as we shall see below, first-order logic with identity is strongly
axiomatisable too.
Thus, first-order logic with identity too is compact, and Corollary 1
continues to hold if we replace ‘first-order logic’ with ‘first-order logic
with identity’.
Luca Incurvati ([email protected]) Basic Logic 7 11 / 34
Expressive power of FOL and FOL with identity
On the expressive power of first-order logic with identity
In the first lecture, we used compactness to show that if a set of
sentences of first-order logic with identity has arbitrarily large finite
models, then it has an infinite model. Hence, we have:
(i) The property of having a finite domain is not definable by a set of
sentences (and so not by a sentence) of first-order logic with identity.
Luca Incurvati ([email protected]) Basic Logic 7 12 / 34
Expressive power of FOL and FOL with identity
On the expressive power of first-order logic with identity
In the first lecture, we used compactness to show that if a set of
sentences of first-order logic with identity has arbitrarily large finite
models, then it has an infinite model. Hence, we have:
(i) The property of having a finite domain is not definable by a set of
sentences (and so not by a sentence) of first-order logic with identity.
(ii) In contrast with first-order logic, the property of having a domain
with exactly one member, the property of having a domain with
exactly two members, and so on for any particular finite size are
definable by single sentences of first-order logic with identity.
(For instance, ‘∃x∃y (x 6= y ∧ ∀z(z = x ∨ z = y ))’ defines the
property of having a domain with exactly two members.)
Luca Incurvati ([email protected]) Basic Logic 7 12 / 34
Expressive power of FOL and FOL with identity
On the expressive power of first-order logic with identity
(iii) In contrast with first-order logic, the property of having an infinite
domain is definable by an infinite set of sentences of first-order logic
with identity.
(Consider the set
{∃x(x = x), ∃x∃y (x 6= y ), ∃x∃y ∃z(x 6= y ∧ x 6= z ∧ y 6= z), . . .}.)
(iv) However, the property of having an infinite domain is not definable by
a single sentence of first-order logic with identity.
(For suppose this property is definable by the sentence S. Then ¬S
defines the property of having a finite domain. But (i) tells us that
there is no such sentence.)
Luca Incurvati ([email protected]) Basic Logic 7 13 / 34
Expressive power of FOL and FOL with identity
The failure of Corollary 2 for FOL with identity
(ii) entails that Corollary 2 fails for first-order logic with identity.
Corollary 2 was proved by using strong soundness and the particular
details of the proof of strong completeness.
Luca Incurvati ([email protected]) Basic Logic 7 14 / 34
Expressive power of FOL and FOL with identity
The failure of Corollary 2 for FOL with identity
(ii) entails that Corollary 2 fails for first-order logic with identity.
Corollary 2 was proved by using strong soundness and the particular
details of the proof of strong completeness.
Since FOL with identity is strongly sound, it is the second step that
must fail.
In particular, the proof of strong completeness for first-order logic
with identity cannot show that any consistent set of sentences of
first-order logic with identity has a denumerably infinite model.
Luca Incurvati ([email protected]) Basic Logic 7 14 / 34
Proving strong completeness: first-order logic with identity
1 Compactness and Löwenheim-Skolem
2 Expressive power
3 Expressive power of FOL and FOL with identity
4 Proving strong completeness: first-order logic with identity
5 Löwenheim-Skolem again
Luca Incurvati ([email protected]) Basic Logic 7 15 / 34
Proving strong completeness: first-order logic with identity
The structure of the proof
Similarly to the previous cases, assume that we are given a standard,
textbook deductive system for first-order logic with identity.
The outline of the proof is the usual one, and as in the case of
first-order logic we show to extend an arbitrary consistent set of
sentences Φ to a maximally consistent, ω-complete set of sentences
Φ? .
Luca Incurvati ([email protected]) Basic Logic 7 16 / 34
Proving strong completeness: first-order logic with identity
The structure of the proof
Similarly to the previous cases, assume that we are given a standard,
textbook deductive system for first-order logic with identity.
The outline of the proof is the usual one, and as in the case of
first-order logic we show to extend an arbitrary consistent set of
sentences Φ to a maximally consistent, ω-complete set of sentences
Φ? .
Next, we need to describe an interpretation I such that for any
sentence ϕ, ϕ is true in I iff ϕ ∈ Φ? .
In the first-order case, it was proved that this is the case by proving a
basis clause and inductive clause.
The basis clause will have to split into two, because it will have to
deal with atomic sentences which feature the identity symbol as well
as those which don’t.
Luca Incurvati ([email protected]) Basic Logic 7 16 / 34
Proving strong completeness: first-order logic with identity
The old interpretation I
In the proof of strong completeness for first-order logic, we specified
the interpretation I as follows:
The domain D of I is the denumerably infinite set of individual
constants of the expanded language.
The valuation V assigns objects to individual constants and set of
n-tuples to n-place predicates as follows:
1 Each individual constant is assigned itself.
2 Each predicate φn of degree n is assigned a set of ordered n-tuples of
individual constants from D such that ha1 , a2 , . . . , an i is a member of
the set iff φn a1 , a2 , . . . an ∈ Φ? .
Luca Incurvati ([email protected]) Basic Logic 7 17 / 34
Proving strong completeness: first-order logic with identity
The problem with the old interpretation I
The way we specified I in the first-order case had the immediate
consequence that ϕ is true in I iff ϕ ∈ Φ? for any atomic sentence ϕ.
However, that specification will not do in the case of first-order logic
of identity.
This is because the identity symbol is treated as a logical constant, as
the relevant clause of the definition of truth in an interpretation
makes clear:
If ϕ is an atomic sentence α = β then ϕ is true in I iff V(α) is
identical to V(β).
Luca Incurvati ([email protected]) Basic Logic 7 18 / 34
Proving strong completeness: first-order logic with identity
The problem with the old interpretation I
Now on the interpretation I we used in the first-order case, each
individual constant was assigned itself.
And this has the consequence that no sentence of the form α = β
(where α and β are two different individual constants) is true in I, for
the obvious reason that α and β are two different constants and so
their extensions are distinct.
But it might be the case that α = β ∈ Φ? , which would make the
biconditional ‘ϕ is true in I iff ϕ ∈ Φ? ’ false for sentences of the form
α = β.
Luca Incurvati ([email protected]) Basic Logic 7 19 / 34
Proving strong completeness: first-order logic with identity
Modifying the old interpretation I
Thus, we need to modify the definition of V so that α = β is true in
I just in case α = β ∈ Φ? .
We want to assign the same object to two constants α and β just in
case α = β ∈ Φ? but still have to make do only with what we have,
namely expressions (and set-theoretic operations on them).
Luca Incurvati ([email protected]) Basic Logic 7 20 / 34
Proving strong completeness: first-order logic with identity
Modifying the old interpretation I
Thus, we need to modify the definition of V so that α = β is true in
I just in case α = β ∈ Φ? .
We want to assign the same object to two constants α and β just in
case α = β ∈ Φ? but still have to make do only with what we have,
namely expressions (and set-theoretic operations on them).
The obvious solution is to resort to equivalence classes: we assign to
each constant an equivalence class of constants in such a way that
the same equivalence class is assigned to two constants α and β just
in case α = β ∈ Φ? :
For any individual constant α, V(α) is the equivalence class of constants
such that, for any constant β, β is in it iff α = β ∈ Φ? . (Thus, in
particular, the equivalence class contains α)
Luca Incurvati ([email protected]) Basic Logic 7 20 / 34
Proving strong completeness: first-order logic with identity
Modifying the old interpretation I
In other words, we take the set of individual constants and use the
equivalence relation ‘x = y ’ ∈ Φ? to induce a partition of this set
into equivalence classes.
The domain of the interpretation is the set of all these equivalence
classes (the quotient set of the set of individual constants by
‘x = y ’ ∈ Φ? ).
Luca Incurvati ([email protected]) Basic Logic 7 21 / 34
Proving strong completeness: first-order logic with identity
Modifying the old interpretation I
In other words, we take the set of individual constants and use the
equivalence relation ‘x = y ’ ∈ Φ? to induce a partition of this set
into equivalence classes.
The domain of the interpretation is the set of all these equivalence
classes (the quotient set of the set of individual constants by
‘x = y ’ ∈ Φ? ).
We assign to each individual constant the equivalence class of
constants of which it is a member.
Luca Incurvati ([email protected]) Basic Logic 7 21 / 34
Proving strong completeness: first-order logic with identity
The new interpretation gives us what we want
Theorem 3
For every maximally consistent, ω-complete set of sentences Φ? , there is
an interpretation I such that ϕ is true in I iff ϕ ∈ Φ? .
Proof.
We need to define the required interpretation I = hD, Ii. First, we define
the following relation on the set Θ of individual constants:
α ∼ β iff α = β ∈ Φ?
It is not hard to prove that ∼ is an equivalence relation on Θ. Next, we
use ∼ to induce a partition of Θ into equivalence classes. In particular, we
define for every α ∈ Θ the set [α]∼ as follows:
[α]∼ = {β|β ∼ α}
Luca Incurvati ([email protected]) Basic Logic 7 22 / 34
Proving strong completeness: first-order logic with identity
The new interpretation gives us what we want
Proof continued.
The domain of the interpretation is the set of all these equivalence classes,
that is
D = {[α]∼ |α ∈ Θ}
The valuation V is defined as follows:
1 For any individual constant γ, V(γ) = [γ]∼ .
2 For each predicate θn of degree n and individual constants
γ1 , γ2 , . . . , γn from D, h[γ1 ]∼ , [γ2 ]∼ , . . . , [γn ]∼ i ∈ V(θn ) iff
θn γ1 , γ2 , . . . γn ∈ Φ? .
Luca Incurvati ([email protected]) Basic Logic 7 23 / 34
Proving strong completeness: first-order logic with identity
The new interpretation gives us what we want
Proof continued.
Next, we prove by induction on the complexity of sentences, that for every
sentence ϕ, ϕ is true in I iff ϕ ∈ Φ? .
(i) ϕ is an atomic sentence. If ϕ is θn γ1 , γ2 , . . . γn , then we reason as in
the first-order case. If ϕ is α = β, then ϕ is true in I iff V(α) = V(β)
(by the relevant clause of the definition of truth in an interpretation).
But we have specified I so that V(α) = V(β) iff α = β ∈ Φ? . Thus,
α = β is true in I iff α = β ∈ Φ? . This establishes that ϕ is true in I
iff ϕ ∈ Φ? for ϕ an atomic sentence.
The proofs of the other cases can be adapted from the first-order case.
Luca Incurvati ([email protected]) Basic Logic 7 24 / 34
Proving strong completeness: first-order logic with identity
The new interpretation gives us what we want
Thus, we have:
Theorem 4 (Strong completeness of FOL= )
Let ϕ be a sentence and Γ be a set of sentences of LFOL= . If Γ |= ϕ then
Γ ` ϕ.
Luca Incurvati ([email protected]) Basic Logic 7 25 / 34
Löwenheim-Skolem again
1 Compactness and Löwenheim-Skolem
2 Expressive power
3 Expressive power of FOL and FOL with identity
4 Proving strong completeness: first-order logic with identity
5 Löwenheim-Skolem again
Luca Incurvati ([email protected]) Basic Logic 7 26 / 34
Löwenheim-Skolem again
The cardinality of the new interpretation I
The domain of the interpretation I we have specified to prove the
strong completeness of first-order logic with identity contains a
number of equivalence classes of individual constants.
How many? At least one, in case there is just one equivalence class
containing all the individual constants.
At most denumerably infinitely many, for instance in the case where
each equivalence class contains exactly one individual constant.
Thus, I is a model of Φ? whose domain is at most denumerably
infinite.
Luca Incurvati ([email protected]) Basic Logic 7 27 / 34
Löwenheim-Skolem again
Downward Löwenheim-Skolem
This fact puts us in a position to prove something similar to Corollary
2 for first-order logic with identity:
Corollary 5 (Downward Löwenheim-Skolem Theorem)
Let Φ be a set of sentences of first-order logic with identity. If Φ has a
model, then it has a model which is at most denumerably infinite (i.e. a
model whose domain is at most denumerably infinite).
Proof.
Luca Incurvati ([email protected]) Basic Logic 7 28 / 34
Löwenheim-Skolem again
Downward Löwenheim-Skolem
This fact puts us in a position to prove something similar to Corollary
2 for first-order logic with identity:
Corollary 5 (Downward Löwenheim-Skolem Theorem)
Let Φ be a set of sentences of first-order logic with identity. If Φ has a
model, then it has a model which is at most denumerably infinite (i.e. a
model whose domain is at most denumerably infinite).
Proof.
Take an arbitrary set Φ of sentences of first-order logic with identity and
suppose that it has a model. By strong soundness, Φ is consistent. Now in
the course of proving strong completeness, we showed how to extend any
consistent set Φ of sentences of first-order logic with identity to a special
set Φ? and how to build a model for Φ? . This model consists of at most
denumerably infinitely many objects and is also a model of Φ. Thus, Φ has
a model which is at most denumerably infinite.
Luca Incurvati ([email protected]) Basic Logic 7 28 / 34
Löwenheim-Skolem again
Remarks on Corollary 3
Corollary 3 is compatible with the existence of sentences of first-order
logic with identity which define the property of having a particular
finite size.
But it does entail that there is no set of sentences of first-order logic
with identity (and hence no sentence) which defines the property of
having a nondenumerably infinite domain.
Luca Incurvati ([email protected]) Basic Logic 7 29 / 34
Löwenheim-Skolem again
Remarks on Corollary 3
Corollary 3 is compatible with the existence of sentences of first-order
logic with identity which define the property of having a particular
finite size.
But it does entail that there is no set of sentences of first-order logic
with identity (and hence no sentence) which defines the property of
having a nondenumerably infinite domain.
In particular, then, if Zermelo-Fraenkel set theory with the Axiom of
Choice (formulated in first-order logic with identity) has a model,
then it has model which is at most denumerably infinite, even though
the theory proves a sentence which says, on the intended
interpretation, ‘There is a set whose cardinality is larger than that of
the set of natural numbers’.
This is known as Skolem’s Paradox.
Luca Incurvati ([email protected]) Basic Logic 7 29 / 34
Löwenheim-Skolem again
Upward Löwenheim-Skolem
Is there a set of sentences of first-order logic that defines the property
of having a denumerably infinite domain?
Theorem 4 below tells us that the answer to this question is negative.
N.B.: We need to make use of the fact that the logic obtained from
first-order logic with identity where we allow nondenumerably
infinitely many constants is compact.
This follows from the strong completeness of that logic, which is
proved using Zorn’s Lemma.
Luca Incurvati ([email protected]) Basic Logic 7 30 / 34
Löwenheim-Skolem again
Upward Löwenheim-Skolem
Theorem 6 (Upward Löwenheim-Skolem Theorem)
Let Φ be a set of sentences of first-order logic with identity. If Φ has an
infinite model, then for every infinite cardinal κ, Φ has a model of
cardinality at least κ.
Proof.
Take an arbitrary set Φ of sentences of first-order logic with identity and
suppose that it has a model A with infinite domain A. We want show that
Φ has a model whose domain has cardinality at least κ.
Luca Incurvati ([email protected]) Basic Logic 7 31 / 34
Löwenheim-Skolem again
Upward Löwenheim-Skolem
Proof continued.
We add to the language of first-order logic κ many new individual
constants a1 , a2 , . . . and consider Φ0 = Φ ∪ {a1 6= a2 , a2 6= a3 , . . .}. Now
consider an arbitrary finite ∆ ⊆ Φ0 . Only finitely many of the new
constants occur in the sentences of ∆ and the domain A of the original
model A is infinite. We can therefore simply consider the interpretation
A0 , which is exactly like A except that we extend the valuation function so
that each of new constants is assigned to a distinct element of A.
Luca Incurvati ([email protected]) Basic Logic 7 32 / 34
Löwenheim-Skolem again
Upward Löwenheim-Skolem
Proof continued.
This will ensure that A0 is a model of ai 6= aj (with i 6= j) for each such
sentence appearing in ∆. Moreover, A0 is a model of whichever subset of
Φ is in ∆ (for A is a model of Φ and hence so is A0 ). Thus, A0 is a model
of ∆.
We have shown that every finite subset ∆ of Φ0 has a model. By
compactness (in the more general form mentioned earlier), Φ0 has a model
too. Call this model B and consider the model B0 obtained from B by
restricting its valuation function to the constants and predicates in the
language of Φ (i.e. the language of first-order logic). B0 is a model of Φ.
Moreover, B0 has cardinality at least κ, since it has the same domain as
B, which is a model of {a1 6= a2 , a2 6= a3 , . . .} where there are κ-many
a1 , a2 , . . .
Luca Incurvati ([email protected]) Basic Logic 7 33 / 34
Löwenheim-Skolem again
References
On Skolem’s Paradox:
T.Skolem, ‘Some Remarks on Axiomatized Set Theory’, in J.van
Heijenoort (ed.), From Frege to Gödel, pp. 290301.
P.Benacerraf, ‘Skolem and the Skeptic’, Proceedings of the Aristotelian
Society 59 (1985).
C.Wright, ‘Skolem and the Skeptic’, Proceedings of the Aristotelian
Society 59 (1985).
Luca Incurvati ([email protected]) Basic Logic 7 34 / 34
