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 .