Results 1 to 4 of 4

Thread: Determine whether alpha |- gamma

  1. #1
    Junior Member
    Joined
    Jul 2011
    Posts
    26

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jul 2011
    Posts
    26

    Re: Determine whether alpha |- gamma

    Quote Originally Posted by dwally89 View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jul 2011
    Posts
    26

    Re: Determine whether alpha |- gamma

    Quote Originally Posted by emakarov View Post
    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 :-)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Let alpha be a real number, alpha > -1 now show that
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: Nov 27th 2011, 07:14 PM
  2. Replies: 1
    Last Post: Nov 14th 2011, 02:48 AM
  3. Gamma - Gamma parameter estimation EM algorithm
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: Jul 24th 2010, 09:53 AM
  4. find g(X) that transforms folded normal into gamma(alpha,beta)
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Jul 22nd 2010, 11:07 AM
  5. Replies: 0
    Last Post: Mar 30th 2008, 12:44 PM

Search Tags


/mathhelpforum @mathhelpforum