12
$\begingroup$

By the compactness theorem, there are nonstandard models where don't have finite prime decomposition, and some elements are divisible by infinitely many distinct primes. But what if we want a nice nonstandard model where any element is divisible by only finitely distinct primes, is it possible? It seems hard to construct one, if it is possible. I don't know how to construct models of Peano's arithmetic where I don't want something to happen.

Of course, we cannot ask for finite prime decomposition, because in any nonstandard model there are nonstandard elements whose only prime divisor is $2$, and hence they are divisible by $2^n$ for any $n \in \mathbb{N}$.

If such a model exists, can we have one of any infinite cardinality?

$\endgroup$
2
  • $\begingroup$ Would the factorial of a non-standard integer have this property, being divisible by all standard primes? $\endgroup$ Feb 19 at 23:30
  • $\begingroup$ @BerenGunsolus I'm not sure how to define the factorial in Peano's arithmetic. $\endgroup$ Feb 20 at 0:05

2 Answers 2

25
$\begingroup$

There is no such model. The following is a theorem of Peano arithmetic:

For every number $n$, there is some number $n'$ that is divisible by all $k < n$.

Consider a non-standard model $\langle \mathfrak{M}, +, \cdot, 0, S\rangle$ of Peano arithmetic. Since $\mathfrak{M}$ is non-standard, it has some non-standard element $K$ so that $0 < K, 1 < K, 2 < K, \dots$ and so on, for each standard natural.

By the theorem of Peano arithmetic quoted above, there is another number $K'$ that is divisible by all $k < K$. In particular, $K'$ is divisible by $2$, divisible by $3$, divisible by $5$, and so on for all the standard primes.

$\endgroup$
1
  • 9
    $\begingroup$ +1. To the OP, more generally anything like the situation you describe is ruled out by overspill. Consider, in a model $M$ of $\mathsf{PA}$, the set of numbers of prime factors that elements can have. This is unbounded in the standard part of $M$, and so by overspill must contain nonstandard elements. Of course in this particular case we can say much more, but overspill is still worth knowing about. $\endgroup$ Feb 17 at 2:06
10
$\begingroup$

The question is interesting and I want to add some non-technical comments to the technically impeccable answer of Z.A.K.

To construct models of PA where something doesn't happen is a notorious difficult problem especially when this something is expressible in first-order logic.

One of the few known results of this sort is the celebrated Paris-Harrington Theorem that construct a model of PA where a (true) variant of Ramsey's Theorem does not hold.

Time ago, it was hoped that weaker versions of PA (i.e. fragments where induction only applies to formulas of low complexity) could make the task of constructing models more feasible.

E.g. Much effort has been spent on the question of whether $I\Delta_0$ (the fragment of PA where induction only applies to bounded formulas) proves the infinity of primes. But the problem was deemed intractable and abandoned some 40 years ago. (The problem is connected with some hopeless open problems in complexity theory.)

$\endgroup$
4
  • $\begingroup$ Can you elaborate on that last parenthesis? $\endgroup$
    – cody
    Feb 18 at 16:06
  • 1
    $\begingroup$ @cody I cannot add much more. The $\Delta_0$ hirerarchy is naturally/usually/intuitively associated to the linear time hierarchy (just read numbers as their binary expansion). Surely someone has dealt with this association formally. If you need a reference I can have a look. $\endgroup$ Feb 18 at 17:27
  • 1
    $\begingroup$ I don't need a reference, I'm just curious. Indeed, a reference where they even mention that this is an open problem would be interesting! $\endgroup$
    – cody
    Feb 18 at 23:07
  • $\begingroup$ @cody I suspect that it's mentioned in the early part of the (excellent!) book Metamathematics of first-order arithmetic, although I don't have time at the moment to check. $\endgroup$ Feb 19 at 22:23

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.