4Predicate logic
II Logic and Set Theory
4.2 Semantic entailment
In propositional logic, we can’t say whether a proposition is true or false unless
we have a valuation. What would be a “valuation” in the case of predicate logic?
It is a set with the operations of the right arity. We call this a structure.
For example, in the language of groups, a structure is a set
G
with the correct
operations. Note that it does not have to satisfy the group axioms in order to
qualify as a structure.
Definition (Structure). An
L
-structure is a non-empty set
A
with a function
f
A
:
A
n
→ A
for each
f ∈
Ω
, α
(
f
) =
n
, and a relation
ϕ
A
⊆ A
n
, for each
ϕ ∈
Π,
α(ϕ) = n.
Note that we explicitly forbid
A
from being empty. It is possible to formulate
predicate logic that allows empty structures, but we will have to make many
exceptions when defining our axioms, as we will see later. Since empty structures
are mostly uninteresting (and don’t exist if there is at least one constant), it
isn’t a huge problem if we ignore it. (There is a small caveat here — we are
working with single-sorted logic here, so everything is of the same “type”. If
we want to work with multi-sorted logic, where there can be things of different
types, it would then be interesting to consider the case where some of the types
could be empty).
Example. In the language of posets
A
, a structure is a set
A
with a relation
≤
A
⊆ A × A.
In the language of groups, a structure is a set
A
with functions
m
A
:
A×A →
A, i
A
: A → A and e
A
∈ A.
Again, these need not be genuine posets/groups since we do not have the
axioms yet.
Now we want to define “
p
holds in
A
” for a sentence
p ∈ L
and a
L
-structure
A.
For example, we want (
∀x
)(
m
(
x, x
) =
e
) to be true in
A
iff for each
a ∈ A
,
we have
m
A
(
a, a
) =
e
A
. So to translate
p
into something about
A
, you “add
subscript
A
to each function-symbol and relation-symbol, insert
∈ A
after the
quantifiers, and say it aloud”. We call this the interpretation of the sentence p.
This is not great as a definition. So we define it formally, and then quickly
forget about it.
Definition (Interpretation). To define the interpretation
p
A
∈ 0, 1
for each
sentence p and L-structure A, we define inductively:
(i) Closed terms: define t
A
∈ A for each closed term t by
(ft
1
, ··· , t
n
)
A
= f
A
(t
1
A
, t
2
A
··· , t
n
A
)
for any f ∈ Ω, α(f ) = n, and closed terms t
1
, ··· , t
n
.
Example. (m(m(e, e), e))
A
= m
A
(m
A
(e
A
, e
A
), e
A
).
(ii) Atomic formulae:
⊥
A
= 0
(s = t)
A
=
(
1 s
A
= t
A
0 s
A
= t
A
(ϕt
1
···t
n
)
A
=
(
1 (t
1
A
, ··· , t
n
A
) ∈ ϕ
A
0 otherwise
.
(iii) Sentences:
(p ⇒ q)
A
=
(
0 p
A
= 1, q
A
= 0
1 otherwise
((∀x)p)
A
=
(
1 p[¯a/x]
¯
A
for all a ∈ A
0 otherwise
where for any
a ∈ A
, we define a new language
L
′
by adding a constant
¯a
and make A into an L
′
structure
¯
A by setting ¯a
¯
A
= a.
Now that we have formally defined truth, just forget about it!
Note that we have only defined the interpretation only for sentences. We
can also define it for functions with free variables. For any formula
p
with
n
free
variables, we can define the interpretation as the set of all things that satisfy
p
.
For example, if p is (∃y)(m(y, y) = a), then
p
A
= {a ∈ A : ∃b ∈ A such that m(b, b) = a}.
However, we are mostly interested in sentences, and don’t have to worry about
these.
Now we can define models and entailment as in propositional logic.
Definition (Theory). A theory is a set of sentences.
Definition (Model). If a sentence
p
has
p
A
= 1, we say that
p
holds in
A
, or
p
is true in A, or A is a model of p.
For a theory S, a model of S is a structure that is a model for each s ∈ S.
Definition (Semantic entailment). For a theory
S
and a sentence
t
,
S
entails
t
,
written as S |= t, if every model of S is a model of t.
“Whenever S is true, t is also true”.
Definition (Tautology).
t
is a tautology, written
|
=
t
, if
∅ |
=
t
, i.e. it is true
everywhere.
Example. (∀x)(x = x) is a tautology.
Example.
(i) Groups:
–
The language
L
is Ω = (
m, i, e
) and Π =
∅
, with arities 2, 1, 0
respectively.
– Let T be
{(∀x)(∀y)(∀z)m(x, m(y, z)) = m(m(x, y), z),
(∀x)(m(x, e) = x ∧ m(e, x) = x),
(∀x)(m(x, i(x)) = e ∧ m(i(x), x) = e)}.
Then an
L
-structure
A
is a model for
T
iff
A
is a group. We say
T
axiomatizes the theory of groups/class of groups. Sometimes we call the
members of T the axioms of T .
Note that we could use a different language and theory to axiomatize group
theory. For example, we can have Ω = (
m, e
) and change the last axiom to
(∀x)(∃y)(m(x, y) = e ∧ m(y, x) = e)}.
(ii) Fields:
–
The language
L
is Ω = (+
, ×, −,
0
,
1) and Π =
∅
, with arities 2, 2, 1,
0, 0.
– The theory T consists of:
◦ Abelian group under +
◦ × is commutative, associative, and distributes over +
◦ ¬(0 = 1)
◦ (∀x)((¬(x = 0)) ⇒ (∃y)(y ×x = 1).
Then an
L
-structure is a model of
T
iff it is a field. Then we have
T |= ”inverses are unique”, i.e.
T |= (∀x)
¬(x = 0)
⇒ (∀y)(∀z)
(xy = 1 ∧ xz = 1) ⇒ (y = z)
(iii) Posets:
– The language is Ω = ∅, and Π = {≤} with arity 2.
– The theory T is
{(∀x)(x ≤ x),
(∀x)(∀y)(∀z)
(x ≤ y) ∧ (y ≤ z) ⇒ x ≤ z
,
(∀x)(∀y)
x ≤ y ∧y ≤ z ⇒ x = y
}
Then T axiomatizes the theory of posets.
(iv) Graphs:
–
The language
L
is Ω =
∅
and Π =
{a}
with arity 2. This relation is
“adjacent to”. So a(x, y) means there is an edge between x and y.
– The theory is
{(∀x)(¬a(x, x)),
(∀x)(∀y)(a(x, y) ⇔ a(y, x)}
Predicate logic is also called “first-order logic”. It is “first-order” because our
quantifiers range over elements of the structure only, and not subsets. It would
be difficult (and in fact impossible) to axiomatize, say, a complete ordered field,
since the definition requires says every bounded subset has a least upper bound.