# Class $K^{\infty}$ is elementary provided that $K$ is.

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}$ ...

• 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)$? – user313212 Jun 4 '17 at 17:28
• 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)$... – user313212 Jun 4 '17 at 17:31
• @user313212 Exactly! Do you see why this finishes the problem? – Noah Schweber Jun 4 '17 at 17:34
• 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$"? – user313212 Jun 4 '17 at 17:52
• @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. – Noah Schweber Jun 5 '17 at 22:20