1
$\begingroup$

I was recently reading a post basically discussing an "intuition" that Goldbach's Conjecture may be a statement which is undecidable (the post does not specify which axiomatic system the statement is undecidable in, I'm assuming Peano Arithmetic). I read the relevant passage in the article mentioned by the post, and as a side note, I believe the "intuition" given in said article is quite...hand-wavy. I don't see how this is "intuitive." Anyway, to quote wikipedia:

"The elements of any model of Peano arithmetic are linearly ordered and possess an initial segment isomorphic to the standard natural numbers. A non-standard model is one that has additional elements outside this initial segment."

My question is this: Suppose we have a non-standard model of PA, $M$, with initial segment $m \cong \mathbb{N}$ via $f:m \rightarrow \mathbb{N}$. Clearly we may define $x \in m$ to be "prime" if and only if $f(x)$ is prime in the usual sense. But what about $y \in M-m$? In general, how would one go about defining a "prime number" in a non-standard model?

This question is probably very dependent on specific non-standard models. The reason I ask is this: Suppose one were to attempt to prove independence of GC with PA via finding models $M, Q$ in which GC is true and false respectively. If one were unable to define primes outside the initial segments of these models $m,q$, essentially you'd be stuck with the original conjecture in the standard model due to the existence of isomorphisms $f:m \rightarrow \mathbb{N}$ and $g: q \rightarrow \mathbb{N}$, so you might as well attack the conjecture in the standard sense. Alternatively, if one could find such a definition, it may be easier to find a counterexample outside the initial segments (or it may not, this is speculative, one could at least try).

$\endgroup$
  • 1
    $\begingroup$ One defines prime in any of the usual ways. The school way (greater than $1$ and having no divisors other than $1$ and itself) works. $\endgroup$ – André Nicolas Jan 25 '16 at 22:02
  • 1
    $\begingroup$ Prime is defined the same way - not the non-trivial product of two smaller elements. The non-standard model still uses the same language. $\endgroup$ – Thomas Andrews Jan 25 '16 at 22:03
  • 1
    $\begingroup$ A slightly weird feature here is that if GC is independent (of PA, say), then it must be true in the standard model N, since it is false in N, then the counterexample 2m which is not the sum of two smaller primes, provably exists by PA (since in PA there is a term denoting the integer 2m and then it's just a matter of verifying finitely many numbers are not primes). So a proof that GC is independent of PA is a proof that it is true in N. $\endgroup$ – Ned Jan 25 '16 at 22:26
  • $\begingroup$ Right, I noticed that in the original post and thought it was fascinating. I seriously don't understand how it is "intuitively" undecidable though, a sentiment echoed by many commenters in the original post. $\endgroup$ – M10687 Jan 25 '16 at 22:29
1
$\begingroup$

You still have addition and multiplication in your non-standard model. Hence you may define $$ \operatorname{prime}(p)\stackrel{\text{def}}\iff p>1 \land \forall a\forall b(ab=p\to (a=1\lor b=1))$$ (even though that actually defines irreducible instead of prime)

$\endgroup$
  • $\begingroup$ Thanks. I feel somewhat silly for writing such a long explanation of a question with such a simple answer. $\endgroup$ – M10687 Jan 25 '16 at 22:13

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.