# Set of finite models, show that some formula has also finite models

Let $Spec(\phi)$ denotes set of cardinalities finite models of $\phi$. Show that if $\Delta$ is set of sentences such that:

• $\forall_{\phi\in\Delta} Spec(\neg\phi)\text{ is finite} \wedge$
• $\Delta\models\psi$
$\Rightarrow$
• $Spec(\neg \psi) \text{is finite}.$

My approach is following:

It is known (I don't prove it here) that there exists finite subset $\Delta_0\subseteq\Delta$ such that $\Delta_0\models\psi$. In other words we know that there exists $\Delta_0=\{\psi_1,...,\psi_k\}$ such that $(\psi_1\wedge \psi_2 \wedge ...\wedge \psi_k)\rightarrow \psi$.
It is equivalent to $\neg \psi\to (\neg \psi_1\vee \neg\psi_2 \vee ...\vee \neg\psi_k)$. Now we, now that each model of $\neg\psi$ must be model of $(\neg \psi_1\vee \neg\psi_2 \vee ...\vee \neg\psi_k)$ . We know that,
each model of $(\neg \psi_1\vee \neg\psi_2 \vee ...\vee \neg\psi_k)$ is finite because $Spec(\neg \psi_1\vee \neg\psi_2 \vee ...\vee \neg\psi_k) = Spec (\neg \psi_1)\cup...\cup Spec(\neg\psi_k)$ is finite.

Am I ok ?

• usually, an "if" is followed by a "then" – mercio Feb 20 '17 at 15:43
• @mercio There's an "$\implies$" between the second and third bullet points - not entirely easy to see, but it's there. – Noah Schweber Feb 20 '17 at 15:44

Yup, looks good! Compactness implies that such a $\Delta_0$ exists, and then the result follows since the union of finitely many finite sets is finite - just like you've said.
• being honestly: I can't see where assumption about finitness of $Spec$ may be exploited. (I mean that task states that $Spec$ is set of finite models, I didn't use this assumption, I treat it as common spec set). Moreover, it seems to me that $Spec$ always contains cardinalities only finite models,.... – user343207 Feb 20 '17 at 15:54
• @HaskellFun Yes, $Spec$ - and this argument - generalize. Given any set (respectively, class) $S$ of cardinalities, we can define $Spec_S(\phi)$ to be the set (respectively, class) of cardinals in $S$ of models of $\phi$. What you've argued also proves: if $Spec_S(\neg\phi)$ is finite for each $\phi\in\Delta$, then $Spec_S(\neg\psi)$ is finite whenever $\Delta\models\psi$. In practice, though, we're only every interested in $Spec_{finite}$ (continued): – Noah Schweber Feb 20 '17 at 15:59
• $Spec_{finite}$ - that is, the usual $Spec$ - is very important in finite model theory and in complexity theory; see this beautiful survey paper on one of the major open problems about $Spec_{finite}$. Meanwhile, why aren't we interested in $Spec_S$ for more general $S$? Well, if $S$ is a set of finite cardinalities, then $Spec_S$ is basically just $Spec_{finite}$ but maybe with less information; and by the Lowenheim-Skolem theorem, if a sentence has any infinite model it has models of every infinite cardinality, (cont'd) – Noah Schweber Feb 20 '17 at 16:03
• so $Spec_{infinite}(\phi)$ is always either $\emptyset$ or $\{$all infinite cardinals$\}$. (That said, things get more interesting if, instead of looking at first-order sentences, we look at sentences in non-first-order logics like infinitary or second-order logic; a relevant concept here is the Hanf number which unfortunately has no wiki page.) So while $Spec$ can be generalized, none of those generalizations are particularly interesting - at least, within the first-order context. – Noah Schweber Feb 20 '17 at 16:06