Since the theorems of (PA + "there is a nonstandard number") are recursively enumerable, by the
  

[Low Basis Theorem](http://en.wikipedia.org/wiki/Low_basis_theorem), [WKL0](http://en.wikipedia.org/wiki/Reverse_mathematics#Weak_K.C3.B6nig.27s_lemma_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](https://mathoverflow.net/questions/29550/completeness-easiest-hardest-problems/35566#35566) to
  

[this question](https://mathoverflow.net/questions/29550/completeness-easiest-hardest-problems), 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?



Turing degrees of nonstandard models of PA
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.


