6
$\begingroup$

What is the relation between omitting types theorems in model theory and the baire category theorem?

$\endgroup$
1
  • 2
    $\begingroup$ If you read Spanish, you may want to try and get a copy of Julián Mariño's Undergraduate Thesis at the Universidad de los Andes in Bogotá, which is on essentially this question. I have a copy somewhere on a pile at my office. $\endgroup$ Sep 16, 2013 at 5:42

1 Answer 1

6
$\begingroup$

OK, found the thesis.

What you can prove is that the omitting types theorem follows from the Baire category theorem. I haven't thought about whether the other direction holds in the sense of reverse mathematics.

One starts by fixing a signature $\tau$, and assigning an appropriate topology to the space $\mathcal E_\tau$ of $\tau$-structures. This is a proper class, but the topology has a set-sized basis, so arguments can be formalized in a straightforward fashion.

The topology of elementary classes is defined by picking as a basis the classes of the form $M_\tau(\phi)$ for $\phi$ a $\tau$-sentence. Here, $M_\tau(\phi)$ simply denotes the class of $\tau$-structures that satisfy $\phi$. Similarly, if $\Phi$ is a set of sentences (a theory), then $M_\tau(\Phi)=\bigcap_{\phi\in\Phi}M_\tau(\phi)$ is the class of models of $\Phi$.

This topology is not quite metrizable, but admits a uniform structure: A basis of uniformity is attained by considering the relations $\equiv_\Phi$, where $\Phi$ varies over the finite sets of $\tau$-sentences, and two $\tau$-structures $\mathcal M$ and $\mathcal N$ are $\Phi$-equivalent, $\mathcal M\equiv_\Phi\mathcal N$ iff for each $\phi\in\Phi$, we have that $\mathcal M\models\phi$ iff $\mathcal N\models\phi$.

As a consequence, $\mathcal E_\tau$ is regular and (if $\tau$ is countable) it is pseudo-metrizable, with pseudo-metric $$d(\mathcal M,\mathcal N)=\inf\{1/n\mid\mathcal M\models_{\Phi_n}\mathcal N\},$$ where $\phi_1,\phi_2,\dots$ enumerates the $\tau$-sentences and $\Phi_n=\{\phi_i\mid i< n\}$.

Notoriously, the space is complete (every Cauchy net converges to an ultraproduct of the members of the net) and compact (and logical compactness can be seen as a consequence of this).

The topological version of the omitting types theorem then takes the following form:

Theorem. Let $\tau$ be a countable signature, and let $T$ be a consistent theory in this language. Let $C$ be a countable set if constant symbols, disjoint from $\tau$. Let $\Sigma(x)$ be a $1$-type in language $\tau$. If for all $c\in C$ we have that $$ M_{\tau\cup C}(T\cup\Sigma(c))$$ is closed nowhere dense in $M_{\tau\cup C}(T)$, then there is a (countable) model of $T$ that omits $\Sigma(x)$.

The point is that $T$ locally omits $\Sigma(x)$ iff for any $c\in C$, the open class $M_{\tau\cup C}(T\cup\Sigma(c))$ has empty interior in $M_{\tau\cup C}(T)$. The key to this argument is that if $\tau'$ expands $\tau$, then the projections $$ P_{\tau'\tau}:\mathcal E_{\tau'}\to\mathcal E_\tau $$ (that map $\tau'$-structures to their restrictions to $\tau$) are uniformly continuous.

This can be used to give an essentially topological proof of the omitting types theorem, as a consequence of the Baire category theorem, as follows: Letting $\phi(x)$ vary over all $\tau\cup C$-formulas in one free variable $x$, define $$ X=\bigcap_{\phi(x)}\bigcup_{i\in\mathbb N}M_{\tau\cup C}(\exists x\phi(x)\to\phi(c_i)). $$ The important properties of $X$ are that it is a dense $G_\delta$ subset of $\mathcal E_{\tau\cup C}$, the projection $P_{\tau\cup C,\tau}\upharpoonright X:X\to\mathcal E_\tau$ is continuous, open, and onto, and $$ X=\{\mathcal M\in\mathcal E_{\tau\cup C}\mid\{c^\mathcal M\mid c\in C\}\mbox{ is the universe of an elementary substructure of }\mathcal M\}.$$

Letting $X(T)=X\cap M_{\tau\cup C}(T)$, we have that $X(T)$ is dense in $M_{\tau\cup C}(T)$, so each $M_{\tau\cup C}(\Sigma(c_i))\cap X(T)$ is closed nowhere dense in $X(T)$, and therefore a $G_\delta$ in the compact regular space $M_{\tau\cup C}(T)$. Therefore $X(T)\cap\bigcup_{i\in\mathbb N}M_{\tau\cup C}(\Sigma(c_i))$ has empty interior and its complement in $X(T)$ is dense (so, relevant for us, non-empty). If $\mathcal M$ is any structure in this complement, then for each $i$ there is a $\sigma_i(x)\in\Sigma(x)$ such that $\mathcal M\models\lnot\sigma_i(c_i)$. So, using the key property of the space $X$, the elementary substructure of $\mathcal M$ with universe the $c_i^\mathcal M$ is countable, and omits $\Sigma(x)$, completing the proof.

The pretty idea of considering $\mathcal E_\tau$ as a topological space is classical. One can see some of it in the book on Models and ultrapowers by Bell and Slomson. Another early reference is

Andrzej Ehrenfeucht, and Andrzej Mostowski. A compact space of models of first order theories, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., 9, (1961), 369–373. MR0148536 (26 #6043).

Modern attention to this topological approach comes from the work of Xavier Caicedo, who saw its usefulness in the setting of abstract logics. See for example his three papers

Compactness and normality in abstract logics, Ann. Pure Appl. Logic, 59 (1), (1993), 33–43. MR1197204 (93m:03062),

Continuous Operations on Spaces of Structures. In Quantifiers: Logics, Models and Computation, pp. 263-296, Synthese Lib., 248, Kluwer Acad. Publ., Dordrecht, 1995,

and

The abstract compactness theorem revisited. In Logic and foundations of mathematics (Florence, 1995), pp. 131–141, Synthese Lib., 280, Kluwer Acad. Publ., Dordrecht, 1999. MR1739865 (2001b:03039).

The specific presentation I sketched above comes from Julián's undergraduate thesis, written under the supervision of Xavier Caicedo:

Julián Mariño Von Hildebrand. Topología en los espacios de models de la lógica de primer orden, Undergraduate thesis, Dept. of Mathematics, Universidad de los Andes, Bogotá, 1995.

(Julián is a friend from many years ago, and I haven't talked to him in ages. Thanks, I think I'll use this question as an excuse to give him a call.)

$\endgroup$
1
  • $\begingroup$ An unhappiness of the argument is that I do not see a "mostly topological" way or arguing about some of the properties of $X$, and instead must invoke a Henkin-style construction. $\endgroup$ Sep 17, 2013 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.