×

The Medvedev lattice of computably closed sets. (English) Zbl 1090.03010

Summary: Simpson introduced the lattice \(\mathfrak P\) of \(\Pi^{0}_{1}\) classes under Medvedev reducibility. Questions regarding completeness in \(\mathfrak P\) are related to questions about measure and randomness. We present a solution to a question of Simpson about Medvedev degrees of \(\Pi^{0}_{1}\) classes of positive measure that was independently solved by Simpson and Slaman. We then proceed to discuss connections to constructive logic. In particular we show that the dual of \(\mathfrak P\) does not allow an implication operator (i.e. that \(\mathfrak P\) is not a Heyting algebra). We also discuss properties of the class of PA-complete sets that are relevant in this context.

MSC:

03D30 Other degrees and reducibilities in computability and recursion theory
03B55 Intermediate logics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balbes, R., Dwinger, P.: Distributive lattices. University of Missouri Press, 1974 · Zbl 0321.06012
[2] Binns, S.: A splitting theorem for the Medvedev and Muchnik lattices. Mathematical Logic Quarterly 49, 327–335 (2003) · Zbl 1022.03021
[3] Binns, S, Simpson, S. G.: Embeddings into the Medvedev and Muchnik lattices of {\(\Pi\)}01 classes. Archive for Mathematical Logic 43, 399–414 (2004) · Zbl 1058.03041
[4] Cenzer, D.: {\(\Pi\)}01 classes in computability theory. Handbook of computability theory, Studies in Logic and the Foundations of Mathematics 140, North-Holland, Amsterdam, 1999 pp. 37–85 · Zbl 0939.03047
[5] Cenzer, D., Hinman, P.: Density of the Medvedev lattice of {\(\Pi\)}01 classes, Archive for Mathematical Logic 42 (6), 583–600 (2003) · Zbl 1037.03040
[6] Jankov, A.V.: Calculus of the weak law of the excluded middle. Izv. Akad. Nauk SSSR Ser. Mat. 32, 1044–1051 (1968) (In Russian.)
[7] Jockusch, C. G. Jr, McLaughlin, T. G.: Countable retracing functions and {\(\Pi\)}02 predicates. Pacific Journal of Mathematics 30, 67–93 (1969) · Zbl 0181.30602
[8] Carl J. G., Jr., Robert Soare, I.: Degrees of members of {\(\Pi\)}01 classes. Pacific Journal of Mathematics 40 (3), 605–616 (1972) · Zbl 0209.02201
[9] Jockusch, C. G. Jr, Soare, R. I.: {\(\Pi\)}01 classes and degrees of theories, Transactions of the American Mathematical Society 173, 35–56 (1972) · Zbl 0262.02041
[10] Kučera, A.: Measure, {\(\Pi\)}10-classes and complete extensions of PA. In: H.-D. Ebbinghaus, G. H. Müller, and G. E. Sacks (eds), Recursion theory week, Lect. Notes in Math. 1141, Springer-Verlag, 1985, pp. 245–259
[11] Medvedev, Yu. T., Degrees of difficulty of the mass problems. Dokl. Akad. Nauk. SSSR 104 (4), 501–504 (1955)
[12] Medvedev, Yu. T.: Finite problems. Dokl. Akad. Nauk. SSSR (NS) 142 (5), 1015–1018 (1962)
[13] Muchnik, A. A.: On strong and weak reducibility of algorithmic problems. Sibirsk. Math. Zh 4, 1328–1341 (1963)
[14] Odifreddi, P. G.: Classical recursion theory Vol. I. Studies in logic and the foundations of mathematics 125, North-Holland, 1989 · Zbl 0661.03029
[15] Odifreddi, P. G.: Classical Recursion Theory Vol. II. Studies in logic and the foundations of mathematics 143, North-Holland, 1999 · Zbl 0931.03057
[16] Rogers, H, Jr.: Theory of recursive functions and effective computability, McGraw-Hill, 1967 · Zbl 0183.01401
[17] Simpson, S. G.: slides for a talk posted on http://www.math.psu.edu/simpson/talks/umn0105, 2003
[18] Simpson, S. G.: {\(\Pi\)}01 sets and models of WKL0 to appear in: Reverse Mathematics 2001. Lecture Notes in Logic, ASL
[19] Simpson, S. G., Slaman, T. A.: Medvedev degrees of {\(\Pi\)}01 subsets of 2{\(\omega\)}. unpublished manuscript
[20] Skvortsova, E. Z.: A faithful interpretation of the intuitionistic propositional calculus by means of an initial segment of the Medvedev lattice, Sibirsk. Math. Zh. 29 (1), 171–178 (1988) (In Russian.) · Zbl 0649.03007
[21] Sorbi, A.: Some remarks on the algebraic structure of the Medvedev lattice. Journal of Symbolic Logic 55 (2), 831–853 (1990) · Zbl 0703.03022
[22] Sorbi, A.: Embedding Brouwer algebras in the Medvedev lattice. Notre Dame Journal of Formal Logic 32 (2), 266–275 (1991) · Zbl 0737.06009
[23] Sorbi, A.: Some quotient lattices of the Medvedev lattice. Zeitschrift für mathematische Logik und Grundlagen der Mathematik 37, 167–182 (1991) · Zbl 0702.03021
[24] Sorbi, A.: The Medvedev lattice of degrees of difficulty. In: S. B. Cooper, T. A. Slaman, and S.S. Wainer (eds.), Computability, Enumerability, Unsolvability: Directions in Recursion Theory, London Mathematical Society Lecture Notes 224, Cambridge University Press, 1996, pp. 289–312 · Zbl 0849.03033
[25] Sorbi, A.: personal communication, Siena, July 2004
[26] Terwijn, S. A.: Complexity and Randomness. Rendiconti del Seminario Matematico di Torino 62 (1), 1–38 (2004) · Zbl 1121.68058
[27] Terwijn, S. A.: Constructive logic and the Medvedev lattice, Journal of Formal Logic (in press) Notre Dame · Zbl 1107.03024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.