Logic about definable subset [closed]

If we have a definable subset A without parameter by a universal formula, say $\forall y, f(x,y)$. And we also have a definable subset B with parameter by existential formula, say $\exists y, f'(x,y,c)$ If A=B, can we show that this is also definable by a existential formula without parameter?

Solution 1:

Not necessarily. For example, consider the structure $(\mathbb{N},\leq)$.

The set $Z= \{ 0\}$ is definable by the universal formula $\forall y\, (x\leq y)$. $Z$ is also definable by the existential formula $\exists y\,(x=0)$ which uses the parameter $0$.

But $Z$ is not definable by any existential formula with no parameters. To see this, recall that if $\varphi(x)$ is an existential formula with no parameters and $h\colon A\to B$ is an embedding, then $A\models \varphi(a)$ implies $B\models \varphi(h(a))$.

Now suppose there is an existential formula $\varphi(x)$ with no parameters such that $\mathbb{N}\models \varphi(0)$. The map $h(n)= n+1$ is an embedding $\mathbb{N}\to\mathbb{N}$, from which it follows that $\mathbb{N}\models \varphi(1)$ (and repeating, $\mathbb{N}\models \varphi(n)$ for all $n$). So $\varphi(x)$ fails to define $Z$.

In the comments, you asked: "How about if we say for all universal formula, they are equivalent to some existential formulas with parameter, then can we eliminate the parameter?"

The answer is again no. Consider the structure $(\mathbb{Q}_{\geq 0},\leq)$, where $\mathbb{Q}_{\geq 0} = \{q\in \mathbb{Q}\mid q\geq 0\}$. The complete theory of this structure is the theory $T$ of dense linear orders with a least element but no greatest element.

It is well-known that if we add a constant symbol naming the least element $0$, the complete theory $T' = \mathrm{Th}(\mathbb{Q}_{\geq 0},\leq,0)$ has quantifier elimination. It follows that in $(\mathbb{Q}_{\geq 0},\leq)$, every formula is equivalent to a quantifier-free formula with a single parameter $0$. In particular, every universal formula is equivalent to an existential formula with parameters.

But again, the universal formula $\forall y\, (x\leq y)$, which defines $\{0\}$, is not equivalent to any existential formula without parameters. If there is an existential formula $\varphi(x)$ with no parameters such that $\mathbb{Q}_{\geq 0}\models \varphi(0)$, then since the map $h(q)= q+1$ is an embedding $\mathbb{Q}_{\geq 0}\to\mathbb{Q}_{\geq 0}$, it follows that $\mathbb{Q}_{\geq 0}\models \varphi(1)$, so $\varphi(x)$ fails to define $\{0\}$.