Highness properties close to PA completeness

Springer Science and Business Media LLC - Tập 244 - Trang 419-465 - 2021
Noam Greenberg1, Joseph S. Miller2, André Nies3
1School of Mathematics and Statistics, Victoria University of Wellington, Wellington, New Zealand
2Department of Mathematics, University of Wisconsin, Madison, Madison, USA
3Department of Computer Science, University of Auckland, Auckland, New Zealand

Tóm tắt

Suppose we are given a computably enumerable object. We are interested in the strength of oracles that can compute an object that approximates this c.e. object. It turns out that in many cases arising from algorithmic randomness or computable analysis, the resulting highness property is either close to, or equivalent to being PA complete. We examine, for example, majorizing a c.e. martingale by an oracle-computable martingale, computing lower bounds for two variants of Kolmogorov complexity, and computing a subtree of positive measure with no dead-ends of a given $$\prod _1^0$$ tree of positive measure. We separate PA completeness from the latter property, called the continuous covering property. We also separate the corresponding principles in reverse mathematics.

Tài liệu tham khảo