0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ $\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}$. $\endgroup$ – Zikrunumea Feb 15 '18 at 4:23
  • $\begingroup$ 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. $\endgroup$ – Noah Schweber Feb 15 '18 at 4:29
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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})$. $\endgroup$ – Zikrunumea Feb 15 '18 at 4:52
  • $\begingroup$ @Zikrunumea Yup. So do you see how this finishes the argument? $\endgroup$ – Noah Schweber Feb 15 '18 at 4:58
  • $\begingroup$ 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$. $\endgroup$ – Zikrunumea Feb 15 '18 at 5:09
  • $\begingroup$ @Zikrunumea Yup! $\endgroup$ – Noah Schweber Feb 15 '18 at 5:11
  • $\begingroup$ Thanks, this was very instructive! $\endgroup$ – Zikrunumea Feb 15 '18 at 5:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.