I came across this problem in a test:
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 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) $∀m.∃n.m ≤ n \land \,\lnot(TwinPrime(n))$
b) $∃m.∀n.n≤m \rightarrow TwinPrime(n)$
c) $∀m.∃n.n≤m \land TwinPrime(n)$
d) $∃m.∀n. TwinPrime(n) \rightarrow n≤m$
I've tried to solve this by converting the sentences into their English equivalents, but the fact that we have to express "finiteness" using quantifiers eludes me. I have the answer key with me, but I am unable to work back from that either.
Some help/hint would be appreciated, thank you.
Best Answer
To say a subset of natural numbers is finite, we say that there is some natural number $m$ such that for any natural number greater than that $m$, that natural number is not in the subset. Likewise, to say that the set of all twin primes is finite, there must be some $m$ such that for all $n > m$, we have that $n$ and $n+2$ are not twin primes. Equivalently, we would say that if the set of all twin primes is finite it must entail that there is some $m$ such that if $n$ is a twin prime, $n \leq m$. So, in logical terms we have that $$\exists m. \forall n. TwinPrime(n) \rightarrow n \leq m$$
Then, why are the others wrong? Consider $\exists m. \forall n. n\leq m \rightarrow TwinPrimes(n)$. It is saying that given some $m$, we have that any natural $n$ lesser than $m$ is a twin prime, which is clearly false (for example, by the statement it is consistent to say that 2 and 4 are twin primes). Moreover, it says nothing about those $n$ such that $n\geq m$, so by this could be true that the set of twin primes are infinite.