# Löwenheim-Skolem in an extension of first order logic

I'm trying to show that the Löwenheim-Skolem Theorem holds in $\mathscr{L}_{Q_{0}}$, which we have defined as an extension of FoL with the following added properties:

1. If $\varphi$ is a formula, then so is $Q_{0} x\varphi$

2. $\mathcal{A},h \models Q_{0}x\varphi \quad$ iff $\quad\left\lbrace a\in A \mid \mathcal{A},h(x \rightarrow a) \models \varphi \right\rbrace$ is (at least countably) infinite.

My first idea was to show that there is a model $\mathcal{B}$ s.t. $\mathcal{B}\models \forall x\varphi_{0}$ ($\varphi_{0}$ in FoL), and then to use that Löwenheim-Skolem holds in FoL and say that $\mathcal{B}\models Q_{0} \varphi_{0}$. But I don't think the Structure $\mathcal{B}$ is the same if I replace the $\forall$ with $Q_{0}$.

Another idea was to somehow use the relativization property of FoL, but I'm having similar problems there.

I'd appreciate any help! Thank you.

One approach is to modify a typical argument for the (downward) Lowenheim-Skolem theorem. Let me first sketch the typical argument, then indicate how to modify. (There is probably something slicker.)

Assume that $\mathcal M$ is an infinite structure. A typical way to argue is now like this. Let $f$ be a function which takes a formula $\phi$ to a function $f_\phi$ such that

if there is a $b\in M$ such that $\mathcal M\models \phi(b,\overrightarrow a)$, then $\mathcal M \models \phi(f_\phi(\overrightarrow a),\overrightarrow a)$ for all $\overrightarrow a\in M$.

You then define $F(X)=\{f_\phi(\overrightarrow a):\overrightarrow a\in X\textrm{ and }\phi \textrm{ a formula}\}$. Set $N=F(\emptyset)\cup F(F(\emptyset))\cup\cdots$, and take the structure $\mathcal N$ to interpret the elements of the signature of $\mathcal M$ as the restrictions to $N$ of their $\mathcal M$-interpretation.

It remains to verify that $N$ is countable and that $\mathcal N$ is a countable elementary substructure of $\mathcal M$.

To adapt the argument to your situation, you can replace the function $f$ with a function $g$ such that for each formula $\phi$, the value $g_\phi$ is a function which takes $\overrightarrow a$ to a countable subset $g_\phi(\overrightarrow a)$ of $M$ such that for all $k$,

if there are at least $k$ elements $b$ of $M$ such that $\mathcal M\models \phi(b,\overrightarrow a)$, then $g_\phi(\overrightarrow a)$ contains at least $k$ elements and $\mathcal M \models \phi(c,\overrightarrow a)$ for all $\overrightarrow a\in M$ and all $c\in g_\phi(\overrightarrow a)$.

The rest of the proof goes through pretty much as before. The domain $N$ is countable because it's a countable union of countable sets. To verify that $\mathcal N$ is indeed an elementary substructure, put the formula into prenex form (with a dual quantifier $Q_1=$"there are at most finitely many counterexamples to"). In the step dealing with $Q_1$, use the induction hypothesis to infer that you couldn't have added infinitely many counterexamples.