Turing degrees of nonstandard models of PA - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T13:57:33Z http://mathoverflow.net/feeds/question/50392 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50392/turing-degrees-of-nonstandard-models-of-pa Turing degrees of nonstandard models of PA Ricky Demer 2010-12-26T03:14:42Z 2010-12-26T05:50:32Z <p>Since the theorems of (PA + "there is a nonstandard number") are recursively enumerable, by the <br> <a href="http://en.wikipedia.org/wiki/Low_basis_theorem" rel="nofollow">Low Basis Theorem</a>, <a href="http://en.wikipedia.org/wiki/Reverse_mathematics#Weak_K.C3.B6nig.27s_lemma_WKL0" rel="nofollow">WKL0</a>'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 <a href="http://mathoverflow.net/questions/29550/completeness-easiest-hardest-problems/35566#35566" rel="nofollow">answer</a> to <br> <a href="http://mathoverflow.net/questions/29550/completeness-easiest-hardest-problems" rel="nofollow">this question</a>, I wonder "how easy" such a model could be to compute.</p> <p><br></p> <p>Can a low nonstandard model of PA be: <br> a) minimal <br> b) computably dominated <br> c) K-trivial <br> ?</p> <p>If it can be more than one of those, which can it be simultaneously?</p> http://mathoverflow.net/questions/50392/turing-degrees-of-nonstandard-models-of-pa/50397#50397 Answer by Bjørn Kjos-Hanssen for Turing degrees of nonstandard models of PA Bjørn Kjos-Hanssen 2010-12-26T05:10:29Z 2010-12-26T05:50:32Z <p>b) is impossible, because the only low computably dominated degree is $\mathbf 0$ (see Soare's book <em>Recursively Enumerable Sets and Degrees</em>) and there are no computable nonstandard models of PA.</p> <p>a) (minimal) and c) (K-trivial) are also impossible. See Theorem 4.2 of Csima/Harizanov/Hirschfeldt/Shore, <em>Bounding homogeneous models</em>. 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, <em>Computability and Randomness</em>, Oxford Logic Guides, 2009.</p>