Transactions of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

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
Posted: December 16, 2011
Full-text PDF

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.

References

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 0401472 (53 #5299)
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 (2004m:03156), http://dx.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 (92f:22001), http://dx.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 (55 #5421)
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 (2000b:06001)
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 0403937 (53 #7746)
7. Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718 (85h:03044)
8. Yu. T. Medvedev, Degrees of difficulty of the mass problem, Dokl. Akad. Nauk SSSR (N.S.) 104 (1955), 501–504 (Russian). MR 0073542 (17,448b)
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 (34 #50)
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 (90d:03072)
12. Richard A. Platek, A note on the cardinality of the Medvedev lattice, Proc. Amer. Math. Soc. 25 (1970), 917. MR 0262080 (41 #6690)
13. Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York, 1967. MR 0224462 (37 #61)
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 (91c:03038), http://dx.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 (92j:03056), http://dx.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 (97g:03048), http://dx.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 (2009j:03066), http://dx.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 (electronic). MR 2211183 (2007h:03077), http://dx.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 (2009c:03041), http://dx.doi.org/10.2178/jsl/1208359059

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|