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.

A 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$

Atompress

Fraisse and Completeness from Baire Categoricity

Baire’s Theorem

Fraisse’s Theorem

Completeness Theorem.

Leave a Reply Cancel reply

Computation with atoms