Constructive logic and the Medvedev lattice. (English) Zbl 1107.03024

Summary: We study the connection between factors of the Medvedev lattice and constructive logic. The algebraic properties of these factors determine logics lying in between intuitionistic propositional logic and the logic of the weak law of the excluded middle (also known as De Morgan, or Jankov, logic). We discuss the relation between the weak law of the excluded middle and the algebraic notion of join-reducibility. Finally we discuss autoreducible degrees.


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


[1] Balbes, R., and P. Dwinger, Distributive Lattices , University of Missouri Press, Columbia, 1974. · Zbl 0321.06012
[2] Dyment, E. Z., ”Certain properties of the Medvedev lattice”, Mathematics of the USSR Sbornik , vol. 30 (1976), pp. 321–40. · Zbl 0382.03028 · doi:10.1070/SM1976v030n03ABEH002277
[3] Jankov, V. A., ”Calculus of the weak law of the excluded middle”, Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya , vol. 32 (1968), pp. 1044–51. In Russian. · Zbl 0187.26306 · doi:10.1070/IM1968v002n05ABEH000690
[4] Jockusch, C. G., Jr., and M. S. Paterson, ”Completely autoreducible degrees”, Zeitschrift für mathematische Logik und Grundlagen der Mathematik , vol. 22 (1976), pp. 571–75. · Zbl 0384.03026 · doi:10.1002/malq.19760220164
[5] Kolmogoroff, A., ”Zur Deutung der intuitionistischen Logik”, Mathematische Zeitschrift , vol. 35 (1932), pp. 58–65. · Zbl 0004.00201 · doi:10.1007/BF01186549
[6] Lachlan, A. H., and R. Lebeuf, ”Countable initial segments of the degrees of unsolvability”, The Journal of Symbolic Logic , vol. 41 (1976), pp. 289–300. · Zbl 0361.02054 · doi:10.2307/2272227
[7] Lerman, M., Degrees of Unsolvability. Local and Global Theory , Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. · Zbl 0542.03023
[8] Medvedev, Y. T., ”Degrees of difficulty of the mass problem”, Doklady Akademii Nauk SSSR , vol. 104 (1955), pp. 501–504. · Zbl 0065.00301
[9] Medvedev, Y. T., ”Finite problems”, Doklady Akademii Nauk SSSR , vol. 142 (1962), pp. 1015–1018. · Zbl 0286.02028
[10] Muchnik, A. A., ”On strong and weak reducibility of algorithmic problems”, Sibirskiĭ Matematicheskiĭ Zhurnal , vol. 4 (1963), pp. 1328–41. In Russian.
[11] Odifreddi, P., Classical Recursion Theory. The Theory of Functions and Sets of Natural Numbers , vol. 125 of Studies in Logic and the Foundations of Mathematics , North-Holland Publishing Co., Amsterdam, 1989. · Zbl 0744.03044
[12] Rogers, H., Jr., Theory of Recursive Functions and Effective Computability , McGraw-Hill Book Co., New York, 1967. · Zbl 0183.01401
[13] Shen, A., and N. Vereshchagin, ”Logical operations and Kolmogorov complexity”, Theoretical Computer Science , vol. 271 (2002), pp. 125–29. Electronic Colloquium on Computational Complexity, report TR01-088, 2001. · Zbl 0982.68079 · doi:10.1016/S0304-3975(01)00035-4
[14] Skvortsova, E. Z., ”A faithful interpretation of the intuitionistic propositional calculus by means of an initial segment of the Medvedev lattice”, Sibirskiĭ Matematicheskiĭ Zhurnal , vol. 29 (1988), pp. 133–39. In Russian. · Zbl 0661.03003 · doi:10.1007/BF00975025
[15] Sorbi, A., ”Some remarks on the algebraic structure of the Medvedev lattice”, The Journal of Symbolic Logic , vol. 55 (1990), pp. 831–53. · Zbl 0703.03022 · doi:10.2307/2274668
[16] Sorbi, A., ”Embedding Brouwer algebras in the Medvedev lattice”, Notre Dame Journal of Formal Logic , vol. 32 (1991), pp. 266–75. · Zbl 0737.06009 · doi:10.1305/ndjfl/1093635751
[17] Sorbi, A., ”Some quotient lattices of the Medvedev lattice”, Zeitschrift für mathematische Logik und Grundlagen der Mathematik , vol. 37 (1991), pp. 167–82. · Zbl 0702.03021 · doi:10.1002/malq.19910370905
[18] Sorbi, A., ”The Medvedev lattice of degrees of difficulty”, pp. 289–312 in Computability, Enumerability, Unsolvability: Directions in Recursion Theory , edited by S. B. Cooper, T. A. Slaman, and S. S. Wainer, vol. 224 of London Mathematical Society Lecture Notes , Cambridge University Press, Cambridge, 1996. · Zbl 0849.03033
[19] Terwijn, S. A., ”The Medvedev lattice of computably closed sets”. Archive for Mathematical Logic , vol. 45 (2006), pp. 179–90. · Zbl 1090.03010 · doi:10.1007/s00153-005-0278-y
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.