Results 1 to 8 of 8

Math Help - Universal and existential statements for prime and composite numbers(proof)

  1. #1
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Universal and existential statements for prime and composite numbers(proof)

    I've a discrete mathematics book that has the following written theorems:

    <br />
n\, is\, prime\, \Leftrightarrow \,\forall\, r,s \in \mathbb{Z}^+,\, if\, n\, = r.s\,\, then\, r = 1\, or\, s = 1<br />

    My question why is this a universal statement on the right? Can't we just use existential statement like this:

    <br />
n\, is\, prime\, \Leftrightarrow \,\exists\, r,s \in \mathbb{Z}^+,\, if\, n\, = r.s\,\, then\, r = 1\, or\, s = 1<br />

    Also :

    <br />
n\, is\, composite\, \Leftrightarrow \,\exists\, r,s \in \mathbb{Z}^+ \,,\, if\, n\, = r.s\,\, then\, r \neq 1\, and \, s \neq 1<br />

    Alternatively can't we write:

    <br />
n\, is\, composite\, \Leftrightarrow \,\forall\, r,s \in \mathbb{Z}^+ \,,\, if\, n\, = r.s\,\, then\, r \neq 1\, and \, s \neq 1<br />

    Why my alternate method for stating the same theorem not right? Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    n\, is\, prime\, \Leftrightarrow \,\exists\, r,s \in \mathbb{Z}^+,\, if\, n\, = r.s\,\, then\, r = 1\, or\, s = 1
    This equivalence is false. Indeed, consider n = 4. Then there exist r = 17 and s = 999 such that n = r * s implies r = 1 or s = 1. The implication is true because the premise is false. Thus, the right-hand side of the equivalence is true while the left-hand side is false.

    n\, is\, composite\, \Leftrightarrow \,\exists\, r,s \in \mathbb{Z}^+ \,,\, if\, n\, = r.s\,\, then\, r \neq 1\, and \, s \neq 1
    This is also false; consider n = 5 and r and s as above. The statement should be, "n is composite <=> \exists\, r,s \in \mathbb{Z}^+,\,n = r\cdot s and r \neq 1 and s \neq 1.

    n\, is\, composite\, \Leftrightarrow \,\forall\, r,s \in \mathbb{Z}^+ \,,\, if\, n\, = r.s\,\, then\, r \neq 1\, and \, s \neq 1
    This is false for all n because for r = n and s = 1, the premise of the implication in the right-hand side is true, but the conclusion is false.

    The idea is that n is prime if all its divisors are trivial, but n is composite if there exist nontrivial divisors.

    Also, universal quantification is usually used with implication: \forall x.\,P(x)\to Q(x) while existential quantification is usually used with conjunction: \exists x.\,P(x)\land Q(x) (though this is not an absolute rule, obviously).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16
    Thanks for your explanation. But i'm a little confused. You're saying that:

    Quote Originally Posted by emakarov View Post
    <br />
n\, is\, prime\, \Leftrightarrow \,\exists\, r,s \in \mathbb{Z}^+,\, if\, n\, = r.s\,\, then\, r = 1\, or\, s = 1<br />

    This equivalence is false. Indeed, consider n = 4. Then there exist r = 17 and s = 999 such that n = r * s implies r = 1 or s = 1. The implication is true because the premise is false. Thus, the right-hand side of the equivalence is true while the left-hand side is false.
    But how's the implication even true? Because r \neq 1 and s \neq 1 . Aren't you jumping to the conclusion without concrete proof?

    Aren't you supposing at the beginning that r=17 and s = 999? How's this supposition lead to the truth of conclusion?

    I don't get it. Can you explain a bit more? Also:

    Quote Originally Posted by emakarov View Post
    The statement should be, "n is composite <=> and

    <br />
