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

**x3bnm** · December 29th 2010, 08:31 AM

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

$ 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:

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

Also :

$ 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:

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

**emakarov** · December 29th 2010, 09:00 AM

$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).

**x3bnm** · December 29th 2010, 10:34 AM

Thanks for your explanation. But i'm a little confused. You're saying that:

Originally Posted by emakarov

$ 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 $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:

Originally Posted by emakarov

The statement should be, "n is composite <=> and

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

You are right. Thanks for that.

**emakarov** · December 29th 2010, 10:57 AM

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.

**x3bnm** · December 29th 2010, 11:11 AM

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

**x3bnm** · January 5th 2011, 09:05 AM

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):

$ 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:

Originally Posted by emakarov

$ 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?

**emakarov** · January 5th 2011, 11:36 AM

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.

**x3bnm** · January 6th 2011, 07:23 PM

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.

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

LinkBack

Thread Tools

Display

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

Similar Math Help Forum Discussions

Order of existential/universal "steps" in proofs with multiple mixed quantifiers

Proof involving prime numbers

Universal quantified statements

proof with perfect and prime numbers

Proof with prime numbers