2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.