# Thread: Determine whether alpha |- gamma

1. ## Determine whether alpha |- gamma

Hi,

Please could someone help me with the following question?

Let $\alpha : \exists x( \neg A(x) \vee B(x))$
Let $\gamma : \neg \exists x A(x) \vee \exists xB(x)$
Determine whether $\alpha \vdash \gamma$.

I've tried both writing a formal proof to see if it is provable and creating a model to see if it's not provable, but I don't seem to be able to reach a conclusion.

Thanks

2. ## Re: Determine whether alpha |- gamma

Originally Posted by dwally89
Hi,

Please could someone help me with the following question?

Let $\alpha : \exists x( \neg A(x) \vee B(x))$
Let $\gamma : \neg \exists x A(x) \vee \exists xB(x)$
Determine whether $\alpha \vdash \gamma$.

I've tried both writing a formal proof to see if it is provable and creating a model to see if it's not provable, but I don't seem to be able to reach a conclusion.

Thanks
Would the following model show that $\alpha$ does not prove $\gamma$?

Let $M=\{ 1,2\}$
Let $M \supset A = \{ 1 \}$
Let $M \supset B = \{ \}$

$\alpha$ can be satisfied by letting $x=2$, as the first first clause $\neg A(x)$ will be true.
$\gamma$ on the other hand can never be satisfied.
The first clause $\neg \exists xA(x)$ can be made false by setting $x=1$, and the second clause $B(x)$ is always false.

Is this ok?

3. ## Re: Determine whether alpha |- gamma

Yes. The formula $\exists x( \neg A(x) \vee B(x))$ is equivalent to $(\exists x\,\neg A(x)) \vee (\exists x\,B(x))$, while $(\neg \exists x\,A(x)) \vee (\exists x\,B(x))$ is equivalent to $(\forall x\,\neg A(x))\lor(\exists x\,B(x))$. So $\alpha$ does not derive $\gamma$ because $\exists x\,\neg A(x)$ does not derive $\forall x\,\neg A(x)$. A countermodel should have $\neg A(x)$ true for some x but not for all x, which is what you have done.

4. ## Re: Determine whether alpha |- gamma

Originally Posted by emakarov
Yes. The formula $\exists x( \neg A(x) \vee B(x))$ is equivalent to $(\exists x\,\neg A(x)) \vee (\exists x\,B(x))$, while $(\neg \exists x\,A(x)) \vee (\exists x\,B(x))$ is equivalent to $(\forall x\,\neg A(x))\lor(\exists x\,B(x))$. So $\alpha$ does not derive $\gamma$ because $\exists x\,\neg A(x)$ does not derive $\forall x\,\neg A(x)$. A countermodel should have $\neg A(x)$ true for some x but not for all x, which is what you have done.
Thanks :-)