Determine whether alpha |- gamma

**dwally89** · April 29th 2012, 01:51 AM

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

**dwally89** · April 29th 2012, 02:55 AM

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?

**emakarov** · April 29th 2012, 08:53 AM

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.

**dwally89** · April 29th 2012, 08:54 AM

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

Thread: Determine whether alpha |- gamma

LinkBack

Thread Tools

Display

Determine whether alpha |- gamma

Re: Determine whether alpha |- gamma

Re: Determine whether alpha |- gamma

Re: Determine whether alpha |- gamma

Similar Math Help Forum Discussions

Let alpha be a real number, alpha > -1 now show that

Let ^ be a nonempty indexing set, let A* = {A subscript alpha such that alpha is an..

Gamma - Gamma parameter estimation EM algorithm

find g(X) that transforms folded normal into gamma(alpha,beta)

Joint Gamma prior, Gamma likelihood with data; posterior distribution is...?

Search Tags