``The completeness theorem is an absolute highlight of all of mathematics. It's brilliant'' - Dr Leader
The number of arguments to a function is its arity.
![]() |
(5.1) |
![]() |
(5.2) |
![]() |
(5.3) |
A poset is a set A with a relation
. Conveniently
is written
.
![]() |
(5.4) |
![]() |
(5.5) |
![]() |
(5.6) |
Let the set of functions and predicates
be distinct
sets, and let the arity function be
. Then the language
is the set of all
formulae.
For groups,
. For posets,
.
A term is a subset of strings of symbols from the alphabet
.
Note that the term
is not the value of the
function
with these arguments. It is just a string. To emphasize
this you can write it
.
An atomic formula is one of
![]() |
![]() |
``not ![]() |
![]() |
![]() |
``p or q'' |
![]() |
![]() |
``p and q'' |
![]() |
![]() |
``exists x such that p'' |
An occurrence of a variable in a formula is free if it is not
within the brackets of a ``
''. Otherwise it is bound.
A sentence is a formula with no free variable (for example the axioms for groups and posets).
Let
be a language. An
-structure is a
non-empty set
, for each
a function
and for each
a subset
.
the language of groups: an
-structure is a set
with
functions
.
the language of posets: an
-structure is a non-empty set with a
relation
.
A closed term is a term with no variables. For example ,
not
.
The interpretation of a closed term in an -structure
written
is defined inductively. If
,
and
closed terms then
.
Note that if is constant symbol then
is already defined.
For a sentence and an
-structure
the interpretation
of
in
is a
defined inductively
where we extend to
by adding a new constant symbol
and make
an
-structure by setting
and for any
term
,
is the formula obtained by replacing each free
occurrence of
with
.
``Now forget all this nonsense and think of it only as in the original idea.'' - Dr Leader.
If we say
holds in
or
is true in
or
is a
model of
written
.
For a set of sentences (a theory) say
is a model of
written
if
.
For a theory,
a sentence, say
entails
written
if every model of
is a model of
.
If
we say
is a tautology.
What is called in propositional logic a valuation is like in predicate logic an interpretation.
Say that the members of a theory are axioms, and that the theory
axiomatizes the things which are models of it.
Let be the language of groups and let
Then an -structure
is a model of
iff
is a group.
axiomatizes the class of groups.
Suppose we change the third axiom to be just
to produce
. Does
axiomatize the class of groups? (Think
about it but the answer is yes).
Let language of posets and let
. Then a model for
is precisely a poset.
Let
.
. For
take
Then axiomatizes the class of fields.
Language of
and
.
.
Then an -structure on
is a
-model iff
is a graph.
This is called first-order logic. We can qualify over elements but not over subsets. For example we cannot say ``for all subgroups of ''.
Could have an alternative language for groups with
and third element of the theory being
.
Many natural theories have infinite. For example, we have fields of characteristic zero.
language of fields.
axioms of a field, with
,
etc.
Fields of non-zero characteristic. language of fields,
axioms
for a field. Can we axiomatize fields of charactistic
? (Exercise.)