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

  • $\begingroup$ In the first paragraph, you mean A is an elementary substructure of B iff... $\endgroup$ – 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)$.


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.