[Math] Equivalence of first-order formulas

first-order-logiclogicpredicate-logic

The following are elementary truths for arbitrary formulas $\phi, \psi$ of first-order logic in which all variables but $x$ are bound:

  1. $\vdash \forall x \phi(x) \wedge \forall x \psi(x) \leftrightarrow \forall x \big(\phi(x) \wedge \psi(x)\big)$

  2. $\vdash \exists x \phi(x) \vee \exists x \psi(x) \leftrightarrow \exists x \big(\phi(x) \vee \psi(x)\big)$

  3. $\forall x \phi(x) \vee \forall x \psi(x) \vdash \forall x \big(\phi(x) \vee \psi(x)\big)$

  4. $\exists x \big(\phi(x) \wedge \psi(x)\big) \vdash \exists x \phi(x) \wedge \exists x \psi(x)$

In case 1. and 2. there is – for arbitrary formulas $\phi, \psi$ as above – a formula $\theta(x) = \theta(\phi(x),\psi(x))$ with one free variable $x$ such that

  1. $\vdash \forall x \phi(x) \wedge \forall x \psi(x) \leftrightarrow \forall x \theta(x)$ with $\theta(x) = \phi(x) \wedge \psi(x)$

  2. $\vdash \exists x \phi(x) \vee \exists x \psi(x) \leftrightarrow \exists x \theta(x)$ with $\theta(x) = \phi(x) \vee \psi(x)$

How do I show that there is – for arbitrary formulas $\phi, \psi$ as above – no formula $\theta(x) = \theta(\phi(x),\psi(x))$ with just
one free variable $x$ such that

$\vdash \forall x \phi(x) \vee \forall x \psi(x) \leftrightarrow \exists x \theta(x)$

$\vdash \exists x \phi(x) \wedge \exists x \psi(x) \leftrightarrow \exists x \theta(x)$

(Note, that they surely are equivalent with formulas with two variables, e.g. with $\forall x \forall y \big(\phi(x) \vee \psi(x/y)\big)$.)

Best Answer

What you strictly want to prove seems to be incorrect. You want to show there is no prenex normal form formula equivalent to $\forall x \phi(x) \vee \forall x \psi(x)$. But consider if $\phi(x)$ and $\psi$ are both "$x = x$" or, if you don't have identity, "$P(x) \vee \neg P(x)$". They don't even have to be the same; you could have $\psi$ be "$Q(x) \vee \neg Q(x)$" if you like. Then $\forall x (\phi \vee \psi)$ and $\forall x\phi \vee \forall x\psi$ are both valid, and hence provably equivalent.

Maybe what you wanted is a case of $\phi(x)$ and $\psi(x)$ which is a counterexample to the claim they're always provably equivalent. In which case, you could easily just take $\phi(x)$ to be $P(x)$, and $\psi(x)$ to be $Q(x)$. Just because everything is either $P$ or $Q$ doesn't mean either everything is $P$ or everything is $Q$. (Similar remarks for the existential case). Or maybe what you wanted is just the case where $\phi$ and $\psi$ are not valid formulae? In that case, you just need to note that if there were a prenex normal form formula equivalent to $\forall x \phi(x) \vee \forall x \psi(x)$ with one variable, it'd have an innermost quantifier that ranged over both the variable in $\phi$ and the variable in $\psi$. You just need to argue in that case that neither choice of innermost quantifiers works.

As for your second question, again, if you choose $\phi$ in the first case to be a valid formula, then $\forall x \phi(x) \wedge \exists x \psi(x)$ is just $\exists x (\phi(x) \wedge \psi(x))$, or even just $\exists x \psi(x)$. Similar remarks for the other formula.

Related Question