1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ You cannot express "finiteness" using quantifiers. What you can do is express the fact that there is a twin-prime pair such that there is no twin-prime pair greater than it. $\endgroup$ – Mauro ALLEGRANZA Sep 17 '18 at 12:05
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

None of the first-order logic statements really express anything about finiteness. However, the statement "there are only finitely many twin primes" is equivalent to "there exists a number which is larger than all twin primes".

Can you figure it out now?

$\endgroup$
2
  • $\begingroup$ Pardon my ignorance, but the statement "there exists a number which is larger than all twin primes" is true, because if there are finitely many twin primes, we can always find a number which is greater than the greatest twin prime(since there are infinitely many numbers)? $\endgroup$ – Gokul Sep 17 '18 at 12:20
  • 1
    $\begingroup$ Well, yes... the statement "there exists a number which is larger than all twin primes" is true if there are only finitely many twin primes. But it is false if there are infinitely many of them. $\endgroup$ – Tanner Swett Sep 17 '18 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.