CMI2010-A-04

Question

Let $m$ and $n$ range over natural numbers and let $\text{Prime}(n)$ be true if $n$ is a prime number. Which of the following formulas expresses the fact that the set of prime numbers is infinite?

• A. $(\forall m) (\exists n) (n > m) \text{ implies Prime}(n)$
• B. $(\exists n) (\forall m) (n > m) \text{ implies Prime}(n)$
• C. $(\forall m) (\exists n) (n > m) \wedge \text{Prime}(n)$
• D. $(\exists n) (\forall m) (n > m) \wedge \text{Prime}(n)$

Comments

Debashish Deka , Bikram explain each option what I am getting is not close to what question asking.

Answer 1

Answer – C.

(∀m)(∃n)(n>m)∧Prime(n)

i.e any m you take from set of Natural no there exists some n such that (n>m) AND n is PRIME

Answer 2

Ans B)

i.e. among all natural numbers which are prime are range greater than other range of natural number

Comments

why not c?

---

@srestha

I am also getting c

Translation of option c:

For every natural number n, there is a natural number m which is greater than m and it is a prime.

If this is true,one can give me any natural number m, i can give a prime  number n which is greater than m.

Hence it implies prime numbers are infinite.

Translation for other options:

Option a:

for every natural number m, there is a natural number n and if n is greater than m then n is prime. This is false if we take m=2,n=4.

Option B:

If there is a natural number n greater than all the natural numbers, then n is a prime.

Option d:

There is natural number n which is greater than all the natural numbers,and n is prime.

---

@chirudeepnamini

what is difference between c and d??

---

@srestha

option c says that :

for every natural number m,there is a natural number n greater than m and n is prime.

this n can be less than some other natural number x.

for example, for m=1 i can have n=2 , for m=2,n=3,for m=3,i can have n=5, for m=4, i can have, n=5......

But option d says that:

There is a natural number n, greater than all the natural numbers  and n is prime.

this says that, for all values of m=1,m=2,m=3,...... there is a single natural number n greater than every value of m and it is prime(single is not correct word to use)

clearly such number can't exist.

the words in bold italic makes the difference between option c,d

this image might be helpful

edit:

 page number 60 of kenneth rosen 7th edition has image that explains in a better way