MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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]( 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?

share|cite|improve this question
If anyone knows how to link directly to Adam Day's answer, please edit the question to do so. – Ricky Demer Dec 26 '10 at 3:18
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. – Noah Schweber Dec 26 '10 at 4:38
Although, the more I think about it, I don't see a way to actually show this; so maybe I'm just wrong. – Noah Schweber Dec 26 '10 at 4:39
up vote 7 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.