3
$\begingroup$

Let $L$ be a first order relational language with identity. Let $E$ be an $L$-structure. Let $L_{\alpha\beta}$ be the usual infinitary extension of $L$. Thus, $E$ is an $L_{\alpha\beta}$-structure also. Let $\phi$ be a formula such that the arity of $\phi$ is $\gamma < \alpha$. $\gamma$ is the ordinal corresponding to the set of free variables of $\phi$. Let $[\phi]_{E}$ be the solution set of $\phi$ in the structure $E$, that is, the set of all $\gamma$-tuples in the domain of $E$ that satisfy $\phi$. We say that $E$ has quantifier elimination if for all formula $\phi$ there is a quantifier-free formula $\psi$ with the same free variables such that $[\phi]_{E} = [\psi]_{E}$. QUESTION: Is it true that if $E$ has quantifier elimination in $L$, then $E$ has quantifier elimination in $L_{\alpha\beta}?$

$\endgroup$
3
$\begingroup$

Note: I assume that when you say $E$ has quantifier elimination in $L$, you mean it has quantifier elimination in the first order logic (i.e. $L_{\omega, \omega}$).

The answer is no. Take $\mathbb R$ in the language $<$. In first order logic it eliminates quantifiers as it is a dense linear order. $L_{\omega_1, \omega}$ definable subsets of $\mathbb R$ are all projective subsets. However those definable with quantifier free $L_{\omega_1, \omega}$-formulas are only Borel subsets.

$\endgroup$
  • $\begingroup$ Thank you, for the example. $\endgroup$ – E. G. de Souza Dec 11 '15 at 22:02
3
$\begingroup$

Certainly not. Here's a simple example:

Let $T = \text{Th}(\mathbb{Z},<,S)$, where $<$ is the usual ordering on $\mathbb{Z}$ and $S$ is the successor function. $T$ has quantifier-elimination (in first-order). Let $M$ be the model of $T$ consisting of two copies of $\mathbb{Z}$ laid end to end. Then $M$ has quantifier-elimination in $L$.

In $L_{\omega_1,\omega}$, we can write down the formula $\varphi(x)\colon \lnot \exists y\, (y<x) \land (\bigwedge_{n\in\omega} S^n(y) \neq x)$. $\varphi$ picks out the first copy of $\mathbb{Z}$ in $M$. But $\varphi$ is not equivalent to any quantifier-free formula. Indeed, it's easy to check by inspection that every atomic formula in just one free variable is satisfied by all elements of $M$ or none of them, so no (infinitary) Boolean combination of atomic formulas picks out the first copy of $\mathbb{Z}$.

$\endgroup$
  • $\begingroup$ Thanks for this contable example. $\endgroup$ – E. G. de Souza Dec 11 '15 at 22:03

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.