In this post, we present the proofs of the following two theorems, using Baire’s categoricity theorem.
Theorem (Fraisse, 1954). Let be a countable class of relational structures over a finite relational signature, which is closed under induced substructures and under amalgamation. Then there is a homogeneous structure
with age
.
We note that this is not the most general version of the theorem.
Theorem (Completeness; Godel, 1929). Let be a theory such that
. Then
has a countable model.
The standard proofs of these theorems involve some sort of constructions which proceed in stages, in each stage satisfying some requests which appeared in the previous stages. The proofs presented below rely on the following.
Theorem (Categoricity; Baire, 1899). Let be a complete metric space, and let
be a family of open and dense subsets of
. Then
is dense in
.
The first proof of Godel’s completeness theorem using Baire’s categoricity theorem appeared in Mathematics of Metamathematics (1963) by Helena Rasiowa (my great-great-phd-grand-mother) and Roman Sikorski. I don’t know who was the first to prove Fraisse’s result using Baire’s categoricity; definitely it is not new in this post (see e.g. W. Kubiś, Fraisse sequences: category-theoretic approach to universal homogeneous structures). Other applications of Baire’s categoricity theorem in logic include the Omitting Type’s theorem and Forcing.
Baire’s Theorem
We first sketch the proof of Baire’s theorem.
Let be an enumeration of the elements of
.
Let and let
be a number. We prove that there is an element
such that
.
Start with and
. For
, perform the following step. Choose an element
in the
-ball around
, which belongs to
; it exists since
is dense. Choose a positive real
such that the
-ball around
is contained in
; it exists since
is open. Increase
and repeat the step.
We obtain a sequence of elements with the property that
for
. In particular, the sequence
is Cauchy and by completeness, converges to some
. It It follows by construction that
for
. This proves the theorem.
Fraisse’s Theorem
Let be a signature consisting of relation or function symbols and let
be a countable class of logical structures over
, closed under:
- embeddings: if
and
is a structure which embeds into
, then
;
- amalgamation: if
and
and
are embeddings, then there exists a structure
and embeddings
and
such that
.
Moreover, is assumed to have the joint embedding property, i.e., any two structures
and
in
embed into a single structure
. A class
with these properties is called a Fraisse class.
The age of a structure is the class of all finitely generated structures
which embed into
. A structure
is homogeneous if every isomorphism between two finitely generated substructures of
extends to an automorphism of
.
Fraisse’s Theorem. Let and
be as above. Then there exists a unique (up to isomorphism) countable homogeneous structure
with age equal to
.
Proof. We only prove the case when the signature is finite and relational.
We prove that there exists a structure with universe contained in
, whose age is contained in
, and which satisfies the following extension axiom denoted
, for all
, where
is an induced substructure of
, and
is a function from the universe of
to the universe of
:
if is an embedding of
to
, then
extends to an embedding
.
Observe that any structure satisfying the above conditions has age equal to
, and that any homogeneous
with age
must satisfy the extension axioms. Homogeneity and uniqueness of
follow easily from the extension axioms, using the back-and-forth method.
It therefore remains to prove that there exists a model with universe
, with age contained in
and which satisfies all the extension axioms.
A literal is a sentence of the form or
, where
is a tuple of parameters from
,
is a relation symbol from
or
is the symbol
, interpreted in a model
as the domain of
.
Let be the set of all structures with universe contained in
over the signature
.
can be viewed as a topological space, with the Tychonoff topology. Explicitly, the basic open sets are specified by finite conjunctions of literals
, and the corresponding subset of
consists of all models
such that
. An open set is a (arbitrary) union of basic open sets. It is well-known (and easy to see) that this topology is compact and metrizable. In particular,
can be treated as a complete metric space.
Let denote the set of all structures
, whose age is contained in
. Note that
is a closed subset of
. Indeed, suppose that
is a structure in
; in particular, there is a tuple
such that the substructure induced by
does not belong to
. Hence,
, where
is the atomic type of
, and is a finite conjunction of literals (here we use the assumption that
is a finite relational signature). It follows that the basic open set defined by the formula
is disjoint from
. Hence
is a closed set. In particular,
is a complete metric space. Note that
is nonempty, as it contains for instance the empty structure.
For an extension axiom , consider the set
which consists of all models
which satisfy the axiom
. It is obvious that
is an open subset of
. We prove that
is a dense in
. Let
and let
be a conjunction of literals such that
. We must show that there is a model
such that
and
satisfies the extension axiom
. If
is not an embedding from
into
, then we can take
. So suppose that
is an embedding from
into
. Let
be the substructure of
induced by all elements which appear as parameters in the sentence
or in the image of
. Then
is an embedding of
into
, and let
denote the inclusion embedding of
into
. By amalgamation applied to
and
, there is a structure
containing
, and an embedding
which extends
. By construction,
and
satisfies the extension axiom
. This proves that
is dense in
.
Let be the family of all sets
, for
ranging over all extension axioms. By Baire’s categoricity theorem,
contains some structure
. Then
has age contained in
and satisfies all the extension axioms. As discussed earlier, this implies that
is the unique countable homogeneous structure with age
.
Completeness Theorem.
If is a language consisting of relation or function symbols, then a theory
over the language
is a set of first order sentences over
.
Let denote some reasonable proof system for first order logic.
Completeness theorem. Let be a theory over a countable language
such that
. Then
has a countable model.
Proof sketch. Without loss of generality, we assume that consists of only relation symbols. We prove the theorem for first order logic without equality. The case for first order logic with equality follows easily, by introducing an additional relation symbol
and adding to
axioms which require that
is an equivalence relation preserved by all other relations in
.
Let be the language
, where
are constant symbols. Let
denote the set of all theories
over
which are maximal, i.e., for every sentence
over
, exactly one of
belongs to
. We treat
as a topological space, in which each basic open set is specified by a finite theory
, and consists of all theories
extending
. Then
is a compact metrizable topological space, and we can therefore treat it as a complete metric space.
Let be the set of all maximal theories
such that
and
. The set
is a closed subset of
, since it is specified by a conjunction of clopen conditions. In particular,
is a complete nonempty metric space. Moreover, it is not difficult to prove that
is nonempty (by starting with
and repeatedly adding to
all sentences
over
such that
).
Let be a formula over
with one free variable
, and let
be a constant in
. We say that a theory
over
satisfies the axiom
if the following implication holds:
implies
for some constant
in
.
For an axiom , let
denote the set of all theories
which satisfy
. Clearly,
is an open subset of
. We show that
is dense in
. Let
and let
be a finite set of sentences. We must show that there is a theory
containing
and such that
satisfies
. If
does not contain the sentence
then we may take
. Therefore, assume that
contains the sentence
, and let
, and let
be any constant from
which is not mentioned in
nor in
. We claim that
is consistent – otherwise, we would have
and our reasonable proof system implies that
, implying
, a contradiction. Let
be a maximal consistent extension of
. Then
satisfies
and contains
; in particular
; moreover,
contains
. Since
be chosen arbitrarily, this proves that
is dense in
.
Let be the family of all sets
, for
ranging over all axioms
. By Baire’s categoricity theorem, there is a theory
. Let
be the model in which the constant
is interpreted as the number
, for
, and the relations in
are defined as specified by the atomic sentences in
. It follows easily by induction on
that
for every sentence
. In particular,
is a model of
.