3
$\begingroup$

Since the theorems of (PA + "there is a nonstandard number") are recursively enumerable, by the
Low Basis Theorem, WKL0's proof of the completeness theorem gives a nonstandard model of PA of [low degree](http://en.wikipedia.org/wiki/Low_(computability). After seeing Adam Day's answer to
this question, I wonder "how easy" such a model could be to compute.


Can a low nonstandard model of PA be:
a) minimal
b) computably dominated
c) K-trivial
?

If it can be more than one of those, which can it be simultaneously?

$\endgroup$
3
  • $\begingroup$ If anyone knows how to link directly to Adam Day's answer, please edit the question to do so. $\endgroup$
    – user5810
    Dec 26, 2010 at 3:18
  • $\begingroup$ Focusing on part (a): Jockusch and Soare (1972) showed that the PA degrees are precisely the degrees of $DNR_2$ functions (i.e., diagonally nonrecursive functions with range $\lbrace 0, 1\rbrace$), and Simpson (1977) proved that the PA degrees are those degrees which compute a path through every infinite tree. I believe that either of these results should suffice to show that there can be no nonstandard model of PA with minimal degree, let alone a low such model; but I am uncertain of this. $\endgroup$ Dec 26, 2010 at 4:38
  • $\begingroup$ Although, the more I think about it, I don't see a way to actually show this; so maybe I'm just wrong. $\endgroup$ Dec 26, 2010 at 4:39

1 Answer 1

7
$\begingroup$

b) is impossible, because the only low computably dominated degree is $\mathbf 0$ (see Soare's book Recursively Enumerable Sets and Degrees) and there are no computable nonstandard models of PA.

a) (minimal) and c) (K-trivial) are also impossible. See Theorem 4.2 of Csima/Harizanov/Hirschfeldt/Shore, Bounding homogeneous models. They give literature references for the fact that computing the atomic diagram of a nonstandard model of PA is equivalent to computing a PA degree, i.e., a complete extension of PA. Such a Turing degree cannot be minimal, because a PA degree bounds a 1-random degree, and the even and odd halves of a 1-random set are of incomparable degree. A PA degree cannot be K-trivial because each K-trivial degree is c.e. traceable, which implies it is not a DNR degree, which implies it is not a PA degree. See Nies, Computability and Randomness, Oxford Logic Guides, 2009.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.