Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
In the first paragraph, you mean A is an elementary substructure of B iff... – Alex Kruckman Jan 28 '13 at 21:53
up vote 5 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.