4Predicate logic
II Logic and Set Theory
4 Predicate logic
In the first chapter, we studied propositional logic. However, it isn’t sufficient
for most mathematics we do.
In, say, group theory, we have a set of objects, operations and constants. For
example, in group theory, we have the operations multiplication
m
:
A
2
→ A
,
inverse
i
:
A → A
, and a constant
e ∈ A
. For each of these, we assign a number
known as the arity, which specifies how many inputs each operation takes. For
example, multiplication has arity 2, inverse has arity 1 and
e
has arity 0 (we can
view e as a function A
0
→ A, that takes no inputs and gives a single output).
The study of these objects is known as predicate logic. Compared to proposi-
tional logic, we have a much richer language, which includes all the operations
and possibly relations. For example, with group theory, we have
m, i, e
in our
language, as well as things like
∀
,
⇒
etc. Note that unlike propositional logic,
different theories give rise to different languages.
Instead of a valuation, now we have a structure, which is a solid object plus
the operations and relations required. For example, a structure of group theory
will be an actual concrete group with the group operations.
Similar to what we did in propositional logic, we will take
S |
=
t
to mean
“for any structure in which
S
is true,
t
is true”. For example, “Axioms of group
theory”
|
=
m
(
e, e
) =
e
, i.e. in any set that satisfies the group axioms,
m
(
e, e
) =
e
.
We also have S ⊢ t meaning we can prove t from S.