2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mauro ALLEGRANZA Jan 29 '17 at 11:27
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.