16
$\begingroup$

I have a proof of the twin primes conjecture using the compactness theorem. It cannot be correct, because it is too simple. Please help find the flaw.

Proof by contradiction, Assumption: there are only $n$ twin primes.

Let $L$ be the language $\{ +, \cdot, 0, S \}$ and $T = Th(\mathbb{N},L)$ be the first order theory of $\mathbb{N}$, with the standard interpretation of the symbols in $L$, with $S$ being the successor function. In the following, numbers like $1$, $2$, $3$ etc. in formulas represent the constant terms $S0$, $SS0$, $SSS0$ etc.

Now let $L^*$ be the language $L$, augmented by $n+1$ constants:

$L^* = L \cup \{ c_{i}\mid i \in N\}$, with $N = \{ 1, ..., n+1\}$

Consider the following sets of formulas:

$\Phi_1 = \{ \neg \mathrm{divides}(p,c_i) \land \neg \mathrm{divides}(p,c_i+2) | i \in N, p \in Primes \}$

$\Phi_2 = \{ c_i \not= c_j \mid i,j\in N, i \not= j \}$

Here $Primes$ denotes the set of constant terms that represent primes (i.e. $P=\{2,3,5,... \}$), and $\mathrm{divides}(p,c)$ is the formula $ \exists k(k \not= 1 \land k \not=c \land k \cdot p = c)$, asserting that $p$ is a true divisor of $c$.

Then $\Psi = T \cup \Phi_1 \cup \Phi_2$ is inconsistent. By compactness, there must be an inconsistent finite subset $\Psi_0 \subset \Psi$. In particular, $\Psi_0$ can only contain finitely many formulas of $\Phi_1$, referencing only finitely many primes. Let $M \subset Primes$ be the set of primes being referenced, and $\Pi M$ the product of all primes in $M$. Then for any $i\ge 1$, the numbers $i\cdot \Pi M-1$ and $i\cdot \Pi M+1$ are coprime to M. Thus interpreting every $c_i$ with $i\cdot \Pi M-1$, we have an interpretation that satisfies all formulas in $\Psi_0$, contradiction.

$\endgroup$
  • 10
    $\begingroup$ I don’t have a lot of time to look at this right now but one thing jumps out at me is you seem to be assuming that the negation of twin primes means that $\Phi_1$ is inconsistent... it means it is not satisfied by $\mathbb N$, not that it is inconsistent. $\endgroup$ – spaceisdarkgreen Dec 5 '19 at 19:47
  • 2
    $\begingroup$ "It cannot be correct, because it is too simple." Maybe it's very simple, but that can always be a great starting point for further more complex attempts! $\endgroup$ – wjmccann Dec 5 '19 at 20:35
  • $\begingroup$ @spaceisdarkgreen: You caught me. Even if there are finitely many twin primes, $\Phi_1$ is still consistent, because for every finite set of primes, you find twins that are coprime to that set. Thus, we'd have models with infinite twins, that are coprime to all finite primes, but still may have infinite divisors. Do you want to make an answer of it? $\endgroup$ – Max Kubierschky Dec 5 '19 at 20:42
  • 1
    $\begingroup$ Why is $\Psi$ inconsistent? If $M$ is a model of $\Psi$, it is a nonstandard model of arithmetic in which each $c_i$ is interpreted as a nonstandard number $A$ such that neither it nor $A+2$ is divisible by any standard prime. This does not mean that $A$ is prime. What is the issue? $\endgroup$ – Andrés E. Caicedo Dec 5 '19 at 21:11
  • $\begingroup$ I am not familiar with model theory. Why is $T \cup \Phi_1 \cup \Phi_2$ inconsistent, without assuming the twin primes conjecture? $\endgroup$ – user253751 Dec 6 '19 at 9:44
10
$\begingroup$

It is not correct to conclude that $\Psi$ is inconsistent. It is true that there is no assignment of values to the $c_i$ in the standard model $\mathbb{N}$ which makes it a model of $\Psi$. However, that doesn't mean that $\Psi$ is inconsistent, because there could be some different model of it (with a nonstandard underlying model of natural numbers). Indeed, your argument proves $\Psi$ is finitely satisfiable, so by compactness such a model exists.

Here is a simpler example of the same phenomenon. Add just a single constant $c$ to the language of arithmetic and consider sentences $\varphi_n$ saying that $c>n$ for each $n\in\mathbb{N}$. Then $T\cup\{\varphi_n:n\in\mathbb{N}\}$ is finitely satisfiable, but again there is no way to give $c$ a value in $\mathbb{N}$ to make it a model. Instead, to get a model you need to take a nonstandard model of $T$ which has elements which are greater than every standard natural number.

$\endgroup$
6
$\begingroup$

In fact, not only is your theory consistent, but (regardless of the status of the twin primes conjecture) in any nonstandard model of arithmetic we can find interpretations of the $c_i$ (we can even do that with countably many $c_i$, not just $n+1$).

The point is that the factorial function makes sense in any nonstandard model of arithmetic, using Gödel's argument to code recursive functions within the language of arithmetic, see here. Let $M$ be a nonstandard model of arithmetic and let $I$ be an infinite (i.e., nonstandard) number in $M$. For $i\in N$, let $c_i=(I+i)!-1$. The $c_i$ so defined are distinct, and the usual (Euclid's) argument for the infinitude of primes shows that no standard prime divides any of the $c_i$ or of the $c_i+2$. Note that absolutely nothing changes if we have countably many $c_i$ rather than only $n+1$.

(Now, if the twin primes conjecture is false, and $N$ as in your post, then in no model of your theory is any of the $c_i$ a prime number. But this is not an issue.)

$\endgroup$

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.