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

• Dec 29th 2010, 08:31 AM
x3bnm
Universal and existential statements for prime and composite numbers(proof)
I've a discrete mathematics book that has the following written theorems:

$\displaystyle n\, is\, prime\, \Leftrightarrow \,\forall\, r,s \in \mathbb{Z}^+,\, if\, n\, = r.s\,\, then\, r = 1\, or\, s = 1$

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

$\displaystyle n\, is\, prime\, \Leftrightarrow \,\exists\, r,s \in \mathbb{Z}^+,\, if\, n\, = r.s\,\, then\, r = 1\, or\, s = 1$

Also :

$\displaystyle n\, is\, composite\, \Leftrightarrow \,\exists\, r,s \in \mathbb{Z}^+ \,,\, if\, n\, = r.s\,\, then\, r \neq 1\, and \, s \neq 1$

Alternatively can't we write:

$\displaystyle n\, is\, composite\, \Leftrightarrow \,\forall\, r,s \in \mathbb{Z}^+ \,,\, if\, n\, = r.s\,\, then\, r \neq 1\, and \, s \neq 1$

Why my alternate method for stating the same theorem not right? Thanks.
• Dec 29th 2010, 09:00 AM
emakarov
Quote:

$\displaystyle 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.

Quote:

$\displaystyle 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 <=> $\displaystyle \exists\, r,s \in \mathbb{Z}^+,\,n = r\cdot s$ and $\displaystyle r \neq 1$ and $\displaystyle s \neq 1$.

Quote:

$\displaystyle 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: $\displaystyle \forall x.\,P(x)\to Q(x)$ while existential quantification is usually used with conjunction: $\displaystyle \exists x.\,P(x)\land Q(x)$ (though this is not an absolute rule, obviously).
• Dec 29th 2010, 10:34 AM
x3bnm
Thanks for your explanation. But i'm a little confused. You're saying that:

Quote:

Originally Posted by emakarov
$\displaystyle 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.

But how's the implication even true? Because $\displaystyle r \neq 1$ and $\displaystyle s \neq 1$ . Aren't you jumping to the conclusion without concrete proof?

Aren't you supposing at the beginning that $\displaystyle r=17$ and $\displaystyle 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
The statement should be, "n is composite <=> and

$\displaystyle \exists\, r,s \in \mathbb{Z}^+,\,n = r\cdot s\, and \,r \neq 1\, and \,s \neq 1$

You are right. Thanks for that.
• Dec 29th 2010, 10:57 AM
emakarov
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.

Quote:

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

Quote:

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.
• Dec 29th 2010, 11:11 AM
x3bnm
Quote:

Originally Posted by emakarov
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 $\displaystyle \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.(Happy)
• Jan 5th 2011, 09:05 AM
x3bnm
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):

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

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

Quote:

Originally Posted by emakarov
$\displaystyle 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.

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?
• Jan 5th 2011, 11:36 AM
emakarov
Quote:

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.
• Jan 6th 2011, 07:23 PM
x3bnm
Quote:

Originally Posted by emakarov
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.