Turing degrees of nonstandard models of PA

2010-12-26T03:14:42Z

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?

Answer by Bjørn Kjos-Hanssen for Turing degrees of nonstandard models of PA

2010-12-26T05:10:29Z

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.

Turing degrees of nonstandard models of PA - MathOverflow

Turing degrees of nonstandard models of PA

Answer by Bjørn Kjos-Hanssen for Turing degrees of nonstandard models of PA