1
$\begingroup$

We say that a sentence is a $\exists\forall$-sentence iff it is of the form $\exists w_1\cdots\exists w_m\forall v_1\cdots\forall v_n \theta(\bar{w},\bar{v})$ where $\theta$ is quantifier-free. My question is, given any two $\psi,\varphi$ $\exists\forall$-sentences, does there exist another $\exists\forall$-sentence $\gamma$ such that $\psi\land\varphi\equiv\gamma$?

I've only managed to almost prove the case when both $\psi$ and $\varphi$ have the same amount of existential and universal quiantifiers, but I don't see how to proceed in the general case.

The main problem I have is that $(\exists x\alpha)\land(\exists x\beta)\not\equiv\exists x(\alpha\land\beta)$, however it is true that $\exists x(\alpha\land\beta)$ logically implies $(\exists x\alpha)\land(\exists x\beta)$.

Thanks for any help.

$\endgroup$
1
  • 1
    $\begingroup$ Am I missing something simple? If $\exists x . \forall y . \theta_1$ and $\exists u . \forall v . \theta_2$, where $x,y,u,v$ all are disjoint collections of variables, then why doesn't $\exists x, u . \forall y, v . \theta_1 \land \theta_2$ work? $\endgroup$
    – Chris Grossack
    Commented Feb 8, 2021 at 20:12

1 Answer 1

Reset to default
2
$\begingroup$

The formula $$\exists \vec{w} \forall \vec{v} \left[P(\vec{w},\vec{v})\right] \land \exists \vec{x} \forall \vec{y} \left[Q(\vec{x},\vec{y})\right]$$ is equivalent to $$\exists \vec{w},\vec{x} \forall \vec{v},\vec{y} \left[P(\vec{w},\vec{v}) \land Q(\vec{x},\vec{y})\right].$$ This assumes that all the $\vec{w},\vec{v},\vec{x},\vec{y}$ are distinct, but you can always achieve that by renaming.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .