# Elimination of quantifiers in the strucure of polynomials and in the structure of exponentials

I am looking at the elimination of quantifiers.

In my notes there is the following:

$L=\{+, ' , T, 0, 1\}$ ($"="$ is meant to be included in $L$)

First-order Logic: $Q_1 x_1 \dots Q_m x_m \ \ [\phi ]$ where $Q_1, \dots , Q_m$ are the quantifiers ($\exists , \forall$), $\phi$ is a boolean combination of atomic formulae ( $t_1 R t_2$ (where $t_1, t_2$ are terms, $R$ is a predicate), $R(t)$ (where $R$ is a predicate) )

The terms can be built from the elements of the language. Terms are for example: $0$, $x$, $x+y$, $x'$, $(x+y)'+x'+1+1$

A sentence without quantifiers has no variables, for example $1=0$, $1'=0$.

Reduction of sentences to sentences without quantifiers.

Let $\mathcal{A}$ be a structure in that we interpret $L$, for example $\text{Exp}(\mathbb{C})$.

Elimination of quantifiers: For each formula $\psi$ there is a formula $\psi_0$ without quantifiers such that in the strucutre $\mathcal{A}$ the following is a tautology: $$\exists x \ \ \psi (x) \leftrightarrow \psi_0$$ i.e., $$\mathcal{A} \models \exists x \ \ \psi (x) \leftrightarrow \psi_0$$

It suffices to mention only the existential formulas since $$\neg \exists x \ \ \psi (x)\equiv \forall x \ \ \neg \psi (x) \\ \neg \forall x \ \ \psi (x)\equiv \exists x \ \ \neg \psi (x)$$

$$L=\{+, -, ', T, 0, 1\}$$

$$\models \exists x \ \ \left (x=a \land x=b\right ) \leftrightarrow a=b \\ \exists x \ \ \left (x+y=a \land x-y=b\right ) \leftrightarrow 2y=a-b$$

A term $t$ is of the form $$t\equiv t(x)+t_0$$ that means that $t(x)$ is a term that contains $x$, that is constructed by the language $L$, and $t_0$ is constructed by the language $L$ and it doesn't contain $x$.





Let $T(x)$ be the predicate that $x$ is non-constant.



Consider the expression $$\exists x \left (x'+x=1 \land T(x) \right ) \tag 1$$ Since the solution of the differential equation $x'+x=1$ is $x(t)=1-Ce^{-t}$, we can eliminate the quantifier at $(1)$ in the structure $\text{Exp}(\mathbb{C})$, so in this case it is $$\exists x \left (x'+x=1 \land T(x) \right ) \leftrightarrow 0=0$$ but we cannot eliminate the quantifiers in the structure of polynomials, so in this case it is $$\exists x \left (x'+x=1 \land T(x) \right ) \leftrightarrow 1=0$$

Is this correct?



Consider the expression $$\exists x \left (x'+x=t \land T(x) \right ) \tag 2$$ Since the solution of the differential equation $x'+x=t$ is $x(t)=Ce^{-t}+t-1$, we cannot eliminate the quantifier at $(2)$ neither in the structure of polynomials nor in the structure $\text{Exp}(\mathbb{C})$. So in both cases it is $$\exists x \left (x'+x=t \land T(x) \right ) \leftrightarrow 1=0$$

Is this correct?

• Your description of first case in (1) is ok (the part considering $EXP(\mathbb{C})$. You can add that this sentence is true in the $EXP(\mathbb{C}$, so it's equivalent (modulo $A$) to $0=0$. The false sentences (in specific structures) are equivalent (modulo $A$) to $0=1$. – M. Stawiski Oct 13 '15 at 7:20
• I have also an other question:  I have shown that the linear differential equation of first order $ax'(z)+bx(z)=y(z)$ has always a solution in the ring $\mathbb{C}[z, e^{\lambda z} \mid \lambda \in \mathbb{C}]$ besides when $a=b=0 \land y \neq 0$.  So, there is an elimination of quantifiers in this ring, right? We can write the following: $$\exists x \in \mathbb{C}[z, e^{\lambda z} \mid \lambda \in \mathbb{C}] \ \ ax'(z)+bx(z)=y(z) \leftrightarrow ( a \neq 0 \lor b \neq 0 ) \lor (a=b=0 \land y=0)$$ Is this correct? – Mary Star Oct 25 '15 at 9:52
• I assume that you are considering $\phi(a,b,y)$? – M. Stawiski Oct 25 '15 at 9:58