4Predicate logic
II Logic and Set Theory
4.1 Language of predicate logic
We start with the definition of the language. This is substantially more compli-
cated than what we’ve got in propositional logic.
Definition (Language). Let Ω (function symbols) and Π (relation symbols) be
disjoint sets, and α : Ω ∪ Π → N a function (’arity’).
The language L = L(Ω, Π, α) is the set of formulae, defined as follows:
–
Variables: we have some variables
x
1
, x
2
, ···
. Sometimes (i.e. always), we
write x, y, z, ··· instead.
– Terms: these are defined inductively by
(i) Every variable is a term
(ii)
If
f ∈
Ω,
α
(
f
) =
n
, and
t
1
, ··· , t
n
are terms, then
ft
1
···t
n
is a term.
We often write f (t
1
, ··· , t
n
) instead.
Example. In the language of groups Ω =
{m, i, e}
, Π =
∅
, and
α
(
m
) =
2, α(i) = 1, α(e) = 0. Then e, x
1
, m(x
1
, x
2
), i(m(x
1
, x
1
)) are terms.
– Atomic formulae: there are three sorts:
(i) ⊥
(ii) (s = t) for any terms s, t.
(iii) (ϕt
1
···t
n
) for any ϕ ∈ Π with α(ϕ) = n and t
1
, ··· , t
n
terms.
Example. In the language of posets, Ω =
∅
, Π =
{≤}
and
α
(
≤
) = 2.
Then (x
1
= x
1
), x
1
≤ x
2
(really means (≤ x
1
x
2
)) are atomic formulae.
– Formulae: defined inductively by
(i) Atomic formulae are formulae
(ii) (p ⇒ q) is a formula for any formulae p, q.
(iii) (∀x)p is a formula for any formula p and variable x.
Example. In the language of groups,
e
=
e
,
x
1
=
e
,
m
(
e, e
) =
e
,
(
∀x
)
m
(
x, i
(
x
)) =
e
, (
∀x
)(
m
(
x, x
) =
e ⇒
(
∃y
)(
m
(
y, y
) =
x
)) are formu-
lae.
It is important to note that a formula is a string of meaningless symbol. It
doesn’t make sense to ask whether it is true or false. In particular, the function
and relation symbols are not assigned any meaning. The only thing the language
cares is the arity of the symbol.
Again, we have the usual abbreviations
¬p
,
p ∧ q
,
p ∨ q
etc. Also, we have
(∃x)p for ¬(∀x)(¬p).
Definition (Closed term). A term is closed if it has no variables.
Example. In the language of groups,
e, m
(
e, e
) are closed terms. However,
m
(
x, i
(
x
)) is not closed even though we think it is always
e
. Apart from the
fact that it is by definition not closed (it has a variable
x
), we do not have the
groups axioms stating that m(x, i(x)) = e.
Definition (Free and bound variables). An occurrence of a variable
x
in a
formula
p
is bound if it is inside brackets of a (
∀x
) quantifier. It is free otherwise.
Example. In (∀x)(m(x, x) = e), x is a bound variable.
In (∀y)(m(y, y) = x ⇒ m(x, y) = m(y, x)), y is bound while x is free.
We are technically allowed to have a formula with
x
both bound and free,
but DO NOT DO IT. For example,
m
(
x, x
) =
e ⇒
(
∀x
)(
∀y
)(
m
(
x, y
) =
m
(
y, x
))
is a valid formula (first two x are free, while the others are bound).
Definition (Sentence). A sentence is a formula with no free variables.
Example.
m
(
e, e
) =
e
and (
∀x
)(
m
(
x, x
) =
e
) are sentences, while
m
(
x, i
(
x
)) =
e
is not.
Definition (Substitution). For a formula
p
, a variable
x
and a term
t
, the
substitution p[t/x] is obtained by replacing each free occurrence of x with t.
Example. If
p
is the statement (
∃y
)(
m
(
y, y
) =
x
), then
p
[
e/x
] is (
∃y
)(
m
(
y, y
) =
e.