11
$\begingroup$

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!

$\endgroup$
  • 3
    $\begingroup$ From a safe distance this smells like an application of the compactness theorem. $\endgroup$ – Myself Jan 13 '15 at 19:03
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am confused. In order to use completeness and claim that T proves a formula, shouldn't we show that said formula holds in every model of T? It seems all we know is that the formula holds only in one model ($M$). $\endgroup$ – chi Jan 14 '15 at 0:14
  • 3
    $\begingroup$ If $M$ is a structure, then $Th(M)$ is complete, since every statement is either true or false in $M$. $\endgroup$ – Asaf Karagila Jan 14 '15 at 0:27

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.