CODEWITHSUNDEEP
logicdiscrete-mathematics
saltedFish
saltedFish

Reputation: 11

Translate the following assertions into logical formulae

Consider Natural number only. Assume there is a predicate IsPrime(x), which is TRUE iff x is a prime number.

1) There is a prime number in every interval whose size is10^8.

2) There are infinite pairs of consecutive prime numbers (p,q) satisfying |p - q|<=10^8.

3) Are the above two assertions logically equivalent? Which must be false? Why?

Upvotes: 1

Views: 131

Answers (1)

Patrick87
Patrick87

Reputation: 28332

(1) There is a prime number in every interval whose size is 10^8.

For every pair (x, y) there exists a z such that if the interval [x, y] is at least 10^8 then there exists a z in that interval which is prime.

ForAll(x).ForAll(y).Exists(z).(y - x >= 10^8) -> (x <= z <= y and IsPrime(z)).

(2) There are infinite pairs of consecutive prime numbers (p,q) satisfying |p - q|<=10^8.

For every x there are p and q with x <= p < q such that p and q are prime and |p - q| <= 10^8.

ForAll(x).Exists(p).Exists(q).(x <= p < q) and IsPrime(p) and IsPrime(q) and (q - p) <= 10^8

(3) No, they are not logically equivalent. There can be infinitely many pairs of prime numbers which differ by less than 10^8, but if there is even a single interval of size 10^8 which does not contain a prime number (either on the ends or in the middle), the first condition is false. Therefore, it's possible for the first condition to be false and not the second. If exactly one of these two assertions is provably false, it must therefore be the first. Indeed, the first of these would imply a linear lower bound for the number of primes up to a given number, but we know from the prime number theorem that n/log(n) is the real asymptotic behavior.

Upvotes: 1

Related Questions