1
$\begingroup$

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 ?

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

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.

$\endgroup$
  • $\begingroup$ Thanks! I invite to other my logic threads ! $\endgroup$ – user343207 Feb 20 '17 at 15:51
  • $\begingroup$ 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,.... $\endgroup$ – user343207 Feb 20 '17 at 15:54
  • 1
    $\begingroup$ @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): $\endgroup$ – Noah Schweber Feb 20 '17 at 15:59
  • 1
    $\begingroup$ $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) $\endgroup$ – Noah Schweber Feb 20 '17 at 16:03
  • 1
    $\begingroup$ 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. $\endgroup$ – Noah Schweber Feb 20 '17 at 16:06

Your Answer

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