3
$\begingroup$

Let $\mathcal{L}$ be a first-order language and let $\mathcal{C}$ be a class of $\mathcal{L}$-structures which is not necessarily an elementary class (i.e. there does not exist a theory $T$ such that $\mathcal{C}=mod(T)$).

Let $\Sigma$ be a set of $\mathcal{L}$-sentences such that for every finite subset $\Sigma_0$ of $\Sigma$ there is a member $\mathcal{M}_{}\in\mathcal{C}$ so that $\mathcal{M}\models \Sigma_0$. Then, can we conclude that there is a member $\mathcal{N}\in\mathcal{C}$ such that $\mathcal{N}\models \Sigma$?

$\endgroup$
5
$\begingroup$

No, we cannot. For example, take $\mathcal{C}$ to be the class of all finite structures in our language, let $\varphi_n$ be the sentence asserting that there exist at least $n$ elements in the universe - that is, $\varphi_n$ is the sentence $$\exists x_1,..., x_n(\bigwedge_{1\le i<j\le n}\neg x_i=x_j),$$ which is clearly first-order - and let $\Sigma=\{\varphi_n:n\in\mathbb{N}\}$. Every finite subset of $\Sigma$ is satisfied in all sufficiently large finite structures, but $\Sigma$ itself is only satisfied in infinite structures.


Note that we can do a similar trick with larger cardinalities, assuming a large enough language. For any infinite cardinal $\kappa$, let $C_\kappa$ be the language consisting of $\kappa$-many distinct constant symbols $c_\eta$ ($\eta<\kappa$), take $\Sigma=\{\neg c_\eta=c_\theta: \eta<\theta<\kappa\}$, and take $\mathcal{C}$ to be the class of all structures of cardinality $<\kappa$. Then every subset of $\Sigma$ with cardinality $<\kappa$ (not just every finite subset) is satisfied in some element of $\mathcal{C}$, but no element of $\mathcal{C}$ satisfies all of $\Sigma$.

$\endgroup$
  • $\begingroup$ If $\mathcal{C}$ has sufficiently large members. Then can we still filnd an example? $\endgroup$ – Alice.H Aug 23 '19 at 22:34
  • $\begingroup$ @Alice.H You can replicate the same idea "in a formula" - e.g. take our language to have a single unary predicate symbol $U$, and let $\mathcal{C}$ be the class of all structures $M$ with $U^M$ finite. $\endgroup$ – Noah Schweber Aug 23 '19 at 22:43
  • $\begingroup$ That said - at the same time it's worth noting that there are logics stronger than first order which are compact. Any class of structures which is elementary with respect to such a logic will, well, be compact for first-order theories and indeed theories in that larger logic. So one thing you might be interested in is what sort of compact logics there are. The relevant topic here is abstract model theory. It's worth noting that there are no logics stronger than first-order which are compact and have the downwards Lowenheim-Skolem property. $\endgroup$ – Noah Schweber Aug 23 '19 at 22:49
  • $\begingroup$ This latter result is Lindstrom's theorem, which was the result which kicked of AMT in the first place. $\endgroup$ – Noah Schweber Aug 23 '19 at 22:50

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.