\exists\, r,s \in \mathbb{Z}^+,\,n = r\cdot s\, and \,r \neq 1\, and \,s \neq 1<br />
    You are right. Thanks for that.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    Look at the definition of when a first-order formula is true. "If A, then B" is true if A is false or B is true. So, "If 4 = 17 * 999, then 17 = 1 or 999 = 1" is true because the premise is false.

    Aren't you supposing at the beginning that s = 999 and s = 999?
    It's not that I suppose (i.e., assume); I just note that taking these values makes the statement after \exists true; therefore, the existential statement is true.

    How's this supposition lead to the truth of conclusion?
    There does not have to be a causal connection between the premise and the conclusion in order for the (material) implication to be true. Ultimately, the reason for this is the definition given above. Philosophers may argue about other definitions. Relevance logic has a different concept of implication.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16
    Quote Originally Posted by emakarov View Post
    Look at the definition of when a first-order formula is true. "If A, then B" is true if A is false or B is true. So, "If 4 = 17 * 999, then 17 = 1 or 999 = 1" is true because the premise is false.

    It's not that I suppose (i.e., assume); I just note that taking these values makes the statement after \exists true; therefore, the existential statement is true.

    There does not have to be a causal connection between the premise and the conclusion in order for the (material) implication to be true. Ultimately, the reason for this is the definition given above. Philosophers may argue about other definitions. Relevance logic has a different concept of implication.
    AAAAA....Now i get it. Thanks a lot. This stuff is interesting.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16
    Although I marked this thread "Solved'' previously I am still having problems understanding quantified statement.

    Sorry for reopening this thread but it's bothering me past couple of days. i couldn't help it.

    The definition of prime number is which i mark as (1):

    <br />
n\, is\, prime\, \Leftrightarrow \,\forall\, r,s \in \mathbb{Z}^+ \,,\, if\, n\, = r.s\,\, then\, r = 1\, or\, s = 1\,\,\,\,\,\,\,\,\,\,\,\,(1)<br />

    I wanted to use the same statement using existential symbol. But then emakarov said:

    Quote Originally Posted by emakarov View Post
    <br />
n\, is\, prime\, \Leftrightarrow \,\exists\, r,s \in \mathbb{Z}^+,\, if\, n\, = r.s\,\, then\, r = 1\, or\, s = 1<br />

    This equivalence is false. Indeed, consider n = 4. Then there exist r = 17 and s = 999 such that n = r * s implies r = 1 or s = 1. The implication is true because the premise is false. Thus, the right-hand side of the equivalence is true while the left-hand side is false.
    Now I can say the same thing as emakarov said for definition of prime number marked as (1), can't i?

    Say r = 17 and s = 999 and n = 4. So the premise of (1) is false but implication is true.

    So the right side of equivalence (1) is true but left side is false. Where am i making mistake?

    Can anyone kindly point out err in my reasoning?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    Now I can say the same thing as emakarov said for definition of prime number marked as (1), can't i?
    To declare the right-hand side of (1) true, one must check all possible r and s, not just r = 17 and s = 999. In particular, for r = s = 2 (and n = 4), the proposition "if n = r * s, then r = 1 or s =1" is false because the premise is true, but the conclusion is false. This one counterexample makes the whole universal quantification false.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16
    Quote Originally Posted by emakarov View Post
    To declare the right-hand side of (1) true, one must check all possible r and s, not just r = 17 and s = 999. In particular, for r = s = 2 (and n = 4), the proposition "if n = r * s, then r = 1 or s =1" is false because the premise is true, but the conclusion is false. This one counterexample makes the whole universal quantification false.
    So for "For All" statement I have to check for all possible values in the domain that makes the quantified statement true or false and if i find a counterexample the statement is false.

    Thanks for clearing that up. That's it I have no more question. Again thanks for taking the time explaining this.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: May 8th 2011, 02:54 PM
  2. Proof involving prime numbers
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 7th 2011, 03:38 PM
  3. Universal quantified statements
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 5th 2010, 09:06 AM
  4. proof with perfect and prime numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 28th 2010, 08:46 PM
  5. Proof with prime numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 25th 2009, 09:58 PM

/mathhelpforum @mathhelpforum