# Expressing given problem in first order logic

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.

• 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. – Mauro ALLEGRANZA Sep 17 '18 at 12:05

## 2 Answers

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.

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?

• 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)? – Gokul Sep 17 '18 at 12:20
• 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. – Tanner Swett Sep 17 '18 at 16:54