Let $K$ be an elementary class of $\Sigma$-structures. Show that the class $K^{\infty}$ formed by the structures of $K$ with infinite domain is also elementary.

I'm really clueless about this problem. I know that $K$ is elementary if there is som $\Phi \subseteq \mathrm{Sent}_{\Sigma}$ such that $K=\mathcal{Mod}(\Phi)$, that is $$K= \{ \mathcal{A} \mid \mathcal{A} \models \varphi \,\, \forall \varphi \in \Phi\}$$ so $$K^{\infty}=\{ \mathcal{A} \in K \mid |\mathcal{A}|=\infty\}$$ Obviously $K^{\infty}\subseteq K$, but I don't know what strategy to follow. Any hint would be highly appreciated. Thank you.


Suppose $\Phi$ is a set of sentences defining $K$ - that is, $K=\{\mathcal{A}: \mathcal{A}\models\Phi\}$. Now $K^\infty\subseteq K$ as you observe, so you want to find a bigger set of sentenecs $\Psi\supseteq \Phi$ such that $K^\infty=\{\mathcal{A}: \mathcal{A}\models\Psi\}$.

(Why bigger? Well, satisfying more sentences is a stronger constraint, and there are fewer things satisfying it.)

That means we want to add some sentences to $\Phi$. Now the obvious sentence to add is "the domain is infinite"; the structures satisfying $\Phi$ together with "the domain is infinite" are exactly the infinite models of $\Phi$, that is, the elements of $K^\infty$!

So we're done, right? Just set $\Psi=\Phi\cup\{$"the domain is infinite"$\}$.

But this doesn't work,since "the domain is infinite" isn't a first-order sentence. So instead, we need to somehow express "the domain is infinite" in a first-order way. On the plus side, we don't have to do this with a single sentence, we're allowed to add a bunch of sentences. Which leaves us with:

Can you think of a family of sentences $\Theta=\{\theta_i: i\in\mathbb{N}\}$ such that the models of $\Theta$ are exactly the infinite structures?

HINT: It's enough for the models of $\theta_i$ to be the structures with size at least $i$, for every $i\in\mathbb{N}$ ...

  • $\begingroup$ Hum... Could it be $\theta_i = \exists x_1 \dots \exists x_i \left( \neg (x_1=x_2)\wedge \neg(x_1=x_3)\wedge \dots \wedge \neg(x_{i-1}=x_i)\right)$? $\endgroup$ – user313212 Jun 4 '17 at 17:28
  • $\begingroup$ So $\theta_1$ would be just "there is an element", $\theta_2 = \exists x\exists y \left( \neg (x=y)\right)$, $\theta_3 = \exists x \exists y \exists z\left( \neg(x=y)\wedge \neg (x=z)\wedge \neg (y=z)\right)$... $\endgroup$ – user313212 Jun 4 '17 at 17:31
  • $\begingroup$ @user313212 Exactly! Do you see why this finishes the problem? $\endgroup$ – Noah Schweber Jun 4 '17 at 17:34
  • $\begingroup$ I think so, I followed you hint, so the rest follows the argument in your answer, right? The models of $\theta_1$ are exactly the structures with size at least 1 and so on. What I'm not really sure is why the models of $\Theta$ are the infinite structures. How do you show that from "I have a set of $\theta_i$ such thay the models of each $\theta_i$ are the structures with size at least $i$"? $\endgroup$ – user313212 Jun 4 '17 at 17:52
  • 1
    $\begingroup$ @dav11 That's not a problem - if $K$ is empty, then $K^\infty$ is empty too, and hence elementary. Although $K$ will have no infinite models, we can define $\Psi=\Phi\cup\Theta$ as I have done, and check that $\Psi$ defines $K^\infty=\emptyset$. So while the empty class is often a counterexample, in this case it's not. $\endgroup$ – Noah Schweber Jun 5 '17 at 22:20

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.