Thread: Determine whether alpha |- gamma

1. Determine whether alpha |- gamma

Hi,

Please could someone help me with the following question?

Let $\displaystyle \alpha : \exists x( \neg A(x) \vee B(x))$
Let $\displaystyle \gamma : \neg \exists x A(x) \vee \exists xB(x)$
Determine whether $\displaystyle \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 $\displaystyle \alpha : \exists x( \neg A(x) \vee B(x))$
Let $\displaystyle \gamma : \neg \exists x A(x) \vee \exists xB(x)$
Determine whether $\displaystyle \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 $\displaystyle \alpha$ does not prove $\displaystyle \gamma$?

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

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

Is this ok?

3. Re: Determine whether alpha |- gamma

Yes. The formula $\displaystyle \exists x( \neg A(x) \vee B(x))$ is equivalent to $\displaystyle (\exists x\,\neg A(x)) \vee (\exists x\,B(x))$, while $\displaystyle (\neg \exists x\,A(x)) \vee (\exists x\,B(x))$ is equivalent to $\displaystyle (\forall x\,\neg A(x))\lor(\exists x\,B(x))$. So $\displaystyle \alpha$ does not derive $\displaystyle \gamma$ because $\displaystyle \exists x\,\neg A(x)$ does not derive $\displaystyle \forall x\,\neg A(x)$. A countermodel should have $\displaystyle \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 $\displaystyle \exists x( \neg A(x) \vee B(x))$ is equivalent to $\displaystyle (\exists x\,\neg A(x)) \vee (\exists x\,B(x))$, while $\displaystyle (\neg \exists x\,A(x)) \vee (\exists x\,B(x))$ is equivalent to $\displaystyle (\forall x\,\neg A(x))\lor(\exists x\,B(x))$. So $\displaystyle \alpha$ does not derive $\displaystyle \gamma$ because $\displaystyle \exists x\,\neg A(x)$ does not derive $\displaystyle \forall x\,\neg A(x)$. A countermodel should have $\displaystyle \neg A(x)$ true for some x but not for all x, which is what you have done.
Thanks :-)