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.