# Tarski-Vaught test for $\preceq$ reduction

The Tarski-Vaught test for $\preceq$ states that given a structure $\mathfrak{B}$ and $A\subseteq B$ then $A$ is the underlying set of an elementary substructure of $\mathfrak{B}$ iff for all formulas $\psi(x_1,\cdots ,x_m,y)$ in $L$ and every sequence $a_1,\cdots , a_m$ of elements in $A$ when $\mathfrak{B}\models \exists y \psi[a_1,\cdots ,a_m]$, then there is $a\in A$ such that $\mathfrak{B}\models \psi[a_1,\cdots ,a_m,a]$.

One direction is clear from the definition of elementary substructure and the other one can be proven using induction on formulas.

I asked around and was told that the second condition can't be reduced to just checking formulas $\exists y\psi$ for $\psi$ quantifier free, but I haven't seen a counterexample.

Intuitively an induction on the number of quantifiers seems to give a proof, but apparently its wrong(?) So what would be a counterexample for it not being necessary to just check quantifier free $\psi$?

• In the first paragraph, you mean A is an elementary substructure of B iff... – Alex Kruckman Jan 28 '13 at 21:53

Let $B=\mathbb{N}\cup\{a\}$ be your universe and let $\mathfrak{B}=(B,<)$ where $<$ is the order of the natural numbers and let $a$ be greater than all natural numbers. Now take $\mathfrak{A}=(\mathbb{N},<)$.
Any quantifier free formula $\psi$ with constants from $\mathbb{N}$ and one free variable $x$ states just the order relation of $x$ with the finite constants. If $\exists x\psi$ is witnessed by $a$ in $\mathfrak{B}$ then it is also witnessed by a natural number greater than all the constants in $\psi$.
On the other hand $\mathfrak{B}\models\exists x\forall y (x\geq y)$ while $\mathfrak{A}\nvDash\exists x\forall y (x\geq y)$.