# Quantifier elimination in infinitary languages

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

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.

• Thank you, for the example. Dec 11, 2015 at 22:02

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

• Thanks for this contable example. Dec 11, 2015 at 22:03