The finite intervals of the Muchnik lattice

Terwijn, Sebastiaan

doi:10.1090/S0002-9947-2011-05384-5

The finite intervals of the Muchnik lattice

Author: Sebastiaan A. Terwijn
Journal: Trans. Amer. Math. Soc. 364 (2012), 2521-2538
MSC (2010): Primary 03D30, 03G10, 06B05, 06D20
DOI: https://doi.org/10.1090/S0002-9947-2011-05384-5
Published electronically: December 16, 2011
MathSciNet review: 2888218
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We characterize the finite intervals of the Muchnik lattice by proving that they form a certain proper subclass of the finite distributive lattices. We also discuss infinite intervals, mainly to conclude that much more is possible here than for the related Medvedev lattice.

1. James E. Baumgartner, Almost-disjoint sets, the dense set problem and the partition calculus, Ann. Math. Logic 9 (1976), no. 4, 401–439. MR 401472, https://doi.org/10.1016/0003-4843(76)90018-8
2. Stephen Binns and Stephen G. Simpson, Embeddings into the Medvedev and Muchnik lattices of Π⁰₁ classes, Arch. Math. Logic 43 (2004), no. 3, 399–414. MR 2052891, https://doi.org/10.1007/s00153-003-0195-x
3. W. W. Comfort and Dieter Remus, Long chains of Hausdorff topological group topologies, Proceedings of the Conference on Locales and Topological Groups (Curaçao, 1989), 1991, pp. 53–72. MR 1100505, https://doi.org/10.1016/0022-4049(91)90006-N
4. E. Z. Dyment, Certain properties of the Medvedev lattice, Mat. Sb. (N.S.) 101(143) (1976), no. 3, 360–379, 455 (Russian). MR 0432433
5. George Grätzer, General lattice theory, 2nd ed., Birkhäuser Verlag, Basel, 1998. New appendices by the author with B. A. Davey, R. Freese, B. Ganter, M. Greferath, P. Jipsen, H. A. Priestley, H. Rose, E. T. Schmidt, S. E. Schmidt, F. Wehrung and R. Wille. MR 1670580
6. A. H. Lachlan and R. Lebeuf, Countable initial segments of the degrees of unsolvability, J. Symbolic Logic 41 (1976), no. 2, 289–300. MR 403937, https://doi.org/10.2307/2272227
7. Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718
8. Yu. T. Medvedev, Degrees of difficulty of the mass problem, Dokl. Akad. Nauk SSSR (N.S.) 104 (1955), 501–504 (Russian). MR 0073542
9. Albert A. Muchnik, Negative answer to the problem of reducibility in the theory of algorithms, Dokl. Akad. Nauk. SSSR (N.S.) 108 (1956) 194-197.
10. A. A. Mučnik, On strong and weak reducibility of algorithmic problems, Sibirsk. Mat. Ž. 4 (1963), 1328–1341 (Russian). MR 0200151
11. Piergiorgio Odifreddi, Classical recursion theory, Studies in Logic and the Foundations of Mathematics, vol. 125, North-Holland Publishing Co., Amsterdam, 1989. The theory of functions and sets of natural numbers; With a foreword by G. E. Sacks. MR 982269
12. Richard A. Platek, A note on the cardinality of the Medvedev lattice, Proc. Amer. Math. Soc. 25 (1970), 917. MR 262080, https://doi.org/10.1090/S0002-9939-1970-0262080-7
13. Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
14. Paul Shafer, A characterization of the join-irreducible Medvedev degrees, (abstract), in: Computability in Europe, CiE 2009, Lecture Notes in Computer Science 5635, p. 353.
15. Andrea Sorbi, Some remarks on the algebraic structure of the Medvedev lattice, J. Symbolic Logic 55 (1990), no. 2, 831–853. MR 1056392, https://doi.org/10.2307/2274668
16. Andrea Sorbi, Embedding Brouwer algebras in the Medvedev lattice, Notre Dame J. Formal Logic 32 (1991), no. 2, 266–275. MR 1123000, https://doi.org/10.1305/ndjfl/1093635751
17. Andrea Sorbi, The Medvedev lattice of degrees of difficulty, Computability, enumerability, unsolvability, London Math. Soc. Lecture Note Ser., vol. 224, Cambridge Univ. Press, Cambridge, 1996, pp. 289–312. MR 1395886, https://doi.org/10.1017/CBO9780511629167.015
18. Andrea Sorbi and Sebastiaan A. Terwijn, Intermediate logics and factors of the Medvedev lattice, Ann. Pure Appl. Logic 155 (2008), no. 2, 69–85. MR 2455558, https://doi.org/10.1016/j.apal.2008.03.002
19. Sebastiaan A. Terwijn, Constructive logic and the Medvedev lattice, Notre Dame J. Formal Logic 47 (2006), no. 1, 73–82. MR 2211183, https://doi.org/10.1305/ndjfl/1143468312
20. Sebastiaan A. Terwijn, Constructive logic and computational lattices, habilitation thesis, Technical University of Vienna, 2007.
21. Sebastiaan A. Terwijn, On the structure of the Medvedev lattice, J. Symbolic Logic 73 (2008), no. 2, 543–558. MR 2414464, https://doi.org/10.2178/jsl/1208359059