Fraisse and Completeness from Baire Categoricity

In this post, we present the proofs of the following two theorems, using Baire’s categoricity theorem.

Theorem (Fraisse, 1954). Let \cal C 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 \str A with age \cal C.

We note that this is not the most general version of the theorem.

Theorem (Completeness; Godel, 1929). Let T be a theory such that T\not\vdash \bot. Then T 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 X be a complete metric space, and let \cal U be a family of open and dense subsets of X. Then \bigcap \cal U is dense in X.

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 U_1,U_2,\ldots be an enumeration of the elements of \cal U.
Let x_0\in X and let \eps be a number. We prove that there is an element x\in \bigcap_{i=1}^\infty U_i such that d(x,x')<\eps.
Start with i=1 and \eps_i=\eps/2. For i=1,\ldots, perform the following step. Choose an element x_{i} in the \eps_i-ball around x_{i-1}, which belongs to U_{i}; it exists since U_i is dense. Choose a positive real \eps_{i+1}<\eps_i/2 such that the \eps_{i+1}-ball around x_i is contained in
U_{i}; it exists since U_i is open. Increase i and repeat the step.

We obtain a sequence of elements x_0,x_1,\ldots with the property that d(x_i,x_j)\le \eps_i\le \eps/{2^i} for 0\le i<j. In particular, the sequence x_0,x_1,\ldots is Cauchy and by completeness, converges to some x\in X. It It follows by construction that x\in U_i for i\ge 1. This proves the theorem.\square

Fraisse’s Theorem

Let \Sigma be a signature consisting of relation or function symbols and let \cal C be a countable class of logical structures over \Sigma, closed under:

  • embeddings: if \str A\in \cal C and \str B is a structure which embeds into \str A, then \str B\in \cal C;
  • amalgamation: if \str A_1,\str A_2,\str A_0\in\cal C and f_1:\str A_0\to\str A_1 and f_2:\str A_0\to\str A_2 are embeddings, then there exists a structure \str A\in\cal C and embeddings g_1:\str A_1\to\str A and g_2:\str A_1\to\str A such that f_1;g_1=f_2;g_2.

Moreover, \cal C is assumed to have the joint embedding property, i.e., any two structures \str A and \str B in \cal C embed into a single structure \str C\in\cal C. A class \cal C with these properties is called a Fraisse class.

The age of a structure \str M is the class of all finitely generated structures  \str A which embed into \str M. A structure \str M is homogeneous if every isomorphism between two finitely generated substructures of \str M extends to an automorphism of \str M.

Fraisse’s Theorem. Let \Sigma and \cal C be as above. Then there exists a unique (up to isomorphism) countable homogeneous structure \str M with age  equal to \cal C.

Proof. We only prove the case when the signature \Sigma is finite and relational.

We prove that there exists a structure \str M with universe contained in \Nat, whose age is contained in \cal C, and which satisfies the following extension axiom denoted ex(\str A,\str B,f), for all \str A,\str B\in\cal C, where  \str A is an induced substructure of \str B, and  f:\str A\to\M is a function from the universe of \str A to the universe of \str M:

if f is an embedding of \str A to \str M, then f extends to an embedding g:\str B\to \str M.

Observe that any structure \str M satisfying the above conditions has age equal to \cal C, and that any homogeneous \str M with age \cal C must satisfy the extension axioms. Homogeneity and uniqueness of \str M follow easily from the extension axioms, using the back-and-forth method. 

It therefore remains to prove that there exists a model \str M with universe \Nat, with age contained in \cal C and which satisfies all the extension axioms.

literal is a sentence of the form R(\bar a) or \neg R(\bar a), where \bar a is a tuple of parameters from \Nat, R is a relation symbol from \Sigma or R is the symbol \mathrm{Dom}, interpreted in a model \str M as the domain of \str M

Let {\cal M}_0 be the set of all  structures with universe contained in \Nat over the signature \Sigma. {\cal M}_0 can be viewed as a topological space, with the Tychonoff topology. Explicitly, the basic open sets are specified by finite conjunctions of literals \phi, and the corresponding subset of {\cal M}_0 consists of all models \stR M such that \str M\models \phi. 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, {\cal M}_0 can be treated as a complete metric space.

Let {\cal M}_1 denote the set of  all structures \str M\in{\cal M}_0, whose age is contained in \cal C. Note that {\cal M}_1 is a closed subset of {\cal M}_0. Indeed, suppose that \str M is a structure in {\cal M}_0-{\cal M}_1; in particular, there is a tuple \bar a such that the substructure induced by \bar a does not belong to \cal C. Hence, \str M,\bar a\models\phi, where \phi is the atomic type of \bar a, and is a finite conjunction of literals (here we use the assumption that \Sigma is a finite relational signature). It follows that the basic open set defined by the formula \phi is disjoint from {\cal M}_1. Hence {\cal M}_1 is a closed set. In particular, {\cal M}_1 is a complete metric space. Note that {\cal M}_1 is nonempty, as it contains for instance the empty structure.

For an extension axiom \alpha=ex(\str A,\str B,f), consider the set G_\alpha\subset{\cal M}_0 which consists of all models \str M which satisfy the axiom \alpha. It is obvious that G_\alpha is an open subset of {\cal M}_0. We prove that G_\alpha is a dense in {\cal M}_1. Let \str M\in{\cal M}_1 and let \phi be a conjunction of literals such that \str M\models \phi. We must show that there is a model \str M'\in{\cal M}_1 such that \str M'\models\phi and \str M' satisfies the extension axiom \alpha. If f is not an embedding from \str A into \str M, then we can take \str M'=\str M. So suppose that f is an embedding from \str A into \str M. Let \str M_1 be the substructure of \str M induced by all elements which appear as parameters in the sentence \phi or in the image of f. Then f is an embedding of \str A into \str M_1, and let i denote the inclusion embedding of \str A into \str B.  By amalgamation applied to f and i, there is a structure \str M' containing \str M_1, and an embedding g:\str A\to \str M' which extends f. By construction, \str M'\models \phi  and \str M' satisfies the extension axiom \alpha. This proves that G_\alpha is dense in {\cal M}_1.

Let \cal U be the family of all sets G_\alpha\cap {\cal M}_1, for \alpha ranging over all extension axioms. By Baire’s categoricity theorem, \bigcap \cal U contains some structure \str M. Then \str M has age contained in \cal C and satisfies all the extension axioms. As discussed earlier, this implies that \str M is the unique countable homogeneous structure with age \cal C.

Completeness Theorem.

If \Sigma is a language consisting of relation or function symbols, then a theory T over the language \Sigma is a set of first order sentences over \Sigma.

Let \vdash denote some reasonable proof system for first order logic.

Completeness theorem. Let T_0 be a theory over a countable language \Sigma such that T_0\not\vdash\bot. Then T_0 has a countable model.

Proof sketch. Without loss of generality, we assume that \Sigma 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 \sim and adding to T_0 axioms which require that \sim is an equivalence relation preserved by all other relations in \Sigma.

Let \Sigma' be the language \Sigma\cup\set{c_0,c_1,\ldots}, where c_0,c_1,\ldots are constant symbols. Let {\cal T}_0 denote the set of all theories T over \Sigma' which are maximal, i.e., for every sentence \phi over \Sigma', exactly one of \phi,\neg\phi belongs to T. We treat {\cal T}_0 as a topological space, in which each basic open set is specified by a finite theory \Delta, and consists of all theories T extending \Delta. Then {\cal T}_0 is a compact metrizable topological space, and we can therefore treat it as a complete metric space.

Let {\cal T}_1 be the set of all maximal theories T\in {\cal T}_0 such that T_0\subset T and T\not\vdash\bot. The set {\cal T}_1 is  a closed subset of {\cal T}_0, since it is specified by a conjunction of clopen conditions. In particular, {\cal T}_1 is a complete nonempty metric space. Moreover, it is not difficult to prove that {\cal T}_1 is nonempty (by starting with T'=T and repeatedly adding to T' all sentences \phi over \Sigma' such that T'\not\vdash\phi).

Let \phi be a formula over \Sigma' with one free variable x, and let c be a constant in \Sigma'. We say that a theory \Delta over \Sigma' satisfies the axiom sp(\phi) if the following implication holds:

\exists x.\phi\in \Delta implies \phi[c/x]\in\Delta for some constant c in \Sigma'.

For an axiom \sigma=sp(\phi), let G_\sigma\subset {\cal T}_0 denote the set of all theories \Delta  which satisfy \sigma. Clearly, G_\sigma is an open subset of {\cal T}_0. We show that G_\sigma is dense in {\cal T}_1. Let T\in{\cal T}_1 and let \Delta\subset T be a finite set of sentences. We must show that there is a theory T'\in{\cal T}_1 containing \Delta and such that T' satisfies \sigma. If T does not contain the sentence \exists x.\phi then we may take T'=T. Therefore, assume that T contains the sentence \exists x.\phi, and let \Delta'=T_0\cup\Delta, and let  c be any constant from \Sigma' which is not mentioned in \Delta nor in \phi. We claim that \Delta'\cup\set{\phi[x/c]}  is consistent – otherwise, we would have \Delta',\phi[x/c]\vdash\bot and our reasonable proof system implies that \Delta',\exists x.\phi\vdash\bot, implying  T\vdash\bot, a contradiction. Let T' be a maximal consistent extension of \Delta'\cup\set{\phi[x/c]}. Then T' satisfies \sigma and contains T; in particular T'\in G_\sigma\cap {\cal T}_1; moreover, T' contains \Delta. Since \Delta\subset T be chosen arbitrarily, this proves that G_\sigma\cap {\cal T}_1 is dense in {\cal T}_1.

Let \cal U be the family of all sets G_\sigma\cap {\cal T}_1, for \sigma ranging over all axioms sp(\phi). By Baire’s categoricity theorem, there is a theory T\in\bigcap \cal U. Let \str M be the model in which the constant c_i is interpreted as the number i, for i\in\Nat, and the relations in \Sigma are defined as specified by the atomic sentences in T. It follows easily by induction on \phi that \str M\models \phi for every sentence \phi\in T. In particular, \str M is a model of T_0.\square


Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>