Skip to main content
MathOverflow

Return to Question

replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 3

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 answeranswer to
this questionthis 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?

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?

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?

added 107 characters in body
Source Link
Andrés E. Caicedo
Andrés E. Caicedo
  • 32.5k
  • 5
  • 133
  • 240

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 answeranswer 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?

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?

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?

Source Link
user5810
user5810

Turing degrees of nonstandard models of PA

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?