The finite intervals of the Muchnik lattice

Terwijn, Sebastiaan

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

The finite intervals of the Muchnik lattice
HTML articles powered by AMS MathViewer

by Sebastiaan A. Terwijn PDF

Trans. Amer. Math. Soc. 364 (2012), 2521-2538 Request permission

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

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, DOI 10.1016/0003-4843(76)90018-8
Stephen Binns and Stephen G. Simpson, Embeddings into the Medvedev and Muchnik lattices of $\Pi ^0_1$ classes, Arch. Math. Logic 43 (2004), no. 3, 399–414. MR 2052891, DOI 10.1007/s00153-003-0195-x
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, DOI 10.1016/0022-4049(91)90006-N
E. Z. Dyment, Certain properties of the Medvedev lattice, Mat. Sb. (N.S.) 101(143) (1976), no. 3, 360–379, 455 (Russian). MR 0432433
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
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, DOI 10.2307/2272227
Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718, DOI 10.1007/978-3-662-21755-9
Yu. T. Medvedev, Degrees of difficulty of the mass problem, Dokl. Akad. Nauk SSSR (N.S.) 104 (1955), 501–504 (Russian). MR 0073542
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.
A. A. Mučnik, On strong and weak reducibility of algorithmic problems, Sibirsk. Mat. Ž. 4 (1963), 1328–1341 (Russian). MR 0200151
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
Richard A. Platek, A note on the cardinality of the Medvedev lattice, Proc. Amer. Math. Soc. 25 (1970), 917. MR 262080, DOI 10.1090/S0002-9939-1970-0262080-7
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
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.
Andrea Sorbi, Some remarks on the algebraic structure of the Medvedev lattice, J. Symbolic Logic 55 (1990), no. 2, 831–853. MR 1056392, DOI 10.2307/2274668
Andrea Sorbi, Embedding Brouwer algebras in the Medvedev lattice, Notre Dame J. Formal Logic 32 (1991), no. 2, 266–275. MR 1123000, DOI 10.1305/ndjfl/1093635751
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, DOI 10.1017/CBO9780511629167.015
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, DOI 10.1016/j.apal.2008.03.002
Sebastiaan A. Terwijn, Constructive logic and the Medvedev lattice, Notre Dame J. Formal Logic 47 (2006), no. 1, 73–82. MR 2211183, DOI 10.1305/ndjfl/1143468312
Sebastiaan A. Terwijn, Constructive logic and computational lattices, habilitation thesis, Technical University of Vienna, 2007.
Sebastiaan A. Terwijn, On the structure of the Medvedev lattice, J. Symbolic Logic 73 (2008), no. 2, 543–558. MR 2414464, DOI 10.2178/jsl/1208359059