First Order Logic: Prove that the infinitely many twin primes conjecture is equivalent to existence of infinite primes

1.4k Views Asked by At

I'm learning First Order Logic independently using a college textbook. I've been doing some self exercise question in it and came across this one, which I can't seem to figure out how to do:

Let there be a language $L = \{ +, \cdot, 0, 1, < \}\cup \{ c_{n}\mid n\in \mathbb{N}\}$ and $N$ a structure such that $|N| = \mathbb{N}$ whereby $c^N_{n} = n$ and all the rest of the language is interpreted as the standard symbols in $\mathbb{N}$ ($+$ is addition, $\cdot$ is multiplication etc.). Let us denote $T = Th(N)$

For every model M of T we shall say that $a \in |M|$ is an infinite member if it holds that $c^M_{n} < a$ for every $n\in{N}$

For every model M of T we shall say that $p \in |M|$ is a prime number if it holds that $c^M_1 < p$ and for every $a, b \in |M|$ if $p = a\cdot^M b$ then $a = p$ or $a = c^M_1$

Show that the following are equivalent:

  1. In $N$ there exist an infinite number of prime numbers $p$ such that $p +^N 2 $ is also a prime. (This is also known as the infinitely many twin primes conjecture and is an unsolved problem in mathematics)
  2. There exists a model $M$, such that $M \vDash T$ with at least one infinite prime $p$ such that $p +^N 2 $ is also prime
  3. For every model $M$, such that $M\vDash T$ with infinite members there exists an infinite prime such that $p +^N 2 $ is also prime

I've sat on it for over an hour and am just lost as to how to prove it. Obviously $3 \Rightarrow 2$ is trivial, but I have absolutely no clue what to do with the others

Any help is appreciated, Thank you!

1

There are 1 best solutions below

2
On BEST ANSWER

The missing implications are clever uses for the fact that $T$ is a complete theory.

$(2)\implies(1)$: In $M$ there is an infinite prime which has a twin, $M$ satisfies the following sentences, for every $n$, "There exists $p>c_n$ such that $p,p+2$ are both prime". But since $T$ is complete it must prove those sentences, and therefore they must hold in $N$, which exactly means $(1)$ is true.

$(1)\implies(3)$: Suppose that $(3)$ fails, and $M$ is a model without infinite twin primes, but with infinite members. Then in $M$ it is true that "There is $c$ such that there are no twin primes larger than $c$", by the virtue of completeness of $T$, this must be true in $N$ which means that there are only finitely many twin primes (since a bounded set in $\Bbb N$ is finite). And therefore $(1)$ must also fail.