Results 1 to 6 of 6

Math Help - Sets and logic

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    7

    Sets and logic [SOLVED]

    I'm having a hard time with these 2 problems.











    I could tip 3$US for your help. If it's against the rules let me know and I'll edit my post.
    Last edited by Zathan; September 24th 2010 at 10:28 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    You could consider the domain to be a group of people and P(x,y) to mean "x knows y". Try to figure out, provided the first proposition is true, whether the second proposition is always true, is always false, or can be either.

    Also, if \exists x\forall y\,P(x,y) is false, it means that \neg\exists x\forall y\,P(x,y) is true. You can move the negation inside, i.e., put it in front of P. Then it is easier to compare the two formulas. Moving negation inside is also useful in problem #2. (Edit: Disregard the following. Basically, it reduces to question whether \forall x\,Q(x) implies \exists x\,Q(x). To answer it, it is important to know if the domain is empty.)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2010
    Posts
    7
    Is it correct to say (for #1): AxEy P(x,y) can be false. If we let the domain of discourse be the persons: Roger, John, Tony and let P(x,y) be the statement "x knows y". Then ExAy P(x,y) is true, but AxEy P(x,y) is false ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    If we let the domain of discourse be the persons: Roger, John, Tony and let P(x,y) be the statement "x knows y". Then ExAy P(x,y) is true, but AxEy P(x,y) is false
    First, why are you saying that ExAy P(x,y) is true since by assumption in problem 1 it is false? Second, what you said depends on who among Roger, John and Tony knows whom. You have not provided this information. Third, the fact that AxEy P(x,y) can be false is not the whole answer: it is not clear if it is always false under the given assumption or if it can be true as well. However, the idea is right: by varying who knows whom, you can construct situations where ExAy P(x,y) is false (hence, the assumption is true), and AxEy P(x,y) is true in some situations and false in others.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2010
    Posts
    61
    First, before addressing the problem as stated, I think the crucial point is that as long as D\neq\varnothing, you may use the following theorems (which are really the same theorem in disguise):

    1. \neg(\forall z Q(z))\iff\exists z(\neg Q(z))
    2. \neg(\exists z Q(z))\iff\forall z(\neg Q(z))

    So for example in your first problem, you use theorem 2 followed by theorem 1 (written with judicious use of parentheses).

    \neg(\exists x\forall y P(x,y))\iff\forall x(\neg(\forall y P(x,y)))\iff\forall x\exists y (\neg P(x,y)).

    Unfortunately, what you assume ( \neg(\exists x\forall y P(x,y))) does not imply anything about the statement you are given to evaluate ( \forall x\exists y P(x,y)). This most likely means that your question is mis-worded. This can be seen further by specifying two examples for P which exhibit opposite behavior.

    Let D=\mathbb{R}. Let P_1(x,y)=(x<y). Then it is clear that your assumption holds: the statement “there exists an x such that for all y, x is less than y” is false. Again, this is the same thing as asserting \neg(\exists x\forall y P_1(x,y)). Now, one may evaluate the statement “for all x, there exists a y such that x < y” as being true. Thus, \forall x\exists y P_1(x,y) is true.

    Now, with the same D, let P_2(x,y)=(y^2=-1). Then it is clear that your assumption holds: the statement “there exists an x such that for all y, y-squared is -1” is false. Again, this is the same thing as asserting \neg(\exists x\forall y  P_2(x,y)). Now, one may evaluate the statement “for all x, there exists a y such y-squared is -1” as being false. Thus, \forall  x\exists y P_2(x,y) is false.

    So question 1 as given has no correct answer (your assumption tells you nothing about the truth or falsehood of the statement you wish to evaluate).

    You can do similar analysis to show that question 2 is also mis-worded. You may, however, be able to show the converse using the following theorem (assuming a non-empty domain):
    \forall zQ(z)\implies\exists zQ(z)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    Well, let's see. The fact \neg(\exists z Q(z))\iff\forall z(\neg Q(z)) holds without the assumption that the domain is nonempty. I agree that in problem 1, the second formula can be true in some interpretations and false in others. However, in problem 2, the second formula is false (provided the first one is false). Here the fact that the domain is nonempty is essential because otherwise the second formula is vacuously true.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help with sets and logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 13th 2011, 02:56 PM
  2. logic sets help
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 1st 2009, 06:48 AM
  3. logic and sets help!!
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: November 24th 2008, 12:30 AM
  4. logic sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 17th 2008, 10:04 AM
  5. Sets and Logic
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 23rd 2008, 05:15 PM

Search Tags


/mathhelpforum @mathhelpforum