4Predicate logic

II Logic and Set Theory



4.5 Completeness and categoricity*
We now study some “completeness” property of theories. For convenience, we
will assume that the language is countable.
Definition (Complete theory). A theory
T
is complete if for all propositions
p
in the language, either T p or T ¬p.
Complete theories are rather hard to find. So for the moment, we will content
ourselves by just looking at theories that are not complete.
Example. The theory of groups is not complete, since the proposition
(g)(h)(gh = hg)
can neither be proven or disproven (there are abelian groups and non-abelian
groups).
Another “completeness” notion we might be interested in is categoricity. We
will need to use the notion of a cardinal, which will be introduced later in the
course. Roughly, a cardinal is a mathematical object that denotes the sizes of
sets, and a set “has cardinality κ if it bijects with κ.
Definition (
κ
-categorical). Let
κ
be an infinite cardinal. Then a theory
T
is
κ
-categorical if there is a unique model of the theory of cardinality
κ
up to
isomorphism.
Here the notion of “isomorphism” is the obvious one a homomorphism of
models is a function between the structures that preserves everything, and an
isomorphism is a homomorphism with an inverse (that is also a homomorphism).
Example (Pure identity theory). The pure identity theory has an empty language
and no axioms. Then this theory is
κ
-categorical for any
κ
, since if two models
have the same cardinality, then by definition there is a bijection between them,
and any such bijection is an isomorphism because there are no properties to be
preserve.
One nice thing about categorical theories is that they are complete!
Proposition. Let
T
be a theory that is
κ
categorical for some
κ
, and suppose
T has no finite models. Then T is complete.
Note that the requirement that
T
has no finite models is necessary. For
example, pure identity theory is
κ
-categorical for all
κ
but is not complete, since
the statement (x)(y)(¬(x = y)) is neither provable nor disprovable.
Proof.
Let
p
be a proposition. Suppose
T ⊢ p
and
T ⊢ ¬p
. Then there are
infinite models of
T {p}
and
T p}
(since the models cannot be finite), and
so by the owenhein–Skolem theorems, we can find such models of cardinality
κ
. But since one satisfies
p
and the other does not, they cannot be isomorphic.
This contradicts κ-categoricity.
We are now going to use this idea to prove the Ax-Grothendieck theorem
Theorem (Ax-Grothendieck theorem). Let
f
:
C
n
C
n
be a complex polyno-
mial. If f is injective, then it is in fact a bijection.
We will use the following result from field theory without proof:
Lemma. Any two uncountable algebraically closed fields with the same di-
mension and same characteristic are isomorphic. In other words, the theory of
algebraically closed fields of characteristic
p
(for
p
a prime or 0) is
κ
-categorical
for all uncountable cardinals κ, and in particular complete.
The rough idea (for the field theorists) is that an algebraically closed field is
uniquely determined by its transcendence degree over the base field Q or F
p
.
In the following proof, we will also use some (very) elementary results about
field theory that can be found in IID Galois Theory.
Proof of Ax-Grothendieck.
We will use compactness and completeness to show
that we only have to prove this for fields of positive characteristic, and the result
can be easily proven since we end up dealing with finite fields.
Let
ACF
be the theory of algebraically closed fields. The language is the
language of rings, and the axioms are the usual axioms of a field, plus the
following axiom for each n > 0:
(a
0
, a
1
, ··· , a
n1
)(x)(x
n
+ a
n1
x
n1
+ ··· + a
1
x + a
0
= 0).
Let
ACF
0
denote the theory of algebraically closed fields of characteristic 0,
where we add the axiom
1 + 1 + ··· + 1
| {z }
n times
= 0 ()
for all n to ACF
n
.
Let
ACF
p
denote the theory of algebraically closed fields of characteristic
p
,
where we add the axiom
1 + 1 + ··· + 1
| {z }
p times
= 0
to ACF.
We now notice the following fact: if
r
is a proposition that is a theorem of
ACF
p
for all
p
, then it is true of
ACF
0
. Indeed, we know that
ACF
0
is complete.
So if
r
is not a theorem in
ACF
0
, then
¬r
is a theorem. But the proof is finite,
so it can only use finitely many instances of (
). So there is some large
p
where
¬r can be proven in ACF
p
, which is a contradiction.
Now the statement “If
f
is a polynomial of degree
d
and
f
is injective, then
f
is surjective” can be expressed as a first-order statement. So we just have to
prove it for all fields of characteristic
p >
0. Moreover, by completeness, for each
p
, we only need to prove it for some algebraically complete field of characteristic
p.
Fix a prime
p
, and consider
F
=
¯
F
p
, the algebraic closure of
F
p
. This is an
algebraically closed field with the property that every element is algebraic over
F
p
, i.e. the field generated by any finite subset of elements is finite.
Let
f
:
F
n
F
n
be a polynomial function involving coefficients
a
1
, ··· , a
K
.
Let
b
= (
b
1
, ··· , b
n
)
F
n
be a point. Then
F
restricts to a function from the
field
˜
F
generated by
{b
1
, ··· , b
n
, a
1
, ··· , a
K
}
to itself. But
˜
F
is finite, so any
function
f|
˜
F
:
˜
F
˜
F
that is injective must also be surjective. So
b
is in the
image of f. So f is surjective. So done.
We conclude the section by stating, without proof, a theorem by Morely:
Theorem (Morley’s categoricity theorem). Let
T
be a theory with a countable
language. If
T
is
κ
-categorical for some uncountable cardinal
κ
, then it is
µ-categorical for all uncountable cardinals µ.
Hence we often just say a theory is uncountably categorical when the theory
is categorical for some (hence all) uncountable cardinals.