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:


*

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

*$\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.
 A: 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.
