II Logic and Set Theory - Predicate logic

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

is complete if for all propositions

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

-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

be a theory that is

categorical for some

, and suppose

T has no finite models. Then T is complete.

Note that the requirement that

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

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 L¨owenhein–Skolem theorems, we can find such models of cardinality

. But since one satisfies

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

→ C

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

(for

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

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

, a

, ··· , a

n−1

)(∃x)(x

+ a

n−1

+ ··· + a

x + a

= 0).

Let

ACF

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

Let

ACF

denote the theory of algebraically closed fields of characteristic

where we add the axiom

1 + 1 + ··· + 1

| {z }

p times

= 0

to ACF.

We now notice the following fact: if

is a proposition that is a theorem of

ACF

for all

, then it is true of

ACF

. Indeed, we know that

ACF

is complete.

So if

is not a theorem in

ACF

, then

¬r

is a theorem. But the proof is finite,

so it can only use finitely many instances of (

∗

). So there is some large

where

¬r can be proven in ACF

, which is a contradiction.

Now the statement “If

is a polynomial of degree

and

is injective, then

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

, we only need to prove it for some algebraically complete field of characteristic

Fix a prime

, and consider

, the algebraic closure of

. This is an

algebraically closed field with the property that every element is algebraic over

, i.e. the field generated by any finite subset of elements is finite.

Let

→ F

be a polynomial function involving coefficients

, ··· , a

Let

= (

, ··· , b

)

∈ F

be a point. Then

restricts to a function from the

field

generated by

, ··· , b

, a

, ··· , a

}

to itself. But

is finite, so any

function

F →

that is injective must also be surjective. So

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

be a theory with a countable

language. If

-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.