# Provability of deduction in presence of existential quantifier

I'm gonna prove that:

$(i)~~\Sigma \vdash \theta$ does imply $\Sigma \vdash \exists x\theta$

$(ii)~~\Sigma \vdash \exists x\theta$ does NOT imply $\Sigma \vdash \theta$

$(i):$ According to rule of inference type (Q2), we have:

$\theta_{t}^{x} \rightarrow \exists x \theta$ if $x$ is substitutable in $\theta$ with term $t$.

So, the steps of the deduction will be as following:

$\theta$

$\theta_{x}^{x}$

$\exists x \theta$

Thus $\Sigma \vdash \exists x\theta$

$(ii)$ : According to one of rules of inference type (QR), we have:

If $x$ is bound in $\psi$, then $\{(\theta \rightarrow \psi),(\exists x \theta \rightarrow \psi)\}$.

Now, according to the assumption, $\exists x \theta$ is true. Then, $\psi$ must be true, too. (Unless, $(\exists x \theta \rightarrow \psi)$ will be false.)

Furthermore, we know that $(\theta \rightarrow \psi)$ is true. (rule of inference's assumption). But both truth of $\psi$ lead to both truth of $\theta$ and $\neg \theta$. So we can't conclude that $\theta$ is (always) true.

Finally, $\Sigma \vdash \exists x\theta$ doesn't imply $\Sigma \vdash \theta$.

Do you find any kind of flaws within arguments above?

• Basically, the proof of (ii) must relies on Th.2.5.3. Soundness and the reasoning following Lemma 2.7.2, that can be used to show that the purported rule (ii) is not sound. – Mauro ALLEGRANZA Jan 29 '17 at 11:27

## 1 Answer

Your first argument is fine. For $(ii)$, you can come up with simple counterexamples, such as this one:

Let $P$ be a $1$-ary relation. Then if the given statement is true,$$\exists xP(x) \vdash \exists xP(x)$$ implies $$\exists xP(x) \vdash P(x)$$ and since $x$ is bound (not free, to be more accurate) in $\exists xP(x)$, we can further conclude that $$\exists xP(x) \vdash \forall x P(x),$$ which is absurd (I think you're doing something similar in your solution. If that's the case then your argument is correct).