Results 1 to 13 of 13

Math Help - logical quantification

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    90

    logical quantification

    Hello everyone,
    I'm having problems with the following type of tutorial questions (yes, there are more of them):

    Use logic notation to express the following:
    "There is at most one x with P(x)"

    I understand that to mean, "if there exists an x such that P(x), then for all other x not P(x)."

    <br />
(\exists x)[P(x)] \rightarrow (\forall y)[\neg P(x)], x \neq y<br />

    but this is wrong, or at least badly expressed. Would the following be right?

    <br />
(\exists x, \forall y; x \neq y)[P(x)]<br />
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member apcalculus's Avatar
    Joined
    Apr 2009
    From
    Boston
    Posts
    293
    Quote Originally Posted by bmp05 View Post
    Hello everyone,
    I'm having problems with the following type of tutorial questions (yes, there are more of them):

    Use logic notation to express the following:
    "There is at most one x with P(x)"

    I understand that to mean, "if there exists an x such that P(x), then for all other x not P(x)."

    <br />
(\exists x)[P(x)] \rightarrow (\forall y)[\neg P(x)], x \neq y<br />

    but this is wrong, or at least badly expressed. Would the following be right?

    <br />
(\exists x, \forall y; x \neq y)[P(x)]<br />
    Hmm... I would have expressed this as a conditional. If there two x-values x1 and x2 such that P(x1) and P(x2), then x1 = x2. Does this make sense?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2009
    Posts
    90
    Thanks for the reply apcalculus, that was a good explanation.

    so you mean something like:

    <br />
(\exists x,y)[(P(x) \leftrightarrow P(y)) \rightarrow (x = y)]<br />

    can you write this as follows?

    <br />
(\exists x,y; x=y)[P(x) \leftrightarrow P(y)]<br />
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    Apcalculus gave the right hint.

    Translating sentences of the form "If there exists x such that P(x), then Q(x)" is a little counterintuitive. One could try

    \left(\exists x\,P(x)\right)\to Q(x)

    but this would not be right because the scope of \exists x does not extend to Q. Another attempt is

    \exists x.\,(P(x)\to Q(x))

    This is also wrong because this proposition affirms the existence of something, while the original plain language sentence did not claim this.

    The right way to translate "If there exists x such that P(x), then Q(x)" is using the universal quantifier:

    \forall x.\,(P(x)\to Q(x))
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Mar 2009
    Posts
    90
    That may well be, but you're making me cry!!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Mar 2009
    Posts
    256
    Thanks
    1
    Quote Originally Posted by bmp05 View Post



    I understand that to mean, "if there exists an x such that P(x), then for all other x not P(x)."
    It is not a conditional and the right expression is:

    There exist an x with P(x) and for all other x not P(x)
    This in logic in quantifier form is expressed as follows:

    \exists xP(x)\wedge\forall x\forall y( P(x)\wedge P(y)\Longrightarrow x = y)
    Last edited by xalk; November 25th 2009 at 05:11 AM. Reason: missing an expression and a typo
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    Well, look: you need to translate the following statement.
    If there two x-values x1 and x2 such that P(x1) and P(x2), then x1 = x2
    Instead of this, I'll translate a not-very-meaningful statement just to give an example:

    If there is an x such that P(x) and P(x), then x=x.

    This would be

    \forall x.\,\big(P(x)\land P(x)\to x=x\big)
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    Of course, to really solve the problem, besides writing the actual formula, you need to understand very well why
    If there two x-values x1 and x2 such that P(x1) and P(x2), then x1 = x2.
    is equivalent to your original statement
    There is at most one x with P(x)
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Mar 2009
    Posts
    256
    Thanks
    1
    Quote Originally Posted by emakarov View Post
    Well, look: you need to translate the following statement.
    Instead of this, I'll translate a not-very-meaningful statement just to give an example:

    If there is an x such that P(x) and P(x), then x=x.

    This would be

    \forall x.\,\big(P(x)\land P(x)\to x=x\big)
    Are you referring to my formula
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    Quote Originally Posted by xalk View Post
    Are you referring to my formula
    No, I am referring to apcalculus's post.

    I don't fully agree with your version.
    Quote Originally Posted by xalk View Post
    It is not a conditional and the right expression is:

    There exist an x with P(x) and for all other x not P(x)
    The right expression of the original statement ("There is at most one...")? This is not correct because the original statement does not assert the existence of anything while your sentence does.

    This in logic in quantifier form is expressed as follows:

    \forall xP(x)\wedge\forall x\forall y( P(x)\wedge P(y)\Longrightarrow x = y)
    This is also strange because now instead of "There exist an x with P(x)" you write \forall xP(x).
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Mar 2009
    Posts
    90
    Quote Originally Posted by emakarov View Post
    Of course, to really solve the problem, besides writing the actual formula, you need to understand very well why
    is equivalent to your original statement
    Yes, I understand the reason. That makes sense, but the quantifiers and the logical operators do not make sense. The problem is the overloading of the x-variable. That hurts my head. It's the formula-writing which is the problem, not the problem itself.

    I have to admit, I find this very hard. Thank you all for your help, nevertheless.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Banned
    Joined
    Mar 2009
    Posts
    256
    Thanks
    1
    Quote Originally Posted by emakarov View Post
    No, I am referring to apcalculus's post.

    I don't fully agree with your version.

    The right expression of the original statement ("There is at most one...")? This is not correct because the original statement does not assert the existence of anything while your sentence does.

    This is also strange because now instead of "There exist an x with P(x)" you write \forall xP(x).
    Yes thank a typo mistake,i corrected my post
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Mar 2009
    Posts
    90
    Thanks emakarov, it took a while for this to sink in. Really. Anyway, thanks again.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question about second-order quantification
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 7th 2011, 07:20 AM
  2. Prove/disprove using logical using logical arguments
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 24th 2010, 06:29 AM
  3. Replies: 3
    Last Post: January 21st 2010, 07:45 AM
  4. Logic: quantification
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 1st 2009, 06:18 AM
  5. universal quantification over null set
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 18th 2007, 03:07 PM

Search Tags


/mathhelpforum @mathhelpforum