CMI2015-A-01

Question

Twin primes are pairs of numbers $p$ and $p+2$ such that both are primes—for instance, $5$ and $7$, $11$ and $13$, $41$ and $43$. The Twin Prime Conjecture says that there are infinitely many twin primes.
Let $\text{TwinPrime}(n)$ be a predicate that is true if $n$ and $n+2$ are twin primes. Which of the following formulas, interpreted over positive integers, expresses that there are only finitely many twin primes?

• A. $\forall m \cdot \exists n \cdot m \leq n \text{ and not(TwinPrime}(n))$
• B. $\exists m \cdot \forall n \cdot n \leq m \text{ implies TwinPrime}(n)$
• C. $\forall m \cdot \exists n \cdot n \leq m \text{ and TwinPrime}(n)$
• D. $\exists m \cdot \forall n \cdot  \text{TwinPrime}(n) \text{ implies }n \leq m$

Comments

I am not sure but according to me -

Let T = {$n_1,n_2,n_3....n_k$} for some k, be the set of all positive integers n such that n and n+2 are primes.
Now if this T is finite then there must exist a maximum number m such that $\forall_i n_i<=m.$

Now coming to Option D -

$∃m.∀n.$ TwinPrime(n) implies $n≤m$
$\Rightarrow∃m(∀n($ TwinPrime(n) implies $n≤m$))

It says that There exist a positive integer m such that for all positive integer n if n and n+2 are primes then n is less then or equal to m.

Expression can be expanded as -

$∃m((TwinPrime(n_1) \rightarrow n_1≤m)\wedge(TwinPrime(n_2) \rightarrow n_2≤m) $.... $.\wedge(TwinPrime(n_k) \rightarrow n_k≤m ))$

$\Rightarrow ((TwinPrime(n_1) \rightarrow n_1≤m_1)\wedge(TwinPrime(n_2) \rightarrow n_2≤m_1) ...\wedge(TwinPrime(n_k) \rightarrow n_k≤m_1 ) )\vee (TwinPrime(n_1) \rightarrow n_1≤m_2)\wedge(TwinPrime(n_2) \rightarrow n_2≤m_2 $.... $\wedge(TwinPrime(n_k) \rightarrow n_k≤m_2 ......  ) )$

---

Let us assume that the set of twin primes nos. are finite.

So,the set of twin prime numbers can be represented as

T = { a₁,a₂,a₃,............,a_n} where a_i's are twin prime numbers.

Now, let us asume that the numbers in the set T are written in ascending order.

That is a₁ <= a₂ <= ..........<= a_n 

So, we get

for all i ∈ [1,n] implies a_i <= a_n

which means for all a_i ∈ T implies a_i <= a_n

which means there exist a_n ∈ N such that for all a_i ∈ T implies a_i <= a_n 

which means there exist a_n ∈ N such that for all n .Twin prime(n) implies n<= a_n [ Note that Twin prime(n) is true iff n ∈ T ]

which means there exist m ∈ N such that for all n. Twin prime(n) implies n<=m. [ assuming a_n = m]

which matches with option D.

---

option C) is wrong

here m=n or n+2

So, m is depending on n

and there is no possibility that n could be depend on m

So , for all n , there exist a m is true statement here

Answer 1

Option D is correct.

We can see that "there are finitely many twin primes" is logically equivalent to the fact that "there exists a number which is greater than all the twin primes".

This is expressed in the last option.

Answer 2