Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.