# Theory of a class of finite L-Structures

Exercise 2.1.2.3. in "A Course in Model Theory" by Ziegler, Tent states:

Assume that $\mathcal{C}$ is a class of finite $L$-structures containing only finitely many structures of size $n$ for each $n\in \omega$. Then the infinite models of Th$(\mathcal{C})=\{\varphi\;|\;\mathfrak{A}\vDash\varphi\text{ for all }\mathfrak{A}\in\mathcal{C}\}$ are exactly the models of \begin{align} \text{Th}_{\text{a}}(\mathcal{C})= \{\varphi\;|\;\mathfrak{A}\vDash\varphi\text{ for all but finitely many }\mathfrak{A}\in\mathcal{C}\} \end{align}

I did not manage to find a proof of this statement.

(I assume that $\mathcal{C}$ is infinite, since otherwise only finitely many structures in $\mathcal{C}$ would not satisfy $\theta=\neg\exists x_1\cdots \exists x_n\; \bigwedge_{i<j} \neg x_i\dot{=} x_j$, i.e. $\theta\in$ Th$_{\text{a}}(\mathcal{C})$ while for any infinite $\mathfrak{A}\vDash\text{Th}(\mathcal{C})$ we have $\mathfrak{A}\not\vDash\theta$.)

When I try to start with an infinite model of $\text{Th}(\mathcal{C})$ I see no reason why it should satisfy any $\varphi\in\text{Th}_{\text{a}}(\mathcal{C})\setminus\text{Th}(\mathcal{C})$ since not every infinite model of Th$(\mathcal{C})$ has to be constructed in way so that elements satisfying $\varphi$ are included.

Counter example to make it more clear: $\mathcal{C}:=\{\mathfrak{A}_n:=(\{1,...,n\}, L)\;|\; n=2,3,4...\}$ with $L=\{R\}$ and $R$ being an $4$-ary relation symbol interpreted as $R(a_1,a_2,a_3,a_4)$ if and only if the informal condition $a_1<a_2<a_3<a_4$ and $a_1,...,a_4<6$ is true. Then \begin{align} \mathfrak{A}_n\vDash \varphi:=\exists x_1\exists x_2\exists x_3\exists x_4 R(x_1,x_2,x_3,x_4)\;\text{ with }\; n>3 \end{align} and, therefore, $\varphi\in\text{Th}_{\text{a}}(\mathcal{C})$. Then $\mathfrak{B}=(\{1,3,5,7,...\},L)$ is an infinite model of Th$(\mathcal{C})=\{\exists x_1\exists x_2\;\neg x_1\dot{=} x_2\}$, but $\mathfrak{B}\not\vDash\varphi$.

Where is my misconception?

• $\text{Th}(\mathcal{C})$ is the theory of $\mathcal{C}$, i.e. the set of all $L$-sentences($L$-formulas without free variables.) satisfied by any structure in $\mathcal{C}$. $\text{Th}_\text{a}(\mathcal{C})$ is the set of $L$-sentences satisfied by all except finitely many structures in $\mathcal{C}$. – Zikrunumea Feb 15 '18 at 4:23
• It looks to me like $\mathfrak{B}$ is not in fact a model of $Th(\mathcal{C})$: every structure in $\mathcal{C}$ satisfies "If there are at least four elements in the domain, then there is an instance of $R$" (which is first-order expressible) but $\mathfrak{B}$ doesn't. – Noah Schweber Feb 15 '18 at 4:29

First of all, note that in your example $Th(\mathcal{C})$ is more complicated than you claim (you write that it is just $\{\exists x_1, x_2(x_1\not=x_2)\}$): for example, the sentence $$\varphi=\mbox{"If there are at least four elements, then there is an instance of R"}$$ is true in every structure in $\mathcal{C}$. And this is first-order expressible; more generally, the sentence $\psi_n$="there are at least $n$ elements" is first-order expressible for each natural number $n$. Now as you observe we have $\mathfrak{B}\not\models\varphi$, so in fact $\mathfrak{B}$ is not a model of $Th(\mathcal{C})$.

This observation is also the key to proving the statement in question. For $\varphi\in Th_a(\mathcal{C})$, write "$height(\varphi)$" for the least $k$ such that every element of $\mathcal{C}$ with at least $k$-many elements satisfies $\varphi$. Note that if $\varphi\in Th_a(\mathcal{C})$ then $height(\varphi)$ exists. The key point is now:

For a sentence $\varphi$, we have $\varphi\in Th_a(\mathcal{C})$ iff $(\psi_{height(\varphi)}\implies\varphi)\in Th(\mathcal{C})$.

(The left-to-right direction is trivial; for the right-to-left direction, what assumption about $\mathcal{C}$ do we need to use?)

From this, do you see how to conclude that $M\models Th(\mathcal{C})\implies M\models Th_a(\mathcal{C})$ for $M$ infinite?

• If $(\psi_{\text{height}(\varphi)}\to \varphi)\in$ Th$(\mathcal{C})$ is satisfied by all structures in $\mathcal{C}$, it means that any structure satisfies either $\neg\psi_{\text{height}(\varphi)}$ or $\varphi$. By defnition of $\mathcal{C}$ only finitely many structures can satisfy $\neg\psi_{\text{height}(\varphi)}$. Therefore, all other satisfy $\varphi$ and therefore $\varphi\in\text{Th}_\text{a}(\mathcal{C})$. – Zikrunumea Feb 15 '18 at 4:52
• @Zikrunumea Yup. So do you see how this finishes the argument? – Noah Schweber Feb 15 '18 at 4:58
• A modus ponens-esque argument like: Let $M\vDash \text{Th}(\mathcal{C})$ be infinite. For any $\varphi\in\text{Th}_\text{a}(\mathcal{C})$ we have $(\psi_{\text{height}(\varphi)}\to\varphi)\in\text{Th}(\mathcal{C})$. Since $M$ is infinite we have $M\vDash\psi_{\text{height}(\varphi)}$ and also by definition $M\vDash (\psi_{\text{height}(\varphi)}\to\varphi)\in\text{Th}(\mathcal{C})$. I.e. $M\vDash (\psi_{\text{height}(\varphi)}\to\varphi)\wedge \psi_{\text{height}(\varphi)}$ and, therefore, $M\vDash \varphi$. – Zikrunumea Feb 15 '18 at 5:09
• @Zikrunumea Yup! – Noah Schweber Feb 15 '18 at 5:11
• Thanks, this was very instructive! – Zikrunumea Feb 15 '18 at 5:12